Ji-Yong D. Chung <virtualcyber@erols.com> wrote:
+---------------
| I have been creating [environments] on the heap, but I am beginning
| to see that it is rather inefficient. I am using a copying collector
| which can only increment its internal memory pointer when it allocates
| memory. Since the copying collector can only move the pointer forward,
| soon or later, it must reach a point where the allocated memory is not
| in L2 (assuming the heap is larger than L2 cache) and cause a cache
| miss -- which is what I am trying to prevent.
+---------------
So that point is precisely where you want to do a "minor" collection,
evict all the live objects from the "nursery" allocation area (the part
of memory in the L2 cache), and start allocating again in the *same* place.
That will keep your cache "hot" and give you much of the same performance
as a stack. [Though let's not start a flamewar over how *close* to "same" --
opinions on that are heated.]
You don't have to convert to a full-blown multi-generation generational
collector to make this worthwhile. You can have a simple "two-space"
collector (traditional "to" and "from" spaces) as the main heap, and
just front it with a third, fixed-location "nursery" space for initial
allocation (or what you hope will *mostly* be ephemeral objects).
And while you *could* go to the trouble of constructing formal "remembered
sets" (the portions of the "to" space that have been mutated to point to
objects in the ephemeral space), you may find it simpler to treat the
entire current "to" space (that is, the semispace you're currently using)
as also being "roots" for the minor collection (in addition to the Scheme
VM registers & globals). That is, when the (fixed) nursery space fills up,
you scan the normal roots *and* the current "to" space for pointers to
objects in the nursery space (which are thereby known to be "live"), and
copy them to the current "to" space.
[If *that* fills up, trigger a normal full collection. That is, flip the
"from" and "to" spaces as usual, use *only* the Scheme VM registers & globals
as roots, and copy live objects from *both* the "from" and "nursery" spaces
into the (new) "to".]
After such a collection (minor or full), the nursery space will be empty
again, and you can reset the allocation pointer to its beginning.
+---------------
| If I were creating these environments on the stack, I would be creating
| and destroying environments which are allocated on memory cells whose
| addresses that are very close to each other -- basically, this will
| reduce/eliminate cache misses.
+---------------
Note that exactly the same thing is true with the above-described
"three-space" allocator.
-Rob
-----
Rob Warnock, 31-2-510 rpw3@sgi.com
SGI Network Engineering <URL:http://reality.sgi.com/rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA