Tim Bradshaw  <tfb@tfeb.org> wrote:
+---------------
| Does anyone have any figures or pointers to references on how fast
| various Lisp systems can allocate ephemeral objects?
+---------------

Appel's book "Compiling with Continuations" has some analysis, and IIRC
also makes reference to some studies by Ungar concerning using a fixed
ephemeral-allocation area roughly the size of the secondary cache on
the machine. That is, rather than the classical "two semi-space" copying
collector (or the generational extension of it), there's a third, fixed
"nursery" space for "generation zero".

All allocation (at least of "small" objects) is done there with a simple
incrementing pointer, and when that space fills up a minor collection is
done that moves all the live data from the nursery into the current active
semi-space of gen#1 (with a more major GC only if/when needed), and you
start allocating again in the fixed nursery. This keeps the area where
furious allocation is going on "hot" in the (secondary) cache, rather
than striding through all of memory.

[Note that Baker's "Cheney on the MTA" ("Cons Should not Cons: II") uses
the C stack as exactly such a fixed nursery area, though with a higher
percentage of "wasted" space (for the unused C stack frames). There's
recently been a long thread in comp.lang.scheme about such things,
especially re the "Chicken" Scheme compiler, whose runtime uses CotMTA.]

Anyway, Appel claims that with typical secondary cache sizes, the amortized
cost of collecting the live data out of the nursery is close to zero...


-Rob

p.s. If you want more precise references, I'll try to dig them out.

-----
Rob Warnock, 31-2-510		rpw3@sgi.com
Network Engineering		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		PP-ASEL-IA
Mountain View, CA  94043