8
$\begingroup$

Theoretically speaking, is it possible to have a Lisp/Scheme compiler that can produce code that can compete with compiled C, let's say within 15-25% margin?

In my testing, I've found that the current crop of compilers (Bigloo, SBCL, Gambit, Chicken, etc) are 20-50 times slower than equivalent C code.

The only outlier is the Stalin compiler. For simple programs, it produces binaries that are equivalent to C. However, what I find suspicious is that none of the other projects (Bigloo, Chicken, Clozure, etc) have attempted to implement whatever tricks Stalin uses ("whole program optimization", etc).

I'm a huge fan of LISP since the mid 90s and would love to bring it on board so my team can crank out projects in half the time in normally takes using C/C++/.NET/etc, but...the performance issues are a huge roadblock.

I wonder if the lack of quality LISP compilers are due to the fact that no serious time and money has been invested into the subject OR if this simply isn't a feasible task given the current state of compiler technology??

$\endgroup$
9
  • 1
    $\begingroup$ I believe you tested the Common Lisp compilers with (declare (optimize ...)), (declare (<type> <var)) and (the <type> <expr>) in your functions? Otherwise it's hardly a fair comparison :) $\endgroup$ Commented Feb 4, 2013 at 22:21
  • 1
    $\begingroup$ I think cs.stackexchange.com/questions/842/… answers this question. $\endgroup$
    – Kyle Jones
    Commented Feb 4, 2013 at 22:25
  • $\begingroup$ @KyleJones Does it? My guess is that with maximum optimizations, Common Lisp can get within the margin specified by the OP, if not closer. $\endgroup$ Commented Feb 4, 2013 at 22:38
  • $\begingroup$ Just changing the programming language will never get your team to crank out four times as much correct code in the same time. What studies have shown is that programmers experienced in the language turn out approximately the same number of code lines per unit time for fixed problem complexity, independent of the language. So you won't gain anything unless in your problem area LISP programs are much shorter. One other thing to consider is that you have to get people experienced in LISP for development and maintenance. And those are far in between. $\endgroup$
    – vonbrand
    Commented Feb 4, 2013 at 23:27
  • 1
    $\begingroup$ It seems to me that this question asks more for programmer experience than for a scientific answer. Therefore, this may be the wrong site for the question. $\endgroup$
    – Raphael
    Commented Feb 6, 2013 at 7:50

1 Answer 1

7
$\begingroup$

As noted in the comments, it isn't very exact to state "the current crop of compilers (Bigloo, SBCL, Gambit, Chicken, etc) are 20-50 times slower than equivalent C code", without qualifying how you tested and what you tested.

For my use, I find that for many things Gambit and Chicken Scheme are quite close to the equivalent 'C' code in speed, with the current version of Gambit (4.7.3) generally faster than Chicken (4.9.0.1) but over pre-optimizing the output 'C' code (making assumptions about the number of available registers - assumes x686 - and forcing the use of stack memory for any extra memory requirements, which decisions should be left to the 'C' compiler as Chicken does, which often eliminates the requirement for extra registers and combines processing steps) so as to prevent the 'C' compiler from doing its own optimizations resulting in very tight small loops being up to about twice as slow as those same tight small loops in 'C' (or Chicken); Chicken just defines as many variables local to a given function as it sees fit (mostly used immutably) and then depends on the compiler to optimize most of those away. Chicken doesn't seem to optimize Continuation Passing Style (CPS) algorithms with multiple forked levels of continuations as well as Gambit and can be up to about eight times slower than Gambit for these, but then one thinks that CPS isn't really formalized for 'C' code at all so...

