Re: lisp performance was Re: problems with lisp

[Matthias Felleisen <address@hidden>]

On Monday, August 25, 2003, at 01:06 PM, Ken Anderson wrote:

> You can find several papers on Lisp performance her:
> http://openmap.bbn.com/~kanderso/performance/
>
> I'd be intersted in looking at your programs if you'd like.
>
> Unfortunately, Common Lisp does not require tail call optimization,  
> though things like tail calls are usually optimized.  You'd see stack  
> overflows if this was an issue.
>
> First, I write Lisp straightforwardly.  This version is often plenty  
> fast enough.  When its not, i profile (see for example,  
> http://openmap.bbn.com/~kanderso/performance/postscript/courage-in- 
> profiles.ps).  I don't know if clisp or gcl have profilers however.   
> Often a few relatively small changes can make a big difference.  These  
> may or may not require type declarations.
>
> Going from OCaml to Lisp you may lose information that OCaml takes  
> advantage of.
>
> I agree that pattern maching makes the code cleaner.
>
> k

I had asked Russ for the code on Sat and translated it into MzScheme.
A couple of observations:

1. The benefits from pattern matching were minimal. I am not revealing
a state secret when I show an example here:

     match ((and64 x edgex), (and64 x edge_x), (and64 x edgey)) with
       | (false, _, _)           -> shift a (shift_left x 2)
       | (true, false, false)    -> shift a (shift_left x 3)
       | (true, true, false)     -> shift a (shift_left x 5)
       | _                       -> a

goes to

                  (let ( [u (and64 x edgex)] [v (and64 x edge_x)] [w  
(and64 x edgey)])
                       (cond
			[(not u)                            (shift a (shift_left x 2))]
			[(and u (not v) (not w)) (shift a (shift_left x 3))]
			[(and u v (not w))          (shift a (shift_left x 5))]
			[else                               a])))])

2. On my machine, the Ocaml code takes around 1.5 seconds to find a  
solution,
and the compiled mzscheme code takes just over 4 seconds.

3. The profiler in DrScheme suggests that the inner "loop", which is  
really
a recursive function that is *mostly* tail recursive, consumes the bulk  
of the
computation time. Tail call optimization rocks. It *truly* makes the  
code clear.

4. I didn't exploit any Scheme insights during the translation, except  
that
Scheme has exact arithmetic and Ocaml needs a special 64bit int module.
To fake this, I actually defined these functions. I didn't use macros  
to in-line
them, like they would, so there are probably another few 1/10 second.
Still, the overall length of the program increased by barely a few  
lines.

(And I have yet to understand all the details of the problem statement  
and
the program.)

-- Matthias