[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: lisp performance was Re: problems with lisp
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
[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.
> 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:
>>> 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,
>>> profiles.ps). I don't know if clisp or gcl have profilers however.
>>> Often a few relatively small changes can make a big difference.
>>> 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.
>> 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)])
>> [(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
>> and the compiled mzscheme code takes just over 4 seconds.
>> 3. The profiler in DrScheme suggests that the inner "loop", which is
>> a recursive function that is *mostly* tail recursive, consumes the
>> 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
>> Scheme has exact arithmetic and Ocaml needs a special 64bit int
>> 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
>> (And I have yet to understand all the details of the problem statement
>> the program.)
>> -- Matthias