Re: lisp performance was Re: problems with lisp

[Russ Ross <address@hidden>]

In this particular case, type declarations are not allowed by the
contest rules:

http://www.ravenbrook.com/doc/2003/05/28/contest/

Using a bytecode lisp interpreter (clisp) and a compiler that isn't
reputed to be all that great (gcl) undoubtedly affected the results.
The bytecode version of the OCaml code takes about 4x longer to run
than the native code version.

I don't wish to drag out the discussion of lisp performance, as that
was only one part of the point I was trying to make originally.
Matthias kindly volunteered to do the PLT Scheme comparison which
provided some interesting results.  I appreciate those who have
offered to help me tune my lisp code, but that example was just
meant to be an anecdote comparing the efforts of a relative novice
in both languages using the main idioms common to those languages
(heavy recursion over list structures).

Getting a significant performance boost through heavy tuning would
just support my complaint that the natural and simple way to do
something often comes with a performance penalty.  I think a useful
design goal for languages would be to make sure that the clean,
simple way of coding a given algorithm is also the efficient way.  I
try to follow the practice of writing code in a style that is simple
and obvious so that I can easily convince myself that it is correct.
Then if performance is a problem I profile to find the bottlenecks
and optimize those.  Usually that means an algorithmic change, but
sometimes it just means recoding a few functions to equivalent
versions that map better to efficient code.  In functional
languages, converting a function to be tail recursive is a good
example.  It would be great if a compiler was smart enough (or a
language design in a way that made it easier to do mechanically) to
automatically figure out when it can convert a function to be tail
recursive by passing an accumulator or something like that.

Wouldn't it be great if we didn't have to use reverse-append or
reverse-map to get tail recursion because the compiler could recognize
the pattern and optimize this into a tail recursive function?
Perhaps the runtime could be smart enough to notice that you were
using map on a really long list (with no dependency between
elements) and convert it to (reverse (reverse-map)) for you?  I'd
love to never have to write something like:

(defun double (lst)
  (labels ((f (n accum)
           (if (endp n)
               accum
               (f (cdr n) (cons (* 2 (car n)) accum)))))
        (reverse (f lst nil))))

when what I really mean is:

(defun double (lst)
  (if (endp lst)
      nil
      (cons (* 2 (car lst)) (double (cdr lst)))))

just for the sake of efficiency.  Lisp isn't the only one guilty of
this (OCaml is the same, as are almost all languages) but this is
just an example to illustrate a point: modern languages let us be
artists, abstractors, and aestheticians some of the time, but they
still force us to be human compilers all too often.  Ideally, a
language should provide enough information for the compiler while
still leaving the programmer free to ignore what's going on under
the hood.  Tail call optimization is a huge success according to
this goal.  Pattern matching and type inference are a couple more
that come to mind--they give the compiler room to optimize things
while staying out of the programmer's way.  Let me hasten to point
out that type inference doesn't necessarily imply strong typing lest
I stoke the wrong fire here.

I don't think this is just about lisp, but Common Lisp seems to be
particularly bad that way (many would-be optimizations break with
some corner case or because it was assumed that eventually hardware
would be helping out in ways that it isn't today--it's almost like
Common Lisp was designed to make writing a compiler difficult).

That's what I meant when I talked about Efficient Lisp vs. Simple
Lisp.  I wasn't looking for help writing Efficient Lisp, I was
wishing it would marry itself to Simple Lisp.  The OCaml example was
just that--an example giving a single data point.

- Russ

p.s. No, I'm not looking for better ways to implement/optimize the
double function  ;-)


On Thu, Aug 28, 2003 at 04:54:45PM -0400, Matthias Felleisen wrote:
> I didn't need any of this in PLT Scheme. I didn't even need to mask
> out "bad" bits when I did shifts, so I doubt that this is a critical 
> issue.
> [I use bignums of course but I am saying that this doesn't seem to
> be the source of the factor of 10 for CL.]  -- Matthias
> 
> 
> 
> On Thursday, August 28, 2003, at 02:58 PM, Ken Anderson wrote:
> 
> >If you're bit shifting longs you'll need to add type declarations to a 
> >Common Lisp version to reduce bignum consing.