%\documentstyle[times,12pt,psfig]{cmu-art}
%\begin{document}

\section{CMU Common Lisp}

This section describes work in progress for the new port of CMU Common
Lisp to the DECStation~3100 using MacLachlan's Python compiler.  This
section assumes only a minimal knowledge of the new object format
\cite{cmu-new-object} used in this port.

%\subsection{Object Format}
%Object format stuff is {\it really sucky} so I may leave it out.  It's
%in a different file for now and the line to include it is commented
%out.
%\input{object-format}

\subsection{Stop-and-Copy Heap Organization}
\label{sec:old-heap}
The current organization of the heap in the new port of CMU Common
Lisp consists of four distinct spaces:
\begin{itemize}
\item Read-Only Space

Read-only space is occupied by objects which are permanent, are never
moved, are never reclaimed, and are never modified.  Further, objects
in read-only space may refer only to objects in read-only space or in
static space.  This makes it unnecessary for the garbage collector to
scavenge read-only space.

\item Static Space

Static space is occupied by objects which are permanent, are never
moved, and are never reclaimed.  They never need to be transported by
the garbage collector.

\item Dynamic-0 Space
\item Dynamic-1 Space

Dynamic-0 space and Dynamic-1 space are the active areas of the heap.
At any given time, one of these spaces acts as newspace and the other
as oldspace.
\end{itemize}

\subsection{Fast Allocation}
\label{sec:fast-allocation}
Object allocation in the new port is very fast.  One machine register,
ALLOC, always contains the free pointer for the current dynamic space.
By simply incrementing this register, allocation may be performed
inline.  Currently, most fixed-length objects are allocated and
initialized inline by the compiler.  For example, the function {\tt
CONS} is always coded inline and it only takes 10 MIPS R2000
instructions to allocate {\it and} initialize the new cell from
arguments in registers.  The code sequence for {\tt CONS} is shown in
Figure~\ref{fig:cons-vop}; it will be explained in more detail later.

\begin{figure}
\begin{center}
{\footnotesize
\begin{verbatim}
        and     $FLAGS, $FLAGS, 65533        ; Clear the INTERRUPTED flag.
        or      $FLAGS, $FLAGS, 1            ; Set the ATOMIC flag.
        addu    $A0, $ALLOC, 3               ; Save the pointer to the CONS.
                                             ; (Add 3 to give it a list tag.)
        addu    $ALLOC, $ALLOC, 8            ; Allocate the CONS (8 bytes).
        sw      $LEXENV, $A0, -3             ; Store the CAR.
        sw      $CNAME, $A0, 1               ; Store the CDR.
        and     $FLAGS, $FLAGS, 65534        ; Clear the ATOMIC flag.
        and     $NL0, $FLAGS, 2              ; Check the INTERRUPTED flag.
        beq     $NL0, $ZERO, L0              ; If not set, go on.
        nop
        break   9                            ; Cause a trap
L0:
\end{verbatim}
}
\end{center}
\caption{Code Sequence for {\tt CONS}}
\label{fig:cons-vop}
\end{figure}

Allocation of some variable-length objects is also performed inline
when the compiler has enough information.  In particular, allocation
and initialization of lists using {\tt LIST} or {\tt LIST*} for a
known number of arguments is coded inline with a number of
instructions proportional to the number of arguments.  The allocation
of vectors and arrays, however, is not coded inline directly; rather,
for a number of common cases, an inline call to one of three small
assembly routines performs the allocation.  The other less common
cases of vector and array allocation require the intervention of
Lisp-level code to first select an appropriate representation.

\subsubsection{Implementing a Garbage Collection Threshold}
Heap allocation beyond a certain point must force a garbage collection
to prevent the system from running out of memory.  This point is
called the garbage collection threshold.  A problem with the code
sequence for {\tt CONS} shown in Figure~\ref{fig:cons-vop} is that it
never checks to see if the allocation pointer has exceeded the garbage
collection threshold.

