Is Scheme Faster than C?

http://www.cs.indiana.edu/~jsobel/c455-c511.updated.txt

by fogus • 15 years ago

216 62 15 years ago

cs.indiana.edu

iwwr• 15 years ago

Scheme employs tail-recursion optimizations. An unoptimized recursive algorithm would indeed run faster in Scheme.

But I'd be interested in how the port to C actually happened. That is, if he translated the functional aspects of the algorithm, or if he just copied intermediary C code that a Scheme compiler can generate.

andjones• 15 years ago

I had the fortune of working with Jonathan Sobel at IU and hearing this story.

We were taught to translate a recursive program to continuation passing style in a way that many variables could be translated to registers directly. If I remember correctly, Jonathan translated this from Scheme to C and just compiled that result.

nikster2• 15 years ago

I'd be interested in the actual application of that. Scheme and Lisp don't seem to lend themselves to a powerful object oriented design very much. Since that is IMO the highest order task in programming, I have never been that interested in them.

I guess if you only write number crunching code, then yeah. But if you write an app (web or client) - what good is Lisp?

copper• 15 years ago

The conclusion is the most inspiring part of this:

> Real efficiency comes from elegant solutions, not optimized programs. Optimization is always just a few correctness-preserving transformations away

silentbicycle6• 15 years ago

More succinctly: Make it work, then make it fast.

Trying to do both at the same time is usually slower, in the long run.

colomon2• 15 years ago

Unless you define "elegant" as "conceptually optimized" or something like that, this is just nonsense. There are many cases where a superior algorithm will run circles around an elegant but not so efficient algorithm -- and no number of "correctness-preserving transformations" will bridge that gap.

flogic• 15 years ago

I believe that's the point. I can imagine though there are instances where it is easier to code up a better algorithmic solution in higher level languages than it would be in C. Lazy data fetches would be a prime example. Obviously, it can be done in C like any Turing complete language. However, it's easier in something higher level.

sliverstorm• 15 years ago

In my experience, a superior algorithm is almost always more elegant.

stcredzero3• 15 years ago

Out of a class of about 15 students, only one person beat me (and only barely), and he wrote significant portions of his program directly in Assembly Language. The next fastest after me took nearly twice as long to do the same work.

...A runtime profile of my program revealed that the majority of time was spent in the C routines "malloc" and "free."

For all of the beginning programmers and most of the student programmers out there: Yes often a fast JIT VM might actually beat your C or get pretty close! If you ever become a good programmer, then you can do much better than the JIT in key situations.

EDIT: There's a self evaluation method here for aspiring C programmers. Start benchmarking your code against the same thing in LuaJIT. You're not "good" until you know how to routinely beat it by a factor approaching 2. And that's necessary, but not sufficient.

scscsc• 15 years ago

He does not use a JIT, he translated his code into C by hand.

stcredzero3• 15 years ago

I never said he did. I think it's good to point out there's a lot of beginner C code out there involving significant memory management that's not much better or slower than the best JITs.

EDIT: Added "involving memory management"

EDIT: To students doing C programming: Be honest, now, but have you ever checked?

abrenzel• 15 years ago

I thought this was going to be another one of those benchmarking articles, but it was really a great exercise in how lateral thinking can produce clean solutions.

The more I hear about the Lisp family of languages, the more I want to give them a try sometime...

nikster2• 15 years ago

Neat as this may be - optimizing a trivial algorithm is not something you'll encounter out of school.

The lesson learned is a good one though: Good design always wins. In real life, that's obvious almost immediately, yet the concept seems to elude the vast majority of programmers.

In reality the difficulty in programming is creating powerful, flexible designs. If you can look at your own code a year later and say "wow - this is good" - then you win.

RiderOfGiraffes• 15 years ago

  > ... optimizing a trivial algorithm is not
  > something you'll encounter out of school.

Sometimes it is. For me, it happens a few times a year.

More importantly, the techniques, methods and mind set are critical daily in the code I and my employees write.

But we aren't doing web development.

sambeau• 15 years ago

Every language should be faster* than C in some way otherwise no-one would use it.

Scripting languages are faster to code in.

Fortran is faster at complex matrix maths.

Lisp is faster to code in and faster to run for a large set of computing problems.

C wins the trade-of of speed-to-create vs speed-of-execution for most system programming tasks but usually when compared to bare assembly code. But there are a large number of problems that it is horribly unsuited for. Hence we end up with c-programs with accidentally embedded lisp implementations.

* - where faster can also mean faster to code to a secure standard.

koenigdavidmj• 15 years ago

> Hence we end up with c-programs with accidentally embedded lisp implementations.

