The memory management component of SCM contains special features which optimize the allocation and garbage collection of environments.
The optimizations are based on certain facts and assumptions:
The SCM evaluator creates many environments with short lifetimes and these account of a large portion of the total number of objects allocated.
The general purpose allocator allocates objects from a freelist, and collects using a mark/sweep algorithm. Research into garbage collection suggests that such an allocator is sub-optimal for object populations containing a large portion of short-lived members and that allocation strategies involving a copying collector are more appropriate.
It is a property of SCM, reflected throughout the source code, that a simple copying collector can not be used as the general purpose memory manager: much code assumes that the run-time stack can be treated as a garbage collection root set using conservative garbage collection techniques, which are incompatible with objects that change location.
Nevertheless, it is possible to use a mostly-separate copying-collector, just for environments. Roughly speaking, cons pairs making up environments are initially allocated from a small heap that is collected by a precise copying collector. These objects must be handled specially for the collector to work. The (presumably) small number of these objects that survive one collection of the copying heap are copied to the general purpose heap, where they will later be collected by the mark/sweep collector. The remaining pairs are more rapidly collected than they would otherwise be and all of this collection is accomplished without having to mark or sweep any other segment of the heap.
Allocating cons pairs for environments from this special heap is a heuristic that approximates the (unachievable) goal:
allocate all short-lived objects from the copying-heap, at no extra cost in allocation time.
A separate heap (
ecache_v) is maintained for the copying
collector. Pairs are allocated from this heap in a stack-like fashion.
Objects in this heap may be protected from garbage collection by:
scm_estk) is used in place of the C run-time stack by the SCM evaluator to hold local variables which refer to the copying heap.
scm_egc_roots). If no object in the mark/sweep heap directly references an object from the copying heap, that object can be preserved by storing a direct reference to it in the copying-collector root set.
When the copying heap or root-set becomes full, the copying collector is invoked. All protected objects are copied to the mark-sweep heap. All references to those objects are updated. The copying collector root-set and heap are emptied.
References to pairs allocated specificly for environments are inaccessible to the Scheme procedures evaluated by SCM. These pairs are manipulated by only a small number of code fragments in the interpreter. To support copying collection, those code fragments (mostly in eval.c) have been modified to protect environments from garbage collection using the three rules listed above.
During a mark-sweep collection, the copying collector heap is marked and swept almost like any ordinary segment of the general purpose heap. The only difference is that pairs from the copying heap that become free during a sweep phase are not added to the freelist.
The environment cache is disabled by adding
to eval.c; all environment cells are then allocated from the
This work seems to build upon a considerable amount of previous work into garbage collection techniques about which a considerable amount of literature is available.