Fortunately, this is not necessary as it would require more
instructions and slow down the allocation sequence.  To implement a
garbage collection threshold, we use virtual memory primitives (as
exported by the MACH operating system \cite{mach-kernel}) to make the
virtual memory page starting at the garbage collection threshold
unwritable.  This page is known as a ``guard'' page and writing to it
will cause the operating system to raise an exception
\cite{mach-exception} which can be handled by user-level code.

To make this work, each of the allocation primitives must follow a
special discipline (which may be seen in Figure~\ref{fig:cons-vop}):
\begin{enumerate}
\item Clear the INTERRUPTED flag.
\item Set the ATOMIC flag.
\item Perform the allocation.
\item Initialize the new object.
\item Clear the ATOMIC flag.
\item Check the INTERRUPTED flag.  If set, cause a trap.
\end{enumerate}
This discipline is necessary so that the exception handler can detect
the case when the allocation pointer has exceeded the garbage
collection threshold and allow the allocation to complete while
regaining control afterwards.  It is important that the allocation and
initialization occur {\it atomically} as otherwise the heap could be
left in an inconsistent state.  A heap in such a state could fatally
confuse the system and, particularly, the garbage collector.

When the exception handler is invoked by the operating system, it
first examines the ATOMIC flag to make sure it is set\footnote{The
ATOMIC flag is always set whenever this exception handler is invoked.
It {\it must} be set since all allocation happens with the ATOMIC flag
set and this exception is only raised during allocation.  So why is
the ATOMIC flag needed?  The ATOMIC flag is needed for other exception
and interrupt handlers which have no {\it a priori} knowledge of the
state of the system when they are invoked (often asynchronously).}.
The handler then unprotects the page so the allocation may continue
and resumes the allocation; however, before it does so, the handler
sets the INTERRUPTED flag so that the allocation primitive will trap
when it is done.  This mechanism allows the allocation to finish while
still allowing the system to regain control immediately after the
allocation.  The trap handler, after examining the state of the system
and realizing the exception handler arranged for this trap to occur,
calls some Lisp-level code to decide if a garbage collection is really
warranted.

This scheme works well for objects which are completely initialized;
however, it fails for objects which do not require explicit
initialization since the allocation of such objects will not write to
the guard page and, consequently, will not cause an exception to be
raised.  The allocation primitives for such objects follow a different
discipline: they simply perform an explicit comparison of the
allocation pointer and the start of the guard page after allocating
the object and invoke a trap when necessary.

\subsection{Stop-and-Copy Garbage Collection}
The current garbage collector in the new port of CMU Common Lisp is a
copying garbage collector based on Cheney's algorithm.  It is written
in The C Programming Language for portability.  It is nearly operating
system independent and the sections of the garbage collector which are
operating system dependent have been modularized.  Further, the
garbage collector is easily extensible as it is completely table
driven.  Adding new ``methods'' for scavenging and transporting
objects is almost trivial.  Emphasis so far has been placed on
simplicity, clarity, style, and portability
\footnote{To give an example, the same code with only minor changes
has been used to implement a preliminary version of the CMU Common
Lisp {\tt PURIFY} function.  {\tt PURIFY} is responsible for moving
objects out of dynamic space and into static and read-only space.  Its
primary use is to help build Lisp core images.}, not on performance.
The code is presented in the appendix.

\subsubsection{Special Considerations}
Garbage collectors in real, high-performance Lisp systems are seldom
as elegant as the algorithms on which they are based -- there are
always special considerations which must be addressed.

One such consideration in the new CMU Common Lisp garbage collector
involves derived pointers.  A derived pointer is a pointer into the
middle of an object and such pointers are often created during array
or structure accesses.  Derived pointers must be handled specially by
a garbage collector and they must not be interpreted as normal
pointers.  Fortunately, there are several solutions.  A simple
solution which was adopted for the new port is to compute and store
any derived pointer in a special register and to always keep the
original base pointer in some other register for the life of its
derivative.  Since this invariant is maintained, it is trivial for the
garbage collector to find the derived pointer (as it is always in the
same register) and its base pointer.  The base pointer is located by
finding the register in the set of valid Lisp registers whose value is
closest to the derived pointer and less than or equal to
it\footnote{If the set of valid Lisp pointers is $R_{i}$ and $R_{d}$
is the derived pointer, the task is to find $i \mid R_{i} \leq R_{d}
\wedge R_{i} > R_{j}, i \neq j$.}.  This register's index and the
offset between the base pointer and the derived pointer are recorded
and after all of the registers have been scavenged, the derived
pointer is recomputed from the new value of the register and the
offset.  The program counter requires similar attention if it was in
fromspace before the garbage collection as it is essentially a derived
pointer of another register in this case.

