[bpt/guile.git] / gc-benchmarks / larceny / README

Source Code for Selected GC Benchmarks

These benchmarks are derived from the benchmarks that Lars Hansen used for
his thesis on Older-first garbage collection in practice . That thesis
contains storage profiles and detailed discussion for most of these
benchmarks.

Portability

Apart from a run-benchmark procedure, most of these benchmarks are intended
to run in any R5RS-conforming implementation of Scheme. (The softscheme
benchmark is an exception.) Please report any portability problems that you
encounter.

To find the main entry point(s) of a benchmark, search for calls to
run-benchmark, which calculates and reports the run time and any other
relevant statistics. The run-benchmark procedure is
implementation-dependent; see run-benchmark.chez for an example of how to
write it.

GC Benchmarks

To obtain a gzip'ed tar file containing source code for all of the
benchmarks described below, click here .

dummy
     Description: A null benchmark for testing the implementation-specific
     run-benchmark procedure.
dynamic
     Description: Fritz Henglein's algorithm for dynamic type inference.
     Three inputs are available for this benchmark. In increasing order of
     size, they are:
       1. dynamic.sch, the code for the benchmark itself
       2. dynamic-input-small.sch, which is macro-expanded code for the
          Twobit compiler
       3. dynamic-input-large.sch, which is macro-expanded code for the
          Twobit compiler and SPARC assembler.
earley
     Description: Earley's context-free parsing algorithm, as implemented by
     Marc Feeley, given a simple ambiguous grammar, generating all the parse
     trees for a short input.
gcbench
     Description: A synthetic benchmark originally written in Java by John
     Ellis, Pete Kovac, and Hans Boehm.
graphs
     Description: Enumeration of directed graphs, possibly written by Jim
     Miller. Makes heavy use of higher-order procedures.
lattice
     Description: Enumeration of lattices of monotone maps between lattices,
     obtained from Andrew Wright, possibly written by Wright or Jim Miller.
nboyer
     Description: Bob Boyer's theorem proving benchmark, with a scaling
     parameter suggested by Boyer, some bug fixes noted by Henry Baker and
     ourselves, and rewritten to use a more reasonable representation for
     the database (with constant-time lookups) instead of property lists
     (which gave linear-time lookups for the most widely distributed form of
     the boyer benchmark in Scheme).
nucleic2
     Description: Marc Feeley et al's Pseudoknot benchmark, revised to use
     R5RS macros instead of implementation-dependent macro systems.
perm
     Description: Zaks's algorithm for generating a list of permutations.
     This is a diabolical garbage collection benchmark with four parameters
     M, N, K, and L. The MpermNKL benchmark allocates a queue of size K and
     then performs M iterations of the following operation: Fill the queue
     with individually computed copies of all permutations of a list of size
     N, and then remove the oldest L copies from the queue. At the end of
     each iteration, the oldest L/K of the live storage becomes garbage, and
     object lifetimes are distributed uniformly between two volumes that
     depend upon N, K, and L.
sboyer
     Description: This is the nboyer benchmark with a small but effective
     tweak: shared consing as implemented by Henry Baker.
softscheme
     Description: Andrew's Wright's soft type inference for Scheme. This
     software is covered by the GNU GENERAL PUBLIC LICENSE. This benchmark
     is nonportable because it uses a low-level syntax definition to define
     a non-hygienic defmacro construct. Requires an input file; the inputs
     used with the dynamic and twobit benchmarks should be suitable.
twobit
     Description: A portable version of the Twobit Scheme compiler and
     Larceny's SPARC assembler, written by Will Clinger and Lars Hansen. Two
     input files are provided:
       1. twobit-input-short.sch, the nucleic2 benchmark stripped of
          implementation-specific alternatives to its R4RS macros
       2. twobit.sch, the twobit benchmark itself
twobit-smaller.sch
     Description: The twobit benchmark without the SPARC assembler.

----------------------------------------------------------------------------

