Erik Naggum  <erik@naggum.no> wrote:
+---------------
|   cache hit rates for stacks (including temporaries in call frames) are
|   typically >99.9%.  to get that good hit rates for a heap allocation
|   scheme that walks over fresh memory while allocating and causes much
|   scattering of allocated call frames unless the heap is optimized like a
|   stack...
+---------------

IIRC from my reading of the GC literature, Ungar introduced the notion
of a fixed "nursery" area [that may not have been his term for it] for
allocation in generational copying collectors, with the size chosen to
be the size of the secondary data cache (or slightly smaller). When you
fill up the nursery area, you do a minor collection, copying all of the
live data out into the main heap, then immediately reusing the *same*
nursery area for subsequent allocation. This causes the nursery area
to stay "hot" in the cache, much like a stack would.

Using such techniques, people [Appel, in particular] have claimed that
heap allocation can be as cheap as stack allocation, on average. (Yes,
I know others have disputed that as well.)


-Rob

p.s. Conversely, Henry Baker's "CONS Should Not CONS Its Arguments, Part II:
Cheney on the M.T.A." <URL:ftp://ftp.netcom.com/pub/hb/hbaker/CheneyMTA.html>
shows how to use the normal C stack *as* the nursery area of a generational
collector -- by writing in a CPS style that "never returns", allocating in
normal C stack-local variables, and limiting stack growth by periodically
combining a "longjmp" to trim the stack with a minor garbage collection.
Again, you get the same result: a copying collector that keeps its
generation-zero allocation area hot in the cache.

-----
Rob Warnock, 41L-955		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		PP-ASEL-IA
Mountain View, CA  94043