Another special consideration regards the handling of {\tt EQ} hash
tables.  The implementation of {\tt EQ} hash tables in CMU Common Lisp
uses an object's pointer or its immediate representation as a
parameter to the hashing function.  Therefore, whenever an object is
moved it must be rehashed since moving an object changes its hash key.
The garbage collector facilitates this by taking special action when
transporting {\tt EQ} hash tables.  This special action consists of
setting a bit in the hash table indicating that the hash table needs
to be rehashed.  All of the Lisp-level functions which operate on {\tt
EQ} hash tables check this bit before operating on a hash table; if it
is set, the Lisp-level code first calls a routine to rehash the hash
table.

The garbage collector also needs to have intimate knowledge of how the
system handles interrupts.  The UNIX operating system saves the state
of the world upon an interrupt in a structure known as an interrupt
context.  The saved state includes among other things information
about the interrupt and a copy of the set of machine registers at the
time of interrupt.  The garbage collector must scavenge all registers
in these saved sets that contain Lisp objects during a garbage
collection.  This is further complicated by the fact that the system
may be interrupted while in a non-Lisp state\footnote{Such a state
exists, for example, during a foreign function call.} -- the garbage
collector must be very careful {\it not} to examine any saved
registers from such an interrupt since they will not contain valid
Lisp objects.

\subsubsection{Extensions}
As a simple extension, weak pointers have been added to the CMU Common
Lisp system with the help of the garbage collector.  A weak pointer is
a pointer which may point at an object in the heap but, unlike normal
pointers, it does not prevent the object from becoming garbage.  Weak
pointers are useful for building doubly-linked and persistent data
structures.  Consider the data structure shown in
Figure~\ref{fig:weak}.
\begin{figure}
\centerline{
\psfig{figure=weak-example.PS}
}
\caption{Weak Pointer Example}
\label{fig:weak}
\end{figure}
Suppose the user's program is using some package\footnote{{\it
Package} here is used to denote a software module rather than the
Common Lisp {\tt PACKAGE} data type.} which has a large persistent
data structure.  Further, suppose that the user's program then calls
some function in that package which creates and returns some object to
which the data base refers with pointer $P_{a}$ (because, for example,
it must keep track of the object to update it).  Now the user's
program has a handle on the object through pointer $P_{b}$.  Ideally,
if the user's program modifies or destroys pointer $P_{b}$, the object
should become garbage; however, it will not since the object will
always be reachable from some root pointer via the persistent data
structure.  Weak pointers are useful because if a weak pointer is used
in place of $P_{a}$ this problem does not arise, since a weak $P_{a}$
would {\it not} cause the object to be retained even though it would
be reachable.

The implementation of weak pointers is straightforward.  Weak pointers
are simply pointers out of objects called weak cells.  While
scavenging newspace, the garbage collector chains together any weak
cells it finds so that it may scan them when it is done; it does {\it
not}, however, scavenge the pointer inside the weak cell.  After
completing the scavenge of newspace, the garbage collector then scans
all of the weak cells it found either updating them or marking them
``broken.''  A weak cell is updated if the weak pointer in the cell
points to an object in oldspace and that object contains a forwarding
pointer; this indicates that the object was referred to by some other
pointer and was copied into new space.  The forwarding pointer points
to the copy of the cell in new space and this value is placed in the
weak cell.  If no forwarding pointer exists in the cell, then the weak
pointer is marked as invalid.  (Note that it would not be difficult to
add finalization of weak pointers.)