See Greenspun's Tenth Rule: Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

And of course the famous corollary: Including Common Lisp.

http://en.wikipedia.org/wiki/Greenspun%27s_Tenth_Rule

silentbicycle6• 15 years ago

XML is proof that Greenspun's Tenth Rule applies to data, as well. :)

Xurinos• 15 years ago

Correct me if I am wrong, but somewhere I read that a while back, Lisp implementations caught up to and surpassed Fortran implementations in terms of math speed... suggesting that Fortran's main strength was finally outdone.

sedachv• 15 years ago

Richard Fateman published two papers on this, one where MacLisp beat out Fortran, in 1973 (http://portal.acm.org/citation.cfm?doid=1086803.1086804), and a really comprehensive paper about Common Lisp in 1995 (http://www.scribd.com/doc/49112889/fateman-et-al-fast-floati...).

scott_s2• 15 years ago

Neat story - he was systematically applying optimizations that compilers could do if they had full knowledge of the semantics of the program. By transforming the program into continuation-passing style, he performed a very similar step that modern compilers do when they transform a program into static single assignment, then optimize the program. For a full treatment of what I mean, see A Correspondence between Continuation Passing Style and Static Single Assignment: http://www.cs.purdue.edu/homes/suresh/502-Fall2008/papers/ke...

dkarl3• 15 years ago

This makes me so nostalgic. Ah, to be back in school when the hardest thing I had to do was math, and I didn't have to worry about anyone wanting to modify my code or coming to me saying, "Hey, dkarl, we just signed a huge contract, and part of what we promised is that a 2 in the hundreds place of the left operand will be treated as a 3 when we do multiplication for this customer. What base? I don't know, rebel base alpha. I'm just the project manager. The product manager answers those kinds of questions. And make sure it's configurable, because the customer has been going back and forth a bit about the specifics, and we don't think we'll be able to nail them down before we deploy."

swannodette• 15 years ago

I would hope that your work is a healthy mix of the kind of elegant design thinking covered in the post and real world pragmatics. Also your example problem doesn't even sound particularly bothersome to implement in Scheme.

dkarl3• 15 years ago

It wouldn't be hard to implement in Scheme -- I'd actually love to work in Scheme -- but if another developer asked me how to update the code for a second customer and I replied, "Start with this Scheme source code, make your changes, then apply this series of transformations and translate the resulting code into C," I would get doused in gasoline and set on fire.

jfm3• 15 years ago

Is Scheme Hand-Compiled Into A Single Main Routine in C Faster than C?

Fixed that title for you.

silentbicycle6• 15 years ago

Really, what he's saying is that it saves a lot of time to prototype code in a convenient language, and then translate parts to optimized code in a fast language (where necessary), once good algorithms have been worked out. Many fast languages get their speed by trading away flexibility.

This is not specific to Scheme, though - while it's a good prototyping language, so are Lua (my favorite, and LuaJIT reduces the need for C), awk, Python, etc.

Knowing how to implement the prototyping languages' constructs efficiently in the "fast" language is important, though.

Of course, "fast" and "convenient" can also be the same language, such as prototyping in Common Lisp and then adding declarations. OCaml is also quite good.

dkarl3• 15 years ago

He did say the semantics-preserving transformations were easier in Scheme:

This is where Scheme really won. Because of its extremely algorithmic---almost mathematical---nature, Scheme can be easily manipulated in a sort of algebraic style.

Peaker• 15 years ago

Haskell is usually great at both convenience and speed, without having to add annotations, even, most of the time

srean2• 15 years ago

Wish the code was available to take a peek at. Talking about optimizing transformations, the Stalin scheme compiler is quite freakily good at that.It would have been interesting to run this code through Stalin and see what happens.

From the author Jerey Mark Siskind's research statement:

  It uses the results of flow analysis to perform life-time analysis, 
  escape analysis, points-to analysis, and must-alias analysis. ...
  It also uses the above analysis to support flow-directed region-based
  storage management, where run-time garbage collection is replaced
  with static allocation and deallocation on a per-abstract-value
  and per-program-point basis. It also performs flow-directed
  lightweight CPS conversion,.. to support extremely efficient first-class continuations.

It is quite remarkable that even without any type annotations Stalin can hold its own against a hand written C and often beat it as well.

http://en.wikipedia.org/wiki/Stalin_(Scheme_implementation)

(Has escaped chrismonsantoization)

igouy2• 15 years ago

Stalin download doesn't seem to have changed since 2006.

Is "Stalin can hold its own against a hand written C and often beat it" just your paraphrase of wikipedia's quote from a bare assertion in Jeffrey Siskind's Purdue research statement - or due you have some numbers to share?

srean2• 15 years ago

The Sourceforge version might be more updated. But I doubt it will differ by much from what you have, the changes in the version are in the minor numbers.

Numbers circa 2008: take a look at section 6 in ftp://ftp.ecn.purdue.edu/qobi/TR-ECE-08-02.pdf and ftp://ftp.ecn.purdue.edu/qobi/TR-ECE-08-03.pdf These are numbers from StalinGrad. A automatic differentiation engine written in Stalin (hence the Grad).

Also the thread http://groups.google.com/group/comp.lang.lisp/browse_frm/thr... that got me interested in Stalin in the first place.

With all that said, any reason to distrust research statements ? Those are usually taken seriously in academia. One only jeopardizes his position by bluffing.

asarazan• 15 years ago

I was in this program at IU, and later worked with Jonathan at Cisco-- and I actually remember this exact story being told by one of my AI's in class.

Guess it's become part of IU lore :-)

mkarazin• 15 years ago

Seems to be that way. Never worked with Jonathan but I did do my undergrad at IU. Both 311 as well as 422 (? compilers) were a ton of fun. I may still have the code for scheme to C lying around somewhere... If you are a programmer and have never used scheme I'd recommend having fun one weekend with it.

dfj225• 15 years ago

FYI, this approach, in general and completely automated, is taken by the Spiral Project DSP generator: http://spiral.net/index.html

DSP transformations are represented in a Scheme-like language. The optimizer performs operations on this language then compiles to C code.

I worked on the Spiral project on things tangental to the DSP generator, but wrote my own optimizing DSP compiler based on Spiral technology for class in university.

malkia• 15 years ago

I think this is rather useless and pointless.

My daily work for the last few weeks has been optimizing speedwise our pipeline.

Usually what we do is OpenMP (openmp.org) the code where it's possible (we deal with lots of DXT compression, mipmaps, normal map calucations, etc.)

Then where possible decrease the floating point accuracy to point where it's acceptable, and use SSE2 through some veclib.

It's all in C (C++) and the difference can be 1:10 and even more.

All I'm saying is this - you sit down, find your bottleneck and do something about it. But simply saying this is faster than this is pointless.

That to be said the language shootout is how it should be done - you have people using (trying at least) to use the same algorithms in different languages by allowing certain language (implementation) optimizations, or available libs.

Yes, I've seen LuaJIT, and LispWorks (which I love dearly) producing better code than C++, especially when comes to std::string put in stdext::hash_map<> simply because it's just harder to intern stuff in C++ (unless you do it manually). In Lua every string is interned, and in LispWorks (and in Common Lisp in general) as long as it's symbol it can be interned.

igouy2• 15 years ago

Hint - say "benchmarks game" to show you've checked the website sometime in the last couple of years ;-)

16s• 15 years ago

The use of gotos rather than function calls is interesting... man that's gutsy programming! I'd never thought to do that when considering optimizations.

swaits• 15 years ago

Sadly, the world of academia has scared people into thinking goto is the spawn of Satan. It really does have its place.

chalst2• 15 years ago

If you were to hand transform your high-level code into assembler, you would have little choice.

zandorg• 15 years ago

Goto's make code really hard to decompile.

morphir2• 15 years ago

"This is where Scheme really won. Because of its extremely algorithmic---almost mathematical---nature, Scheme can be easily manipulated in a sort of algebraic style. One can follow a series of rewrite rules (just about blindly) to transform a program into another form with some desirable property. This was exactly what I needed."

Can anyone explain this with an example? I have been pondering what he meant with this for a long time.

plinkplonk• 15 years ago

" 'One can follow a series of rewrite rules (just about blindly) to transform a program into another form with some desirable property. This was exactly what I needed.'

Can anyone explain this with an example? I have been pondering what he meant with this for a long time. "

see the cps-transform rewrite rules in "Essentials of Programming Languages". The first edition has the densest and most extensive explanation. The third edition has the clearest, but a relatively attenuated exposition.

morphir2• 15 years ago

if this proves to be true, I'm most grateful for your tips. Maybe you could be even more specific providing a page number/chapter?

http://books.google.com/books?id=GtPoyremy4EC&printsec=f...

chalst2• 15 years ago

The kind of hand transformation from a Lisp-like language into C/asm is described very well in Dan Friedman (2001)'s talk, The Role of the Study of Programming Languages in the Education of a Programmer http://www.cs.indiana.edu/hyplan/dfried/mex.ps

Friedman is at Indiana, so the similarity in the transformation is no surprise. I'm surprised the arty doesn't mention Friedman.

Is Scheme Faster than C?

Related Stories