(818) 986-1436 (818) 986-1360 (FAX)

Copyright (c) 1992 by Nimble Computer Corporation

We show how to speed up the Boyer Benchmark by an order of magnitude (46 X faster than the Cray-1) on a Common Lisp system (80860-based OKIstation) using better programming techniques. The resulting program fits nicely within next generation on-chip caches and kills almost all potential parallelism, thus becoming worthless as a general-purpose Lisp benchmark.

Nevertheless, the Boyer benchmark is fatally flawed, primarily because the code given in [Gabriel85] is not nearly the best method to solve the problem, and hence any attempt to speed up the Gabriel version of the code speeds up an artificial problem.

We show that the standard technique of *memoizing*
[Bird80] reduces the number of conses to 1% of those in the standard code, and
with the additional technique of *hash consing* [Goto74], the total space
required by all consing is satisfied by a total of 2219 cons cells.

(defmacro assq (x y) `(assoc ,x ,y :test #'eq))

(defun falsep (x lst) (or (equal x '(f)) (member x lst :test #'equal))) (defun truep (x lst) (or (equal x '(t)) (member x lst :test #'equal)))

(defparameter *memo-table* (make-hash-table :test #'equal)) (defun rewrite (term) (cond ((atom term) term) ((gethash term *memo-table*)) (t (setf (gethash term *memo-table*) (rewrite-with-lemmas `(,(car term) ,@(rewrite-args (cdr term))) (get (car term) 'lemmas))))))

Hash consing builds up an expression recursively from atoms by use of
the `hcons` function, which is a true mathematical function in
the sense that given the same pair of arguments, the result is always
`eq`. Hash consing can be simulated in Common Lisp by using an
`equal` hash table, but such an implementation is at least an
order of magnitude less efficient than a direct implementation,
because the hash table never needs to recurse beyond the `car`
and `cdr` in order to determine equality, and the value is
always the key itself. As a result, the effectiveness of the hash
consing optimization of the Boyer benchmark is dependent upon the
efficiency of the `hcons` function.

Notice that hash consing saves both space and time. Space is saved, because a subtree is never duplicated in memory. Time is saved, because any(defparameter *cons-table* (make-hash-table :test #'equal)) (defparameter *a-cons-cell* (list nil)) ;holding area for spare cons. (defun hcons (x y) ;not very fast; only for illustration. (setf (car *a-cons-cell*) x (cdr *a-cons-cell*) y) ;don't cons yet. (let ((z (gethash *a-cons-cell* *cons-table*))) (or z (prog1 (setf (gethash *a-cons-cell* *cons-table*) *a-cons-cell*) (setq *a-cons-cell* (list nil)))))) ;do next cons here.

The effectiveness of hash consing for the Boyer benchmark can be seen by considering the result of(defparameter *memo-table* (make-hash-table :test #'eq))

(We note that Boyer himself achieves speedups of 2 orders of magnitude on rewriting, by using rule compilation techniques [Boyer86]; Peter Deutsch [Deutsch73] also utilized memoizing and hash consing for similar effect.)

The success of memoization shows that almost all of the parallel processes in the Multilisp implementation of Boyer [Osborne89] are performing identially the same computation, hence the Boyer benchmark is worthless for estimating parallelism in real (i.e., highly optimized) applications. In a sense, memoization is the most powerful of all parallel programming techniques, because one processor simulates the execution of many processes with a single execution!

Bird, R.S. "Tabulation Techniques for Recursive Programs". *ACM
Comp. Surv. 12*,4 (Dec. 1980),403-417.

Boyer, R. "Rewrite Rule Compilation". TR AI-194-86-P, M.C.C., Austin, TX, 1986.

Deutsch, L. Peter. "An Interactive Program Verifier". Xerox PARC TR CSL-73-1, 1973.

Ershov, A.P. "On Programming of Arithmetic Operations".
*Doklady, AN USSR 118*,3 (1958),427-430, transl. Friedman,
M.D., *CACM 1*,8 (Aug. 1958),3-6.

Gabriel, R.P. *Performance and Evaluation of Lisp Systems*. MIT
Press, Camb., MA, 1985.

Goto, Eiichi. "Monocopy and Associative Algorithms in Extended Lisp". TR. 74-03, U. Tokyo, 1974.

Keller, R.M., and Sleep, M.R. "Applicative Caching". *ACM
TOPLAS 8*,1 (Jan. 1986),88-108.

Osborne, R.B. *Speculative Computation in Multilisp*.
MIT/LCS/TR-464, Dec. 1989.

Moon, D.A. "Garbage Collection in a Large Lisp System". *ACM Lisp
& Funct. Prog. Conf.*, Aug., 1984.

Steele, Guy L. *Common Lisp, The Language; 2nd Ed*. Digital
Press, Bedford, MA, 1990,1029p.