\subsubsection{Future Work}
There are a number of areas in which further work is needed.  The
first is adding more instrumentation.  Currently, the instrumentation
consists of measuring and reporting elapsed real time, system time,
and user time along with the total number of bytes scavenged and the
total number of bytes retained.  Additional instrumentation needs to
be added so that new ``improvements'' may be evaluated quantitatively
on more dimensions.  For example, a table listing the frequency of use
of all of the scavenging and transporting methods would be extremely
informative.  A breakdown on the distribution of the size of objects
scavenged segregated by object type might also be handy.

With additional instrumentation, it will be relatively easy to improve
performance by simply recoding parts of the garbage collector.  As
mentioned earlier, emphasis so far has been placed on clarity and
style.  There are known inefficiencies in the code -- in particular
there are a number of function calls which could easily be eliminated
without obfuscating the code to any serious degree.

There are two algorithmic changes which deserve further attention.
Both strive to improve post-garbage collection performance of the
system by reducing paging.  Paging is hopefully reduced by increasing
the locality of reference in the heap.  The first change is minor.  It
involves experimenting with the order used to scavenge the pointers in
the root set to find the order that typically best improves the
locality of reference of objects in the heap.  The root set for the
new port consists of any valid interrupt contexts, the interrupt
handler functions, the control stack, the binding stack, and all of
static space.

The other change involves adding one of the pseudo depth-first
traversal modifications described in Section~\ref{sec:paging} to the
garbage collector.  While doing so will make garbage collections
slower, the potential exists for a large improvement in post-garbage
collection performance due to the modification.

\subsection{The Design of a Generational Garbage Collector under a
Sophisticated Operating System}
\typeout{GGC}
This section contains the draft of a design for a generational garbage
collector for the new port of CMU Common Lisp.  Work on this garbage
collector is currently in progress.

\subsubsection{Operating System Support}
This design requires sophisticated operating system support.  In
particular, flexible virtual memory support is assumed.  The MACH
operating system \cite{mach-kernel} has such support, and,
consequently, this design specifically addresses the use of the MACH
operating system although other operating systems could be used.

\subsubsection{Number of Generations}
Four generations are used each with a scavenge time, $t_{s}$, roughly
an order of magnitude larger than the previous:
\begin{itemize}
\item Generation 0

The young generation.  Most objects are created in this generation.
It flips often and will be sized and scheduled to have a scavenge time
$t_{s} \leq 1$ second.

\item Generation 1

The intermediate generation.  The size of this generation will depend
on the amount of physical memory available and will be chosen so that
paging is not a dominant factor.  The scavenge time, $t_{s}$, will be
tens of seconds.

\item Generation 2

The advanced generation.  This generation holds user objects advanced
from generation 1; thus, it should fill very slowly.  It is only
flipped when there is a danger of running out of virtual memory or
backing store.  The scavenge time, $t_{s}$, will be large -- tens of
minutes.

\item Generation 3

The initial generation.  This generation holds objects which are part
of the Lisp system itself and, possibly, any user objects which have
advanced from generation 2.  It is somewhat similar to the static and
read-only spaces described in Section~\ref{sec:old-heap}.  It is never
flipped.
\end{itemize}

\noindent
More generations may be necessary for increased throughput.

\subsubsection{Heap Organization and Advancement Policy}
Each generation is divided into two semispaces (or buckets) and a
creation space.  When scavenging a generation, one of the semispaces
acts as a newspace for objects being copied out of the previous
generation while the other acts as a fromspace for objects being
copied into the next generation.  The creation space is completely
emptied upon each scavenge and the data (normally) remains in the same
generation.  

This results in a two scavenge advancement threshold.  By realizing
that the data in the creation space are ordered by age and immediately
advancing some percentage of that data, the advancement policy may be
varied continuously from a one scavenge advancement threshold to a two
scavenge advancement threshold.  This is essentially the organization
proposed by Wilson \cite{wilson89a} and Wilson and Moher
\cite{wilson89b} and it is detailed in Section~\ref{sec:gen-layout}.  It
is a well-balanced solution as it maintains a decent guarantee of
object age, allows for a flexible advancement policy, and advances
data quickly enough that copying costs are reasonable.

