Re: lisp performance was Re: problems with lisp

[Ken Anderson <address@hidden>]

Actually, i think your Simple Lisp version did quite well if Matthias' Scheme numbers are representative of what Common Lisp results would be.  The Simple list version replaced longs with bignums thus probably accounting for much of the time difference.

k
At 11:24 PM 8/28/2003 +0100, Russ Ross wrote:
>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.