Re: Just how fast is LISP?

        [...] The fastest LCL has ever done relative to gcc is a factor of 2,
        often much worse. [...]


        This is hard to understand. If a Lisp program doesn't cons, use closures
        or any other fancy Lispisms, but just munges pointers and (heavily
        declared) fixnums with setq, what causes the degradation?


A potential killer that you may be missing is the GC write barrier. LCL
implements a generational GC, which is generally a win, but causes
assigning to pointer-valued locations (global variables, structure slots,
...) to become substantially more expensive (anywhere from 2x to >10x
worse, depending on how the write barrier is implemented.)


In generational GC systems it is quite likely to be less expensive to cons
a new object than to destructively modify an old one; this is totally
contrary to efficient memory allocation discipline in non-generational
implementations.


        I've compared LCL code from (disassemble 'foo) and gcc -S, and the answer
        seems to be mainly that the function call overhead of Lisp is terrible,
        [...] I'm guessing the reasons have to do with keyword and &rest
        parameters, garbage collection, symbol-function indirection, special
        bindings, etc.


The biggest function call overheads are:
  -- Allowing code objects to be garbage collected makes it more difficult to
        do direct jumps and to use hardware call instructions (return PCs must be
        tagged so that the garbage collector can recognize them.)
  -- Allowing for run-time function redefinition. As Barmar says, the cost of
        the control transfer can largely be finessed through sufficient
        implementation complexity, but there are other overheads in not knowing
        what function you are calling at the time you compile (or load) the call.
  -- Supporting multiple return values when the callee may not generate the
        same number of values that the caller is expecting.


        >and of course _everything_ in Lisp is a function call.


Well, not really. If your Lisp code is really doing more function calls
than your C code, then it is hardly surprising that it runs more slowly
--- but this should not be the case.


        [...] if speed is a concern, it often takes again as long as writing the
        program in CL to apply declarations, inlining, tricks, etc to get back to
        within a factor of 3 of the speed of a C program. This is a really
        annoying process.


Yes, this is a big problem. With most Lisps it is *possible* to tweak CL
programs so that they run within 50% of C. Unfortunately, the Lisp
compiler writer is probably the only person who knows how to do this.
Compilers can do more to communicate efficiency problems to programmers.
I believe that in my work on Python (the CMU CL compiler), I have shown
that tuning numeric&array CL code can be a lot easier than it currently
is.


    Robert A. MacLachlan (ram@cs.cmu.edu)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.