Last updated 4 April 2001.
Commit	Line	Data
c1d1d824 LC	1	Source Code for Selected GC Benchmarks
	2
	3	These benchmarks are derived from the benchmarks that Lars Hansen used for
	4	his thesis on Older-first garbage collection in practice . That thesis
	5	contains storage profiles and detailed discussion for most of these
	6	benchmarks.
	7
	8	Portability
	9
	10	Apart from a run-benchmark procedure, most of these benchmarks are intended
	11	to run in any R5RS-conforming implementation of Scheme. (The softscheme
	12	benchmark is an exception.) Please report any portability problems that you
	13	encounter.
	14
	15	To find the main entry point(s) of a benchmark, search for calls to
	16	run-benchmark, which calculates and reports the run time and any other
	17	relevant statistics. The run-benchmark procedure is
	18	implementation-dependent; see run-benchmark.chez for an example of how to
	19	write it.
	20
	21	GC Benchmarks
	22
	23	To obtain a gzip'ed tar file containing source code for all of the
	24	benchmarks described below, click here .
	25
	26	dummy
	27	Description: A null benchmark for testing the implementation-specific
	28	run-benchmark procedure.
	29	dynamic
	30	Description: Fritz Henglein's algorithm for dynamic type inference.
	31	Three inputs are available for this benchmark. In increasing order of
	32	size, they are:
	33	1. dynamic.sch, the code for the benchmark itself
	34	2. dynamic-input-small.sch, which is macro-expanded code for the
	35	Twobit compiler
	36	3. dynamic-input-large.sch, which is macro-expanded code for the
	37	Twobit compiler and SPARC assembler.
	38	earley
	39	Description: Earley's context-free parsing algorithm, as implemented by
	40	Marc Feeley, given a simple ambiguous grammar, generating all the parse
	41	trees for a short input.
	42	gcbench
	43	Description: A synthetic benchmark originally written in Java by John
	44	Ellis, Pete Kovac, and Hans Boehm.
	45	graphs
	46	Description: Enumeration of directed graphs, possibly written by Jim
	47	Miller. Makes heavy use of higher-order procedures.
	48	lattice
	49	Description: Enumeration of lattices of monotone maps between lattices,
	50	obtained from Andrew Wright, possibly written by Wright or Jim Miller.
	51	nboyer
	52	Description: Bob Boyer's theorem proving benchmark, with a scaling
	53	parameter suggested by Boyer, some bug fixes noted by Henry Baker and
	54	ourselves, and rewritten to use a more reasonable representation for
	55	the database (with constant-time lookups) instead of property lists
	56	(which gave linear-time lookups for the most widely distributed form of
	57	the boyer benchmark in Scheme).
	58	nucleic2
	59	Description: Marc Feeley et al's Pseudoknot benchmark, revised to use
	60	R5RS macros instead of implementation-dependent macro systems.
	61	perm
	62	Description: Zaks's algorithm for generating a list of permutations.
	63	This is a diabolical garbage collection benchmark with four parameters
	64	M, N, K, and L. The MpermNKL benchmark allocates a queue of size K and
65	then performs M iterations of the following operation: Fill the queue
66	with individually computed copies of all permutations of a list of size
67	N, and then remove the oldest L copies from the queue. At the end of
68	each iteration, the oldest L/K of the live storage becomes garbage, and
69	object lifetimes are distributed uniformly between two volumes that
70	depend upon N, K, and L.
71	sboyer
72	Description: This is the nboyer benchmark with a small but effective
73	tweak: shared consing as implemented by Henry Baker.
74	softscheme
75	Description: Andrew's Wright's soft type inference for Scheme. This
76	software is covered by the GNU GENERAL PUBLIC LICENSE. This benchmark
77	is nonportable because it uses a low-level syntax definition to define
78	a non-hygienic defmacro construct. Requires an input file; the inputs
79	used with the dynamic and twobit benchmarks should be suitable.
80	twobit
81	Description: A portable version of the Twobit Scheme compiler and
82	Larceny's SPARC assembler, written by Will Clinger and Lars Hansen. Two
83	input files are provided:
84	1. twobit-input-short.sch, the nucleic2 benchmark stripped of
85	implementation-specific alternatives to its R4RS macros
86	2. twobit.sch, the twobit benchmark itself
87	twobit-smaller.sch
88	Description: The twobit benchmark without the SPARC assembler.
89
90	----------------------------------------------------------------------------
91
92	Last updated 4 April 2001.