|benchmark programs email@example.com (1996-07-03)|
|Re: benchmark programs firstname.lastname@example.org (1996-07-05)|
|Re: benchmark programs email@example.com (1996-07-07)|
|Re: benchmark programs firstname.lastname@example.org (1996-07-09)|
|From:||email@example.com (Mark Tillotson)|
|Date:||9 Jul 1996 13:31:29 -0400|
|Organization:||Harlequin Limited, Cambridge, England|
firstname.lastname@example.org (Peach Microsystems) wrote
> Gabriel's "Performance & Evaluation of LISP Systems", early 80's, had LISP
> source for a number of benchmarks including multiple variants of a viciously
> recursive but otherwise trivial function called tak. At least one variant was
> deliberately designed to defeat cache.
> // omitting details I don't recall offhand
For the record:
(defun tak (x y z)
(if (<= x y)
(tak (tak (1- x) y z)
(tak (1- y) z x)
(tak (1- z) x y))))
(tak 18 12 6) => 7, and involves 63609 calls to tak (47707 of which
are leaf case - ie. x <= y) with a maximum stack depth of 18 frames.
The cache-defeating variant has 100 variants, and is slower by a factor
of about 5 on a Dec Alpha, according to a quick test of mine...
This benchmark certainly shows up the benefits in doing leaf-path
analysis, as 75% of calls take the short branch and don't need any
stack-building. Tail-recursion elimination also pays off.
[ email@example.com | http://www.harlequin.co.uk/ | +44 1954 785433 ]
[ personal homepage http://firstname.lastname@example.org/ ]
Return to the
Search the comp.compilers archives again.