Re: lisp performance was Re: problems with lisp

[Matthias Felleisen <address@hidden>]

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