\subsubsection{Recording Intergenerational References}
A generational garbage collector must be able to find all of the
intergenerational references in the heap.  In this design,
intergenerational references are recorded via page marking using a
MACH memory manager \cite{mach-kernel}.  A MACH memory manager is a
server which handles paging requests from a MACH kernel for memory
objects.  Most memory objects are created by the kernel and are
handled by the default memory manager that is part of the kernel.
However, the MACH virtual memory system allows a user to create
specialized memory objects and to supply external, user-level memory
managers to manage these objects.

A memory object may be mapped into the address space of any number of
tasks; in fact, a task's address space is simply a mapping between
contiguous virtual memory addresses and memory objects.  The MACH
kernel uses physical memory pages as a cache for the contents of
mapped memory objects.  A memory manager is responsible for supplying
data for any page in a mapped memory object when a cache miss (page
fault) occurs.  The MACH kernel may also decide to flush a page from
its cache at any time.  This is known as a page out operation and a
memory manager is responsible for supplying backing store to handle
page outs for all of its memory objects.

External memory managers allow a task to manage its address space in
interesting ways.  Using an external memory manager, a thread may map
a memory object created by the external memory manager into its
address space and then access that memory directly in the normal
manner.  The kernel will call the corresponding external memory
manager to handle any paging requests for the mapped memory.

In this design, an external memory manager is used to perform
``transparent'' page marking.  The Lisp external memory manager runs
as one of two threads in the Lisp task: the Lisp thread proper and the
Lisp memory manager thread.  Ranges of virtual memory which require
marking are created by allocating a special {\it with-marking} memory
object managed by the Lisp external memory manager and mapping that
memory object into the Lisp task's address space.  Backing store for
each of these memory objects is allocated in the normal manner from
the kernel.

When a page fault occurs on a memory object, the kernel sends a {\it
memory object data request} message to the appropriate memory manager
requesting the data for the faulted page .  The Lisp external memory
manager handles these request by simply sending the kernel the
corresponding page of backing store.  When a page out occurs on a
memory object and the paged-out page is {\it dirty} (i.e. it has been
modified), the kernel sends a {\it memory object data write} message
containing the data for that page to the appropriate memory manager.
The Lisp external memory manager handles these request by copying the
dirty page into the backing store and marking the page for the garbage
collector.  Thus, page marking in this design is implemented in a
manner similar to Shaw's virtual memory page dirty bit marking
mechanism; however, page marking in this design is
portable\footnote{That is, it is portable to any machine running the
MACH operating system.}.

Page marking was chosen because it is cheap, unobtrusive, and simple
to implement (under MACH).  Unfortunately, with page marking,
scavenging performance can suffer dramatically due to the large number
of locations which must be scanned for each marked page.  This
overhead can become excessive -- especially if the locality of writes
into older generations is poor as many pages will become marked.

It may be necessary to use different strategies for different
programs.  Some programs might opt to use software card marking
(conditional or unconditional) whereas other programs might use page
marking exclusively.  To make this work, all system code would have to
be compiled with software card marking.  Programs which used page
marking would have to run in a special dynamic environment which would
work as described above except that instead of marking dirty pages,
all of the cards corresponding to a dirty page would be marked.  This
scheme would facilitate the flexible use of conditional and
unconditional software card marking and page marking in the same Lisp
system.

\subsubsection{Scanning Marked Pages}
During a scavenge, all marked pages must be scanned for
intergenerational references.  This is complicated by the fact that
Lisp objects in the heap may contain unboxed data -- raw bits that may
look like valid Lisp pointers.  Several solutions to this problem were
outlined in Section~\ref{sec:forward-pointers}.

The solution adopted for this design is to divide each generation in
half and store boxed and unboxed objects separately.  This layout is
illustrated in Figure~\ref{fig:my-heap}.  Note that the zero
generation is {\it not} segregated since it is never marked and,
consequently, never scanned.
\begin{figure}
\centerline{
\psfig{figure=my-heap.PS}
}
\caption[foo]{Layout of Generations with Separate Boxed and Unboxed Spaces}
\label{fig:my-heap}
\end{figure}
The novel use of an unsegregated zero generation is interesting
because it greatly simplifies allocation (which is discussed further
in Section~\ref{sec:gen-allocation}); it may also result in improved
paging and cache performance since the density of all of the truly
``hot'' objects will be greater.

