[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: lisp performance was Re: problems with lisp
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. 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.
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
(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))]
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 bulk
computation time. Tail call optimization rocks. It *truly* makes the
4. I didn't exploit any Scheme insights during the translation, except
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
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