Re: lisp performance was Re: problems with lisp

[Peter Seibel <address@hidden>]

Russ Ross <rgr22@cl.cam.ac.uk> writes:

> 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.)

So this is--to me--a case of the "not too bad" variety. Even if one
did write this version originally, the overall shape of the code isn't
going to change dramatically once one realizes that arrays are
probably a better data structure than lists (as they point out). Just
change the implementation of make-matrix and change the calls to NTH
to AREF and LENGH to ARRAY-DIMENSION.

If that's not enough, adding some declarations will probably help. And
maybe give add-matrix an additional optional argument to specify where
the result should be put (which would allow us to avoid allocating a
new) matrix for the result--we could destructively reuse one of the
arguments, for instance, if we (the caller) knew it wasn't going to be
needed after the call to add-matrix.

It is true that a programmer who wants to write efficient code in Lisp
will have to understand that these transformations are available and
why they are a good idea. But it doesn't seem that the Lisp programmer
needs to know much more than, say, a C programmer. It's just that the
C programmer *has* to know it to do *anything*.

>     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.

I agree with the need to have the assembly floating around one's
mind--eventually. To me the perfect language would be one where I
could express myself very naturally at a high-level and without having
to concern myself with how things get translated into assembly but
which then gives me the ability to add information to my program that
allows me to know what assembly it will be compiled into.

Common Lisp seems to come pretty close to this with its optional
declarations but it does still sometimes seems to be a bit of a black
art--just by observing code bumming threads on comp.lang.lisp is seems
that a certain amount of implementation specific (as in which
implementation of Common Lisp is being used) is required to get that
last little bit of efficiency: the guys who *really* know how the
various compilers work are obviously the best at figuring out how to
make it generate the right assembly. But even then, the kinds of
changes they seem to make (after getting the algorithm basically right
in terms of big-O kinds of issues, obviously) seem to mostly be in the
form of declarations.

The slightly disconcerting thing is that different implementations
sometimes need different declarations to get the same end result and
it sometimes seems to take wizard-level knowledge of a particular
implementation to understand why. OTOH, getting absolutely the most
efficient code in *any* language usually requires wizard-level
knowledge of something.

-Peter

-- 
Peter Seibel                                      peter@javamonkey.com

         Lisp is the red pill. -- John Fraser, comp.lang.lisp