While scavenging the zero generation, the garbage collector will have
to sort the advancing boxed objects from the advancing unboxed objects
and transport them into the appropriate areas of the next generation.
The overhead to do this will be almost negligible since the garbage
collector already must determine the type of an object in order to
transport it.

Separating the boxed from the unboxed objects not only makes scanning
simpler, it makes scanning more efficient too.  Since boxed objects
contain only valid Lisp objects, marked pages may be scanned {\it
blindly} without trying to interpret the objects or the contents of
each page.  This should help reduce the extra scavenge-time costs due
to scanning which are associated with page marking.

Separating boxed and unboxed objects has another performance
advantage.  It reduces the total amount of memory which must be page
marked since the unboxed section of each generation does not need to
marked (since it cannot contain valid Lisp pointers).  While the
previously described implementation of page marking is fairly
efficient, there is still some overhead incurred.  Thus, eliminating
the need to mark several large sections of memory will improve
performance, if only slightly.

Using separate spaces for boxed and unboxed objects does have one
major drawback -- it could potentially increase the size of the heap
by as much as a factor of two.  This, however, is not a concern under
MACH because MACH implements large, sparse address spaces efficiently.

\subsubsection{Code Objects}
Code objects are problematic.  Code objects may not be placed in
either the boxed area or unboxed area of the later generations as code
objects contain both boxed and unboxed data.  Thus, code objects must
be handled specially.

One solution is to place all code objects in special generations and
to handle intergenerational references for these generations
differently.  Two generations should be sufficient as code objects
most likely have a bimodal lifetime distribution.  Code objects either
die off quickly (as is this case with those that are top-level forms)
or they live virtually forever (as is the case with those code objects
that compose a program).

It is important to note that code objects are only created by the
system functions {\tt LOAD} and {\tt COMPILE} and that they are
immutable.  Thus, it would be easy to special case the allocation of
code objects if necessary.  However, a simpler solution is to allocate
code objects in the creation space in the zero generation where most
other other objects are allocated.  Allocation of code objects in the
zero generation would give code objects an initial chance to die off
before being advanced into the ``permanent'' code generation.  Thus,
only one additional generation, a ``permanent'' code generation, is
needed for code objects.

Placing code objects in their own generation does not solve the
problem with intergenerational references.  Further, it is not
possible to page mark the ``permanent'' code generation and scan it
naively.  A brute force solution would be to scan all of the advanced
code objects at every scavenge in order to find the intergenerational
references; this, however, would be much too costly.  A viable
solution would be to maintain an unscannable set and to use it to
interpret code objects and marked pages during scanning as described
described in Section~\ref{sec:forward-pointers}.  This solution should
be explored further; it would be advantageous, however, to find a
solution which does not require interpreting code objects at scavenge
time.

It may be possible, through a special advancement policy for code
objects, to keep the number of intergenerational references in a code
object to a minimum by transporting any of the referents of a code
object into an older generation when transporting the code object
itself.  However, it is impossible to cheaply guarantee that there
will never be any intergenerational references in all advanced code
objects.  For example, some referent of a code object might have
already been advanced (due to some other reference) when it comes time
to advance the code object; this would make it impossible to advance
the referent to an older generation without also scavenging the
referent's generation.

Even though it is impossible to rely on a special advancement policy
alone, such a policy is still useful because any remaining
intergenerational references can simply be explicitly recorded and
scanned at scavenge time.  This would be beneficial since it would
reduce the overhead of scanning code objects at scavenge time.  To
implement such a scheme, all intergenerational references would have
to be copied into per-generation data structures along with pointers
back to the original references.  The garbage collector would scan the
copied references at scavenge time looking for intergenerational
references; when one was found, it would scavenge the reference and
update the copy {\it and} the original reference by following the back
pointer.  The advantage of explicitly tracking the intergenerational
references in code objects is that it eliminates the need for the
scavenger to understand how to interpret code objects and marked
pages.  This reduction in complexity would offset the complexity of
maintaining this separate data structure.

