Re: lisp performance was Re: problems with lisp

[Ken Anderson <address@hidden>]

If you're bit shifting longs you'll need to add type declarations to a Common Lisp version to reduce bignum consing.  

k

At 09:56 PM 8/25/2003 -0400, Matthias Felleisen wrote:

>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