Description of Benchmarks

Note: Our educated guesses concerning the reasons for a particular system's performance appear within [square brackets].

Microbenchmarks: floating point arithmetic

sumfp

Sums the integers from 0 to 10000, 10000 iterations. A test of floating point arithmetic. Uses essentially the same code as the `sum` benchmark. [In Larceny, all floating point calculations are done using generic arithmetic.]

fibfp

Calculation of the 25th Fibonacci number using inexact numbers, 50 iterations. A test of floating point arithmetic. Uses essentially the same code as the `fib` benchmark.

Microbenchmarks: calls, closures, continuations

sum

Sums the integers from 0 to 10000, 10000 iterations.

fib

Doubly recursive computation of the 25th fibonacci number (75025), using `(< n 2)` to terminate the recursion. [Register windows should perform well on this benchmark, but gcc may squander part of this advantage by allocating a register window even for the base case.]

tak

A triply recursive integer function related to the Takeuchi function, a Gabriel benchmark, 1000 iterations. A test of non-tail calls and arithmetic. Historical note: The Symbolics 3600 performed 1 iteration of this benchmark in 0.43 seconds using generic arithmetic, which is about 65 times as slow as a Sun Ultra 1.

cpstak

The `tak` benchmark in continuation-passing style, 300 iterations. A test of closure creation. [Improperly tail recursive implementations convert this benchmark's tail recursion into deep recursion, which may exceed limits on the size of a control stack.]

ctak

The `tak` benchmark in continuation-capturing style, 30 iterations. A test of `call-with-current-continuation`. [Larceny's code for `call-with-current-continuation` is now written in C, and most of its time on this benchmark is spent crossing the Scheme/C barrier.]

Microbenchmarks: lists

takl

The `tak` benchmark using lists to represent integers, a Gabriel benchmark, 200 iterations. This benchmark contains a peculiar boolean expression for which some compilers generate very poor code:
```    (define (shorterp x y)
(and (not (null? y))
(or (null? x)
(shorterp (cdr x)
(cdr y)))))
```
Compare with the `ntakl` benchmark.

ntakl

A version of the `takl` benchmark in which the peculiar boolean expression has been rewritten to make it less confusing for most people and for some compilers:
```    (define (shorterp x y)
(cond ((null? y) #f)
((null? x) #t)
(else
(shorterp (cdr x) (cdr y)))))
```
The rewritten expression is logically equivalent to the original. [The C versions of the `takl` and `ntakl` benchmarks make no attempt to reclaim heap storage, which gives C an advantage over garbage-collected languages. This advantage disappears in benchmarks that allocate large amounts of heap storage, such as `diviter`, `divrec`, `gcbench`, and `perm9`.]

dderiv

Table-driven symbolic differentiation, a Gabriel benchmark, 800000 iterations. Uses association lists instead of the original benchmark's property lists.

deriv

Symbolic differentiation, a Gabriel benchmark, 800000 iterations.

destruc

Destructive list operations, a Gabriel benchmark, 300 iterations.

diviter

Divides 200 by 2 using lists as a unary notation for integers, a Gabriel benchmark, 400000 iterations. This benchmark tests `null?`, `cons`, `car`, `cdr`, and little else. [This benchmark allocates 320 megabytes of heap storage, so the C version can't get by without deallocating storage. The C code for this benchmark performs node-at-a-time deallocation using either `free` or a custom deallocator. On our test machine, the standard library version of `free` is very slow for this benchmark, and even the custom deallocator can't reclaim storage quite as fast as a generational garbage collector. Compare this benchmark with `perm9`, for which a custom node-at-a-time deallocator outperforms generational garbage collection.]

divrec

This benchmark is the same as idiv2 except it uses deep recursion instead of iteration. [Implementations that use the SPARC's register windows to implement recursion will perform poorly on this benchmark. That is why `gcc` performs so poorly even with the custom storage allocator.]

browse

Browsing a data base, a Gabriel benchmark, 600 iterations. [May be a test of `string->symbol` and/or `symbol->string`.]

Larger benchmarks: floating point

fft

Fast Fourier Transform, a Gabriel benchmark, 2000 iterations. A test of floating point arithmetic. (I haven't yet checked to see whether it has the same bugs as the original Gabriel benchmark.)

mbrot

Generation of a Mandelbrot set, 30 iterations. A test of floating point arithmetic.

nucleic

Determination of a nucleic acid's spatial structure, 10 iterations. A test of floating point arithmetic, and a real program.

pnpoly

Testing to see whether a point is contained within a 2-dimensional polygon, 10000 iterations. A test of floating point arithmetic.

ray

Ray tracing a simple scene, 10 iterations. A test of floating point arithmetic. This program is translated from the Common Lisp code in Example 9.8 of Paul Graham's book on ANSI Common Lisp.

simplex

Simplex algorithm, 60000 iterations. A test of floating point arithmetic, and a real program.

Larger benchmarks: puzzles

puzzle

Combinatorial search of a state space, a Gabriel benchmark, 100 iterations. A test of arrays and classical compiler optimizations. This benchmark was originally written in Pascal by Forrest Baskett.

triangl

Another combinatorial search similar to `puzzle`, a Gabriel benchmark, 10 iterations.

Larger benchmarks: miscellaneous

conform

A type checker written by Jim Miller, 20 iterations.

dynamic

Dynamic type inference, self-applied, 10 iterations. Written by Fritz Henglein. A real program.

earley

Earley's parsing algorithm, parsing a 9-symbol input according to one of the simplest ambiguous grammars, 150 iterations. A real program, applied to toy data.

graphs

This program was provided by Andrew Wright, but we don't know much about it, and would appreciate more information. This higher order program creates closures almost as often as it performs non-tail procedure calls.

lattice

Another program that was provided by Andrew Wright. This program may have been written by Jim Miller. It enumerates the order-preserving maps between finite lattices.

maze

Constructs a maze on a hexagonal grid, 2500 iterations. Written by Olin Shivers.

mazefun

Constructs a maze on a rectangular grid using purely functional style, 100 iterations. Written by Olin Shivers.

peval

Partial evaluation of Scheme code, 100 iterations. Written by Marc Feeley.

scheme

A Scheme interpreter evaluating a merge sort, 200 iterations. Written by Marc Feeley.

slatex

Scheme to LaTeX processor, 20 iterations. A test of file i/o and probably much else. Part of a real program written by Dorai Sitaram.

Larger benchmarks: variations on `boyer`

boyer

Bob Boyer's theorem proving benchmark, a Gabriel benchmark, 10 iterations. This benchmark uses association lists in place of the original benchmark's property lists. The `nboyer` benchmark is an updated version of this benchmark.

smlboyer

Translation into Scheme of a translation into Standard ML of a translation into Scheme of the Common Lisp code for the original `boyer` benchmark, 10 iterations. Thanks to Standard ML, the data structures are somewhat more convoluted than in the `boyer` benchmark, but aren't much better.

nboyer

An updated and exponentially scalable version of the `boyer` benchmark, 1 iteration on a problem of size 3. (The `boyer` and `smlboyer` benchmarks solve a problem of size 0.) This benchmark's data structures are considerably more appropriate than the data structures used in the `boyer` and `smlboyer` benchmarks. A test of lists, vectors, and garbage collection.

sboyer

A version of nboyer that has been tuned (by Henry Baker) to reduce storage allocation, making it less of a garbage collection benchmark and more of a compiler benchmark. Only 4 lines of code were changed, and another 7 lines of code were added.

Synthetic benchmarks: garbage collection

gcbench

This program was written to mimic the phase structure that has been conjectured for a class of application programs for which garbage collection may represent a significant fraction of the execution time. This benchmark warms up by allocating and then dropping a binary tree of height 18. Then it allocates a permanent tree of height 16 and a permanent array of 500000 floating point numbers. Then it allocates about 350 megabytes of tree storage in seven phases, allocating about 50 megabytes per phase. The first phase allocates 67648 trees of height 4, dropping each tree before allocating the next. The second phase allocates and drops 16512 trees of height 6, and so on to the last phase, which allocates 8 trees of height 16. Each phase is divided into two subphases. The first subphase allocates trees top-down using side effects, while the second subphase allocates trees bottom-up without using side effects. This benchmark was written in Java by John Ellis and Pete Kovac, modified by Hans Boehm, and translated into Scheme, Standard ML, C++, and C by William Clinger.

One glaring difference between this benchmark and typical application code is that none of the trees are traversed after they are constructed. [This puts C and C++ at a disadvantage, because languages that rely on explicit deallocation must traverse the trees to deallocate their storage.]

[Generational garbage collectors perform extremely well on the early phases of this benchmark, but are likely to perform worse than non-generational collectors on the last phase or two.]

perm9

Creates a list containing all 362880 permutations of a list of 9 integers, in grey code order, using Zaks's algorithm, 5 iterations. A test of storage allocation and garbage collection. At the end of each iteration, the oldest half of the live storage becomes garbage.

[This benchmark is particularly difficult for generational garbage collectors, since it violates their assumption that young objects have a shorter future life expectancy than older objects. Nevertheless the generational collectors used in Larceny and in Chez Scheme perform reasonably well.]

[This benchmark is also difficult for C, because the permutation lists share much of their substructure. To avoid freeing nodes more than once, the C version of this benchmark performs an extra pass over the lists to compute (biased negative) reference counts for each node:

```  for ( p = perms; p != 0; p = p->cdr ) {
for ( x = p->car; x != 0; x = x->cdr ) {
if ( x->num > 0 )
x->num = 0;
else --(x->num);
}
}
```
This extra pass can be omitted when using a storage allocator written especially for this benchmark instead of using `malloc` and `free`. With this custom allocator, the code generated by gcc runs almost 10 times as fast. The code shown above does not account for very much of this improvement; most of the improvement must be blamed on the library code for `free`.]

Last updated 6 July 1999.