EDIT_ADD: I have done some more research into the Chicken and Gambit-C Scheme versions and have found the following:

  1. Chicken is faster than Gambit for small tight loops for the above reason (depends more on the 'C' compiler for optimizations without doing as much itself and thus takes better advantage of x86-64 extra registers), but also because it doesn't include a "POLL" stack maintenance check inside the loops, whereas Gambit includes the "POLL" check inside the loop. Even when this isn't triggered (the usual case), it will take several CPU clock cycles to determine that nothing is required (about 6 cycles). A future smarter compiler might see that there is no need to do a stack check when inside a tight loop and not doing stack-building operations, doing it just before or after the loop and save this time.

  2. Gambit's 'C' macro's do too much work, as said, in precisely defining how the operations should be carried out, especially including fixed stack size operations, and these are likely harder for the 'C' compiler to optimize; using registers more effectively could reduce tight loop time by perhaps 4 cycles, which in combination with the above would put it into the Chicken ballpark.

  3. Neither output "read/modify/write" optimizations for say vector operations that are modify in place and don't output code so that the compiler does it. A smarter backend such as LLVM when used with Haskell does this kind of thing. This would reduce register use by one and execution time in using only a single instruction rather than a separate read, computation of the modification, and a write to the same location; this would become just a calculation of the modification (say a bit or), and then a read modify (|=) write single instruction. This might make the speed faster by a cycle or so

  4. Both are dynamically typed and process data "tag" bits as part of their data. Neither are smart enough for tight loops to reduce the tags, perform the loop "tag-less", then add the tags back for any results from the loop, nor do they produce code where the 'C' compiler can see to do this although it does combine these operations for some cases. Optimization here could reduce loop times by a couple of CPU cycles or so, depending on the loop.

  5. Very tight 'C' loops can take about 3.5 CPU clock cycles per loop on a fast CPU that isn't memory cache access speed throttled (such as AMD Bulldozer, which is about twice as slow); the same loop in Chicken currently takes about 6 cycles and Gambit takes about 16.9 cycles. With all of the optimizations as per the above, there is no reason that these implementations of Scheme couldn't do that, however some work is required:

  6. In the case of Gambit, the harder work might be improving the flow analysis to recognize when no "POLL" tests need to be inserted (ie. could this be interrupt driven, although the compiler does allow interrupts to be turned off for some uses?); the easier improvement would be to just implement better register usage (ie. recognize x86-64 registers better rather than the default x686 architecture). For both, better flow analysis to recognize that they can "untag" the data, especially "fixnum", "flonum", and vector, data so these operations aren't necessary inside tight loops and combining read/modify/write instructions. Both of these ends could be accomplished by using a better backend such as LLVM (not a trivial amount of work, but both are already partly there).

Conclusion: Chicken is currently about 50% slower than 'C' on the fastest CPU's (not my Bulldozer, where it is about the same speed due to cache throttling of the 'C' code) and Gambit is about 400% slower (only about 125% slower on my slow Bulldozer). However, future improvements to the compilers could reduce this so that either code is no slower than 'C' or within the margin that the OP specifies.

A more complex language such as Haskell, when using the LLVM backend, paying careful attention to strictness use (not a problem with scheme which is always eager by default), and using appropriate data structures (ST unboxed arrays rather than lists for tight loops; somewhat applicable to Scheme using vectors), runs at about the same speed as 'C' if the LLVM backend is used with full optimizations. If it can do this, so can Scheme with the above compiler improvements.

AGAIN, there is no way that either of these is 20 to 50 times as slow when used with proper optimization flags. END_EDIT_ADD

Of course, all benchmarks are invalidated if one does not use the appropriate optimization settings for each as one would in a production environment...

I would think that the commercial Chez Scheme compiler would be in the ballpark as to producing high performance output as do Gambit and Chicken, as being commercial it surely has some "serious time and money invested into it".

The only way I can get Gambit or Chicken to run as slow as "20 to 50 times slower than 'C'" is to not use any optimization settings, in which case they often don't run much faster than as interpreted in their REPL's - 10's of times slower than as properly using those settings.

Is it possible that the OP hasn't tested using these settings properly?

If the OP cares to clarify his testing procedures, I will gladly edit this answer to show that at least Gambit and Chicken don't have to be that slow.

$\endgroup$
6
  • $\begingroup$ Is this with runtime type checks disabled? I would not want to do that in production, as it makes bugs exploitable that previously were not. $\endgroup$
    – Demi
    Commented Sep 7, 2015 at 23:48
  • $\begingroup$ @Demetri, with most of the Scheme compilers such as Gambit-C, Chicken, or Bigloo, one gets about a three times speed up for many benchmarks by disabling all runtime checks, but the code is still not "20 to 50 times slower" as stated by the OP question. In fact, many of these checks can be safely disabled in production code after checking for problems in debugging without risk by writing the code so that such checks are built-in to the code only when necessary. $\endgroup$ Commented Sep 8, 2015 at 1:10
  • $\begingroup$ @Demetri I can attest to chicken scheme being in the ballpark of 1.5-2.5x slower than C for benchmark code, if compiled with optimizations. But yeah it's horribly slow if compiled without optimizations. FWIW I get best results from using fixnum-ops, unboxed-objects and allowing block compilation, i.e. better static-analysis leading to better optimizations. $\endgroup$ Commented Nov 16, 2015 at 19:34
  • $\begingroup$ I am more worried about runtime safety checks -- I would not want a bug that did not show up in testing to be an exploitable buffer overflow. Obviously one would turn on optimizations. $\endgroup$
    – Demi
    Commented Nov 16, 2015 at 22:24
  • $\begingroup$ @Demetri understandable. My experience is that overhead of runtime-checks depends a lot on the type of code you write. Sometimes the overhead is more than 10x that of running without checks in my testing. $\endgroup$ Commented Nov 17, 2015 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.