importance of high-level optimization and debugging (was nausea)

[Rob_MacLachlan@LISP-PMAX2.SLISP.CS.CMU.EDU]

    I'm just not convinced that native code optimiation for a Lisp is
    likely to produce results that are *better* than what the C compiler
    does on a Unix system for simple things like function call and
    assignment to a global.

You are almost certainly right within +-10%.

    Nothing against Lisp, but rather just a comment on the sheer numbers of
    clever people interested in optimizing C compilers.

Yes, so many companies have poured so much money into it, that it is virtually
impossible to make them much better.  At the last SIGPLAN conference, everyone
was talking like "my scheduler is 5-7% better", and often "sometimes 7% better,
sometimes 5% worse."  They're trying so hard, that I believe that I can read
their papers and get 80% of the performance for 20% of the work.  

In mainstream compilers, the only real challenges left are compiling for new
hardware with more parallelism (low or high level.)

    So, to continue the line of thought, to the extent that AKCL manages to
    turn a Lisp operation (e.g., a function call, setq, arithmetic or logical
    operation), into a corresponding C operation, one would not expect to beat
    AKCL with a native code Lisp.

Assuming that Lisp continues to be a widely-used language, there will be a
need for Lisp-to-C translators, since translating to C can solve several
related Lisp problems (often lumped as the "delivery problem"):
 -- C low-level optimization gets the last N% CPU performance.
 -- Link-level integration with C libraries.
 -- Space reduction through selective linking with the Lisp library.

However, translating to C only eliminates the compiler's back-end; it doesn't
eliminate the utility of doing transformations at the level of Lisp semantics.
I am much more interested in high-level optimization, which is why I'm
concentrating on the problems like:
 -- Making it easier to write programs that work and are acceptably efficient.
 -- Figuring out how to convert high-level Lisp programs into low-level (C
    equivalent code.)
 -- Figuring out how to reasonably efficiently implement complex Lisp
    features with no obvious C equivalent (e.g. CLOS generic functions.)

To bring this back to the issue of why I say that some programs will be much
slower in KCL, I claim that:
    Many interesting and useful Common Lisp programs require appreciable
    semantic analysis and transformation to convert them to C-equivalent
    programs, or

    Without high-level optimization, many programs run very, very slowly.

To make it clear, I don't expect that there are a lot of these
high-optimization Lisp programs currently lying about, but they can easily be
written, and more importantly, they can be written *more easily*.  In other
words, the benefits of high-level optimization come only when you write
programs knowing that this optimization will be done.

If you read the "Advanced Compiler" chapter in the CMU CL user manual, you
can get an idea of some of the changes in Lisp programming style that I am
advocating.

There would definitely be a performance improvement if you put a
state-of-the-art C compiler back-end on CMU CL.  In fact, Tim Moore at Utah
looked into adapting the GCC backend.  However, there are number of nasty
problems:
 -- GC discipline.  Without substantial backend changes, you are forced to use
    a conservative GC.  (There are no solid results on the importance of this,
    but I think it's important.)
 -- Propagating Lisp debug info through a C backend.
 -- Incremental compilation.

Now, none of these problems are insuperable, and AKCL has some sort of solution
for all of them.  But since I think that good storage management, debuggability
and incremental development are more important that last N% of speed, it was a
reasonable decision for us to implement our own mediocre backend.


As to your question:

    Can one redefine functions wired inside a block?  One couldn't in
    Interlisp-10.

Can't redefine (though it is harmless).  Can trace (real soon now) since we
are switching to a breakpoint-driven tracer.  But it is going to be very
difficult for KCL to win the debuggable-and-fast contest with CMU CL.

In fact, Python is in a very exclusive league for compilers in any language,
being a compiler that supports source-level debugging of optimized code.  The
speed penalty for allowing source-level debugging is so small as to be
generally ignorable (although (optimize (speed 3)) does sacrifice some
debuggability for that last N%.)  This is easier to do for Lisp than C, because
Lisp has well-defined and relatively sparse locations where the debugger can be
entered.

And Python's approach to type checking is very different, being:
 -- Precise (check for exact declared type)
 -- Eager (check as soon as possible, instead of delaying until the value is
    used.)
 -- Efficient.  Full type safety generally gives a 2x or less slowdown (as
    Bill's first round of benchmark results showed.)

So, Python is solving different problems than AKCL, and I think that the
solutions in CMU CL will be very interesting to many Lisp programmers.

  Rob

p.s. 
    I would be glad to discuss adapting Python's semantic analysis and
    diagnostic capabilities to the problem of Lisp-to-C translation.