Re: benchmark programs (Mark Tillotson)
9 Jul 1996 13:31:29 -0400

          From comp.compilers

Related articles
benchmark programs (1996-07-03)
Re: benchmark programs (1996-07-05)
Re: benchmark programs (1996-07-07)
Re: benchmark programs (1996-07-09)
| List of all articles for this month |

From: (Mark Tillotson)
Newsgroups: comp.compilers
Date: 9 Jul 1996 13:31:29 -0400
Organization: Harlequin Limited, Cambridge, England
References: 96-07-033 96-07-050
Keywords: benchmarks, architecture (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.

[ | | +44 1954 785433 ]
[ personal homepage ]

Post a followup to this message

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