This scheme also has the potential to significantly reduce paging
while scanning code objects for intergenerational references.  If all
of the intergenerational references due to code objects are recorded
as pairs (the copy of the reference and a pointer back to the original
reference) in contiguous addresses in memory, all of the
intergenerational references will be contained on a small number of
pages.  Scanning these pages will cause only a small fraction of the
page faults that scanning the code objects themselves would cause.

\subsubsection{Allocation with Generational Garbage Collection}
\label{sec:gen-allocation}
The novel use of an unsegregated zero generation greatly simplifies
most allocation.  Since there is only a single free pointer and since
boxed objects and unboxed objects are treated identically, allocation
in the zero generation may be performed as described in
Section~\ref{sec:fast-allocation}.  Thus allocation in this design is
also ``fast.''

It will, however, be advantageous to allocate certain objects directly
into later generations.  Large objects (and in particular large
arrays) that would otherwise suffer significant copying costs should
be allocated directly into an older generation.  This is really a
practical consideration but it makes sense from a generational
viewpoint too -- an object's lifetime is related to its size (although
not as directly as it is to its age).  Large objects tend to have
longer lifetimes than smaller ones.

Further, it would be nice to export a primitive to the user to control
where allocation occurs and to effectively facilitate the direct
advancement of objects.  This primitive would most likely be a macro
or special form perhaps called {\tt WITH-ALLOCATION-IN-GENERATION}.
Any allocation occurring within the dynamic extent of the form would
occur in the specified generation.  This would allow the programmer to
tell the system which data structures in the program are permanent so
that the data would not incur repeated scavenging and copying costs.

Unfortunately, the use of an unsegregated zero generation makes
allocation in later generations more difficult because allocation in
later generations must be handled differently than allocation in the
zero generation.  This is not a problem for system code (such as the
code which performs array allocation) as it can use special primitives
to do its job; it does, however, make the implementation of the {\tt
WITH-ALLOCATION-IN-GENERATION} form difficult.  The form cannot simply
rebind the dynamic space allocation pointer (ALLOC) to the specified
generation's allocation pointer\footnote{It cannot because, if for no
other reason, there is not a single allocation pointer for the older
generations.  The real reason, of course, is that boxed objects must
go in one area and unboxed objects in another.} during its dynamic
extent.  Several solutions have been proposed but none have been both
general and efficient.  This is an area which requires more
investigation.

\subsubsection{Instrumentation and Tuning}
A significant amount of work will have to be done in the area of
instrumentation.  Tuning a generational garbage collector can be very
difficult due to the large number of variables involved and the
complex manner in which they interact.  Good instrumentation is one of
the few tools which can help reduce this complexity.  Effective and
efficient instrumentation is also useful for implementing adaptive
advancement policies and scavenging schedules.

\subsubsection{Other Ideas}
There are several other interesting ideas which may be incorporated
into this design.  The first involves the observation that the
lifetime of some heap-allocated data are closely associated with
function calls and returns \cite{lieber-hewitt83,wilson89b}.  Another
related observation is that it is usually a good time to garbage
collect when the control stack is near its top\footnote{This assumes
the reader pictures stacks growing down.}.  When the control stack is
near its top, the program is typically running in one of its top-level
functions and has usually just completed some major computation.
Consequently, this is a good time to garbage collect as the heap is
likely to contain a large percentage of garbage.  While developing
heuristics to utilize these observations and integrating them into the
system may be difficult, they merit further attention.

Another idea which could be incorporated into this design is to add
Appel-Ellis-Li-style incremental garbage collection for those programs
which require pseudo-real-time performance.  This could be integrated
nicely into the Lisp external memory manager and, modulo code objects
and the zero generation, could work without a crossing map due to the
segregated heap.  This style of incremental garbage collection is
discussed in detail in Section~\ref{sec:incremental}.

%\end{document}
