Re: benchmark programs

peach@entrenet.com (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)
              z
        (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.


__Mark
[ markt@harlequin.co.uk | http://www.harlequin.co.uk/ | +44 1954 785433 ]
[ personal homepage http://www.juggling.org/~markt@harlequin.co.uk/ ]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.