Re: lisp performance was Re: problems with lisp

[Russ Ross <address@hidden>]

On Mon, Sep 01, 2003 at 12:03:18PM -0700, Peter Seibel wrote:
> Do you have a more practical example. Something where the real
> "simple" version was not only too slow, but couldn't in fact be made
> effecient without fundamentally rewriting it? I'm sincerely curious
> because I've been thinking about this problem lately but don't have
> enough real-world Common Lisp experience under my belt to have a lot
> of good examples, one way or the other.

This may not quite fit the criteria, but I came across an
interesting passage this morning while reading Steele & Gabriel's
"The Evolution of Lisp".  I'll quote the relevant part:

    Lisp has proved itself concerned more with expressiveness than
    anything else.  We can see this more obliquely by observing that
    only a person well-versed with how a particular Lisp is
    implemented can write efficient programs.  Here is a perfectly
    nice piece of code:

    (defun make-matrix (n m)
      (let ((matrix ()))
        (dotimes (i n matrix)
          (push (make-list m) matrix))))

    (defun add-matrix (m1 m2)
      (let ((l1 (length m1))
            (l2 (length m2)))
        (let ((matrix (make-matrix l1 l2)))
          (dotimes (i l1 matrix)
            (dotimes (j l2)
              (setf (nth i (nth j matrix))
                    (+ (nth i (nth j m1))
                       (nth i (nth j m2)))))))))

    The expression to read and write a cell in a matrix looks
    perfectly harmless and fast as anything.  But it is slow,
    because nth takes time proportional to the value of its first
    argument, essentially CDRing down the list every time it is
    called.  (An experienced Lisp coder would iterate over the cells
    of a list rather than over numeric indices, or would use arrays
    instead of lists.)

    Here expressiveness has gone awry.  People tend to expect that
    operations in the language cost a small unit time, not something
    complicated to figure out.  But this expectation is false for a
    sufficiently expressive language.  When the primitives are at a
    sufficiently high level, there is enough wiggle room underneath
    to permit a choice of implementation strategies.  Lisp
    implementors continue to explore that space of strategies.
    Precisely because Lisp is so expressive, it can be very hard to
    write fast programs (though it is easy to write pretty or clear
    ones).

The authors indicate that expressivity makes efficiency difficult by
its very nature.  I'm not sure if I agree with this conclusion, but
it brings to mind the notion of "leaky abstractions":

http://www.joelonsoftware.com/articles/LeakyAbstractions.html

Which is summarized as:

    All non-trivial abstractions, to some degree, are leaky.

This seems to be particularly true in programming languages.  Nearly
all the abstractions languages give us can only be used effectively
(outside of toy examples) if we understand the plumbing underneath.
One of things that makes a good programmer good is that (s)he has
internalized the language, tools, and environment well enough to
make good decisions about them subconsciously and focus on the
particular problem at hand.  I've known very good theoreticians who
could never write good code because they didn't understand the lower
levels well enough.  Good hackers tend to get their feet wet with
many parts of the system, and even when they use something as
high level as Lisp they have assembly language floating around
somewhere in the back of their minds.

If it is true that we have to understand what is behind the
abstractions to use them effectively, then perhaps it is worth
admitting that in the design of the abstractions themselves so that
the efficiency considerations are clearer to the programmer and the
compiler both.  Even the Sufficiently Smart Compiler that Lisp seems
to require can be defeated by the Sufficiently Ignorant Programmer,
and that's not saying anything about the intelligence of the SIP.

- Russ