; -*- text -*-

Last modification: Sun Nov  8 02:35:58 1998

A gen gc for guile, 

The latest versions of this document (as well as news on the gc, and
probably some other things) can be found at
http://home.thezone.net/~gharvey/guile/guile.html


The layout:

(Any particular bit can be found by searching for *xxx bit,
i.e. *Zeroth bit)

The Zeroth bit deals with the purpose of this document, as well as
serving as a prime example why numbering *after* the document is
written is a good idea (and using a markup language to do it
automatically is even better). This is mostly unrelated, and can be
safely skipped.

The First bit deals with what a generational garbage collector is; the
benefits and drawbacks of the generational approach; pointers to
additional information about the issues in garbage collection; and the
definition of some terms. This can also be skipped, if you already
know (or don't care about) what a generational garbage collector is.

The Second bit contains things that are important to remember about
guile, and things that I've been assuming were true up until now, but
I'm not 100% sure about. Might be a good idea to check out if you know
a lot about the gutz 'o guile, and let me know if I've made a bad
assumption. 

The Third bit details the problems faced with implementing a
generational gc in guile, and looks at various solutions, weighing
their benefits and drawbacks. Quite wordy. This could probably be best
refered to as an edited stream of conciousness.

The Fourth bit gives what I currently consider the preferred
implementation. It also summarizes some of the information from the
Third bit, giving a terse list of methods, their highlights &
lowlights.

The Fifth bit tries to quantify some of the costs of various
implementation details. This isn't entirely rigourous, but could be
useful if you don't give a hoot about how it's implemented, but want
to know how much it's gonna cost you.

The Sixth bit deals with the actual implementation. Mostly, it's a
scratch pad for figuring out what parts of the gc will be responsible
for what actions, and what has to be remembered in certain areas to
keep the state consistant.

The Seventh bit deals with possible future features, which might
influence the implementation.

*Zeroth bit

This document exists for several reasons:

1) I generally keep notes on things anyway, and it's not too much
   extra work to make them (hopefully) readable. I'm a bit sorry that
   I didn't start off using a markup language, though.

2) A change to the guile gc is going to affect all users of guile. I
   would like to make it possible for anyone requiring special
   considerations from the garbage collector to make them known before
   work on the actual implementation begins. I'm trying to avoid a
   quick hack that breaks everything, everywhere, and it makes sense
   to me to give an opportunity to people who know more about guile
   than myself to point out potential problems. I'd also like to be
   able to get an idea of how much extra space requirements people are
   willing to live with in order to get a quicker gc.

3) Unlike more dynamic (sane) programming languages, c doesn't
   lend itself well to exploritory programming. I prefer to have a
   very solid idea of what I'm going to do with c, before I start
   doing it.

Flaws:

1) It tends to detail very simple things.

2) Poorly structured. It may tend to jump about a bit. In some places,
   I was writing as I pondered, and sometimes a seemingly unrelated
   bit would suddenly click with a bit already written, so I'd mention
   it there, and go back to mention it in the relevent section, as
   well. It might also refer to things that turned out to be really
   stupid ideas and disappeared.

3) Far too long. It is. I didn't intend to do this much.

4) A bit incomplete. I'd really like to stop all this writing and work
   on some code.

5) It's sort of a look into my mind as I figure things out. That could
   be kind of spooky.

*First bit

+Resources

Some quick & dirty information on generational garbage
collectors. This not a complete treatment of garbage collectors. For
those who think it's all a little bit voodoo, I'd recommend checking
out Paul Wilson's gc surveys at
http://www.cs.utexas.edu/users/oops/papers.html  

There is also a wealth of papers at their ftp site at
ftp://ftp.cs.utexas.edu/pub/garbage
not all of which are linked to from the papers page.

Also useful is the code to other garbage collectors. Some of the
implementations I've looked at include: the generational gc from elk,
the sgc from gcl, and Boehm's gc for c and c++.

Other resources on more specific bits of the implementation:

Write Barriers:

Barrier Methods for Garbage Collection, by Bejamin G. Zorn:
ftp://ftp.cs.colorado.edu/pub/cs/techreports/zorn/CU-CS-494-90.ps.Z


+What is it and why do we want it?

In traditional garbage collectors, both copying and mark/sweep (the
current method of guile), every garbage collection requires a scan of
every currently live object. In the case of mark/sweep, things get
even worse, because it not only has to mark each live object, but it
has to scan every chunk of heap memory current used by the application
in order to find dead objects (whereas copying takes a more memory
intensive approach, which allows quicker collections, but larger
memory requirements). In quick & dirty profiles of guile, it
appears that guile spends close to half of it's time collecting
garbage (at least in the startup).

A generational garbage collector is a modification of one of those
methods which takes into account general allocation and garbage
creation patterns that typically occur in programs, such as:

1) Many young objects are created for temporary or local storage, and
   don't tend to hang around very long. Therefore, they're more likely
   to be garbage, and a collection of these will likely yield a
   significant amount of garbage.

2) Conversely, old objects tend to not die very often, so we generally
   don't expect to get much memory back when we scan older objects.

Taking these two `facts' into account, we see that there can be
significantly less work done in the garbage collector if we collect on
young objects more frequently, leaving the old objects to be scanned
only occasionally, when we are hard up for memory (or it seems like a
good idea). This gives us the benefit that we tend to get back much of
the garbage that is created, without having to touch every live object
& every piece of heap memory.

The main drawbacks to a generational gc are: 

1) it can have a tendancy to use up a lot of memory... old dead
   objects will hang around for a while, and all objects need to have
   extra information to make the generational gc work (at the very
   least a generation number, but there's more to it than that).

2) it will likely not perform well in the cases where memory
   allocation patterns differ from the general scheme of young objects
   dying a lot more often than old objects.

One possible objective when implementing a gen-gc in guile is to make
it possible to change gc methods at run-time (possibly even during
run-time, if feasible), allowing the current mark&sweep collector to
be used if it makes more sense for a specific application. It's likely
that the generational gc will include full mark&sweep as a fall back,
since it allows you to avoid the 'figuring out who points into what
generation' stage that would occur if implementing a full gc as a gc
on each individual generation.

A few (obviously not technical) terms that get used throughout, which
could represent an underhanded attempt to create emotional attachments
to objects so that they won't get killed by accident, or just a short
hand for writing younger generations/older generations:

Babies: all objects that haven't yet survived a collection. All
	created objects are initially babies.

Kids: objects in mid-generations. What this actually refers to is
      dependent on the final implementation, but are somewhere in the
      generation range 1 <= kid < geezer

Youngsters: The set of Babies && Kids

Geezer: oldest objects. Also implementation dependent, but there's a
	good chance that geezers will get some special treatment.

Rogue: any object `out of place'. A baby in the middle of a bunch of
       geezers, for example. Mostly used in relation to conservatively
       traced objects (who are always rogues).
       
Scan: synonym for the marking sequence (yeah, I know, but pedancy is a
      lark)
*Second bit

Important things to remember in the implementation for guile:

1) Don't move objects traced conservatively. This is not a difficult
   constraint, but I did overlook it in the earliest incarnations of
   improved gc ideas.

2) Needs to provide compatable definitions for everything currently
   exported by the gc.

Possible misunderstandings (if any of these are wrong, please point
them out):

1) We don't need big chunks of contiguous heap. This seems safe, and
   isn't a really sticky point if not true.

2) Heap segments aren't created with ncells != 1... even if this isn't
   the case, it's not a big problem, but makes compacting different
   heaps impossible.

*Third bit

The essential problems:

Generational garbage collection isn't all that difficult. The concept
is fairly simple and obvious, but the implementation tends to have
more interlocking pieces than non-generational gc's (i.e. how and
where we can place objects has an effect on how we implement
generation information, which affects how we find pointers to younger
generations, which affects how and where we can place objects). The
primary goals are to make it quick, and avoid sacrificing too much
memory (if we wanted to be really fast, we could ignore garbage
collection altogether, and just restart when there's too much
garbage).

This section looks at the issues (not necessarily independant of one
another, or exhaustive) that have arisen so far in figuring out the
implementation; the possible implementations and solutions are each
treated in the sections following (search for Problem #x).

1) Locating the members of a generation: needs to be quick and cannot
   just blindly scan the heap all the time (or else, you get what we
   currently have)

2) Finding out who points where: we have to know of inter-heap
   pointers to find roots for tracing... if not, used objects will be
   collected, which is obviously never going to be acceptable. This
   requires both knowing when an object is changed to point to a young
   generation, as well as finding those objects at collection time.

3) Memory organization and fragmentation: this is currently not a big
   problem with guile since we use a free list, and can place objects
   anywhere we please. With a generational scheme, however, it's quite
   desirable to not spread youngsters all over the place. If we can
   constrain them to one or a few heap segments, then scanning is a
   breeze. The problems occur with geezers, who can end up spread all
   about the heap, and whose storage cannot be easily reused once they
   die. 

4) Conservatively traced objects: tremendously useful, or a tool of
   the darkest evil? 

5) When to age objects: It's important to find a balance between
   advancing objects too quickly (and creating tons of garbage
   geezers, which are more work to scan), and advancing too slowly, so
   that potential geezers are scanned repeatedly.

6) When to collect: We need an acceptable method of determining the
   collection schedule of the various generations.

Problem #1 

i) Representing generations:

It's necessary to keep some extra information on objects in order to
implement a generational scheme. The questions that arise are 'Where
does the information go?' and 'How do we get at it?'

Implementing this directly on the object (as the current scheme does)
isn't feasible, since we need more bits than can be squeezed out of
our current SCM values.

My initial thought on this was that each generation should use a data
structure that would allow us to both check if an object is a member
of that generation, and to quickly locate all of a generations
objects. The problem with this approach is that it adds a lot to the
storage requirements for each object (potentially more than doubling
the space needed for representation). For a babies & kids, this is
doubly stupid, since it's pretty easy to direct where the objects are
created, and in the early going, maturing kids should tend to be
around the same area.

A second idea (suggested by Jim Blandy), would be to represent this
information in a per-segment byte vector. This has the major benefit
of consuming less memory, but introduces significant effort in
scanning geezers, which can be spread across many heap segments,
requiring that a lot of heap segments be swept, if this is just placed
on top of the current heap management.  I consider this to also be an
unacceptable general solution, since this would require close to as
much work as the current gc for geezers, which likely won't result in
significant garbage being collected. This method also has the drawback
that getting at the info for an object requires a scan through the
existing heap segments to find out where the object is, calculating
it's offset in the heap segment, then accessing the vector.

I can see two solutions to this problem (independent to the heap
layout, which will be covered later), covered in the next two
sections.

ii) Manage different generations differently:

Since the goals are to make youngsters small and easily to dealt with,
while making sure that geezers don't bog us down in scanning, maybe we
should manage each generation differently. Geezers, who will require
significant effort to find and scan under the vector approach, can be
listed in a global per-generation data structure, while babies & kids
can forgo the memory overhead of a more complex data structure by just
using a per segment vector. This is a nice fit, as we can generally
expect to have to trace a full segment when a gc gets called on the
youngsters anyway, because that's the only place we plan on putting
them.

When an object reachs a certain age (tenatively, either the fourth or
the eight, to allow the simple byte vector approach for young
generations to work), we can promote it to a special status, and keep
more information on the objects in these & older generations. Assuming
that this initial advancement will likely occur in a fairly localized
place (all objects of gen. 3 grow up at the same time), it could
probably allow us to just junk the vector, and set them up in the
generation data structure.

iii) Kill 'em all! Taking the old with the young:

An alternative approach would be collecting all generations <= the
current generation being collected. This has the potential benefit
that we're going to be treking all over memory anyway, so at least we
are potentially going to get more garbage collected. This does have
the problem of increasing pauses in gc and still doesn't really fix
the problem. Also, if the gc chooses to do a gc on the next generation
before allocating more heap, it means a ton of duplicated effort (a
factoral gc).


The exception to this is that babies are always collected. In
practice, this will be quicker than going through the trouble of
keeping track of where all these potential stillborns point.

iv) Thinking forward:

Depending on the solution to the memory problems (Problem 3), the
chips could fall heavily towards the vector approach.


Problem #2:

Stop pointing at me!

With a generational gc, we need to be able to find out quickly who
points where across generations. For example, when we're scanning the
first generation, we have to take into account that object in the
eight generation that points to that young, cute little cons cell. It
is a good idea to not keep track of baby objects that point into older
generations, since we can assume that many of these will be created
and die long before the old generation is scanned. It's questionable
whether we should start this with objects once they reach the first
generation, or at some later time. This has the benefit that the only
young objects that have this info associated with them are the objects
that live long enough to make it worthwhile, and will require only a
scan of the child generation (happening often, anyway) to find other
possible roots for the old generation being collected.

i) Determining when pointers are changed:

The only real feasible solution for guile is to use a write
barrier. This will likely depend upon memory protection services in
the host os, but any os that doesn't provide this probably isn't
running guile in the first place. For machines that do run guile, but
have nothing resembling mem protection, I'd welcome a pointer to an
implementation of a suitable memory protection mechanism that doesn't
bring guile to it's knees (or even if it does... I won't be the one
running it). 

There's actually a subtler issue here, in that the modification of
heap segments will make memory protection apply to a bunch of
segments, including segments where we plan on allocating new
babies. This might not be an issue, provided we split on page
boundries (which might also afford performance benefits on the host
machine to make it worth the small amount of mem loss that is likely
to occur). 

There is another problem with using memory protection, in that it
doesn't work with objects stored outside the heap; for example, an
smob that contains a heap pointer won't be mem protected, so we will
miss that object if it gets modified, and screw things up
royally. This is one of the hardest problems, actually, because it
means finding a solution that gives good performance but doesn't
require coders to know and understand the guts of the garbage
collector. I'll not deal with it now (Sun Nov 8 02:33:15 1998),
because it falls into the class of problems that I discovered after I
thought I'd thought through everything, and it needs a bit of time to
bounce around in my head.

It will still be possible to select the current gc, or a modified
version, that won't have the memory protection requirements. Many of
the principles that make a generational gc nice can also be applied to
the current gc... in fact, the whole generational scheme could be
implemented on top of a full scan of the heap per collection, rather
than the painful fudging with the write barrier.


ii) Determining what pointers are changed:

There are also a few ways of keeping track of what pointers get
changed and where they point. A list of addresses of objects that
could point into a generation, kept on a per generation basis, would
make the selection of roots mindlessly easy. The downside: more memory
needed. 

Alternatively, we can keep track of the information on a per object
basis. This would require scans during each gc of a younger
generation. The extent of the scans could be reduced by adding to per
generation info with info on which generations it could point at, and
then scanning only those generations where there's the
possibility. 


This information is determined by the memory barrier, and needs to be
kept updated by the tracing facilities, so that if a younger object
being pointed at ends up in the same generation as the pointer, then
we can completely ignore the current object for scans with young
generations from now on.


Problem #3

How we use the memory regained in a conservational generational gc is
possibly the most complicated issue involved. Here, more than any
other place, we have to cross our fingers and hope things turn out all
right.

i) I've fallen and I can't get up: The croaking geezers problem

Younger generations have a large benefit, in that it's easy to tell
where they are.  Older generations pose a different problem; they are
stuck in one place, and possibly scattered over many segments. When
they die, there's a gap left in the heap segment, and if we constrict
the babies to one particular area, nothing new will be put
there. Two possible solutions here:

1) Bugger sticking babies in one place, and use the whole heap
   (the current method of guile)

2) Ignore the empty spaces until they're significant, then compact the
   old objects as much as possible, freeing the unused space at the
   end. This is a bit iffy, since it's unknown whether the operating
   system can actually make use of that memory, or if it just rots
   there (meaning the gc won't really doing it's job of collecting
   memory to be reused)

The problems in the first can be overcome by keeping more information
on young generations.

The problems in the second can be removed by either changing what a
heap segment is, from a chunk of contiguous memory to a collection of
chunks of memory, possibly not contiguous; or by modifying the current
code to allow us to chunk up and use small segments when we need to
reclaim some memory.

Note that, for the latter to be worthwhile, it is utterly necessary to
do some amount of compacting. It also raises issues with the memory
protection scheme, as we can only start a segment on page
boundries. In the case of linux, it means the smallest number of
objects per segment is 512 with the system provided write
barrier. However, the memory protection services also have other
problems, which are covered

ii) It's garbage collection time: Do you know where your children are?

One approach would be to use the current 'allocate objects everywhere'
method, and keep a copy of the free list after a collection and only
check the elements there on the next collection of the youngest
objects.. This only solves the problem for the absolute youngest
generation, greatly increases the memory for these mostly garbage
objects, and feels gross. 

iii) Bending the heap to our evil purposes

a) Making heaps nice by breaking them: Virtual heap segments

This approach will change heap segments from strictly a chunk of
contiguous memory, to a collection of fragments all over memory. This
fits in very well with the different representations for different
generations idea (since the vector approach to heaps is based on
position in the segment, rather than the address of the
object. Unfortunately, this will cause major problems if a chunk of
contiguous heap is required (though this could be worked around by
creating a new contiguous heap segment if the need comes up). Can also
result in the youngster collections having to trot all over memory. 


b) Don't be so complicated: Using smaller heaps

Instead of solving fragmentation with screwy heap segments, it could
be better to just split a heap segment when it contains an older
generation & free space. This amounts to changing the upper bounds in
the first segment, then initializing a new heap segment with the rest
of the segment. Per generation info can be kept on what heap segments
can contain this generations objects. Compacting is still an issue,
though.


Problem #4 

Guile has a great feature, in that you don't have to bend over
backwards to use SCM objects in c without having them gc'd behind your
back. Guile has a terribly annoying feature where it scans for objects
through chunks of memory which may or may not actually be SCM
objects. The facility is one and the same, and is the largest headache
in the gen-gc. Any object in the heap could be traced conservatively,
and when it is, it has to stay put. 

i) Stop pushing me man!

A possible simplification to the problem is to avoid using generations
with conservatively traced objects. In fact, it's a bit senseless to
generationalize these objects; they will be hit on each collection,
because we always have to scan the stack. This will require a means of
tracking rogue babies, since they can end up smushed about the stack.


ii) The fountain of youth

Removing generational control from stack traced objects is a big win
for baby objects, but what should be done when an older object is
scanned from the stack? While it's probably not a good idea to remove
the object from it's generation (since being used from the stack
doesn't really mean it's going to die, or become more likely to die),
it is going to make it difficult to do sane things with the heap to
avoid memory wastage. The glaring hope here is that a stack pointer to
an old object will only be a rare or temporary thing, and that they
won't significantly interfere with compacting (dangling by pinkies at
this point).

Problem #5

The problem of how to age objects isn't generally as hard as the
others, but requires a 'try 'em out, use the best one' approach. The
sensible implementation is using an extra bit to signify that they've
survived one collection in this generation, but to not advance them
until they survive a second one in the current generation.  This is
most useful for babies, because it should really help in the case of
baby garbage being created just before the gc (so, still alive, but
probably gonna die right after collection is finished).

Problem #6

I can't stand you hanging around!

A big question in generational gc is when to collect garbage. Like
aging, this is a problem that's mostly separate from the underlying
implementation (which is mostly finding time/space tradeoffs in the
data structures), but is also the main factor in determining how well
a gen-gc will perform.

The babies are a no brainer... when their segment is full, we collect
on them. For older generations, more care needs to be taken, because
we don't want to scan too often, but we want to avoid a lot of space
hanging around.

This is another 'your guess is as good as mine'. I'm thinking that the
nth generation should be collected every n collections, with a
generation getting extra priority based on the amount of memory it
currently consumes. There's the potential here for a lot of tinkering
& funky functions.

*Fourth bit

The preferred implementation:

My personal fave right now is to allow spliting heap segments, with a
two byte vector per cell for generation info. 

Each heap segment with a kid or geezer generation will keep track of
where a contained object could point (babies don't need it).

A per-generation structure will keep track of what heap segments can
contain objects from this generation, which will require some updating
when objects advance. 

Intergenerational pointers will be tracked by implementing a write
barrier on heap segments.

Babies conservatively traced are never advanced. A list of the rogue
babies will be maintained to avoid problems when the heap segment
becomes full of older objects.

There might be a few more points I missed.

Quick & dirty summaries of some problems & possible implementations.

!Problem #1

Representing generations:

1) Hold the generation info using a vector per heap segment
   
   + Small memory usage
   
   - Getting to the generation info for an object requires finding out
     what heap segment the object is in, figuring out it's offset into
     the heap, and looking up the offset in the table.

   - Can have sweep characteristics much like the current garbage
     collector for scattered objects

2) Use a global table-like structure per generation:
 
   + The locations of all objects in a particular generation can be
     accessed easily, greatly improving the sweep characteristics of
     an arbitrary generation from being proportional to the number of
     heap segments that could contain these objects, to the number of
     objects that existed in the generation before the collection.

   + The generation of any object is determined in time proportional
     to the access characteristics of the underlying data structure.

   - Changing the generation of an object has costs a removal and
     insertion in the underlying data structure (could also be a plus)
   
   - Greatly increases (potentially doubles) the storage used to
     represent objects.

!Problem #2

Determining when a pointer on the heap has changed.

A write barrier is about the only sane thing we can do with generic
hardware. This will be a problem for brain damaged operating systems.

Determining what pointers point where:

1) Keeping a list of possible pointers into a generation for each
   generation:

   + Quick and brainless finding of roots to trace

   - Real increase in memory

   - Write barrier has to find out if the pointer is
     already there (possibly time consuming, and will effect general
     usage) 

2) Grabbing two bits from the gengc tags to indicate that an object
   points forwards or backwards

   + Very small memory requirements

   + Write barrier only has to set a bit and possibly put an integer
     on a list, probably cheaper than the trapping process itself.
 
   - Even with heap segments keeping info about where they could
     point, requires a scan of some heap segments to find roots.


3) Keep an alist (or other structure) with (pointed to gen . (offsets
   into the segment)) elements in each segment:

   + Less memory than the first, more efficient than the second

   - Introduces more overhead with the write barrier.

!Problem #3

How to deal with croaking geezers.

1) Continue the current scheme of using a global freelist, and stick
   young objects into the holes.

   + Easy allocation, no fiddling about

   - Objects from the same generation are all over the place, sweeping
     a young generation would require checking all heaps where any old
     object has died (probably most).

a) Keep info on where new objects are placed

   + Sweep becomes a walk through a list, checking for marks (very
   fast, compared to a heap seg sweep)

   - Big mem requirements for short-lived objects

   - Just delays the problem until gen 1

b) Keep info on all objects

   + Sweeping everyone is so much fun, it's silly. 

   - Only able to allocate two objects, since the rest of mem holds gc
     stuff

2) Let the spaces hang around for a bit, compacting when the space
   becomes fairly large, then doing a realloc to get the heap to the
   size that's needed.

   + Simple, allows us to avoid chucking a baby between geezers,
     then sweeping through those geezers everytime we want to look at
     the baby.

   - Crosses fingers and hopes that stack traced objects aren't living
     all over the place (general compacting issue, actually)

   - The os can't necessarily use that memory anymore; if not, it just
     rots 

a) Using virtual heap segments

   + I get to make up a name for something

   + Allows us to use most memory without horrid scan times.

   + No looking at geezers when we only want to look at babies, and
     vice versa (well, kids, we always want to look at the babies)
   
   - Relies on being able to compact memory to work efficiently. 

   - Can result in a trot all over memory to do a sweep, completely
     toasting any locality of data benefits.

   - Heap memory is generally not contiguous anymore.

b) Splitting heaps:

   + Allows us to use most memory

   + Lets a heap remain a contiguous (though smaller) chunk of memory.

   + Makes the generation facilities do their own dirty work. 

   - Relies on being able to compact memory to work efficiently.

   - Possible large number of heap segments, which could make getting
     generation information on an object a very costly process.

*Fifth bit

(Mostly incomplete, more to satisfy my own curiosity than to provide
info) 

Virtual heap segments:

These could be represented using address ranges in the headers

ex

struct vheap_segment {
       int chunks;
       SCM_CELLPTR **chunk_bounds;
       ...
}

There probably isn't a better approach here.

Assuming a segment for n cells, the cost of a current heap segment is 
n*cells_size + a small chunk for headers, no more than a handful of words
= n * 2 * sizeof(SCM) ; possible dangerous assumption here!
  
For a virtual heap segment, best case:
n*cells_size + header stuff, essentially the same as a normal segment,
	                     an extra word for the pointer

For a virtual heap segment, worst case (one cell chunks all over
              memory) 
         n*cells_size + 3*n*sizeof(SCM_CELLPTR) + headers.
	               (^ bounds = SCM_CELLPTR **; bounds[n] =
                                                   SCM_CELLPTR * 2
						   No, c isn't beautiful)
	=n*sizeof(SCM_CELL) + 3*n*sizeof(SCM_CELLPTR) + headers
	=n*2*sizeof(SCM) + 3*n*sizeof(SCM) + headers (assuming
              sizeof(SCM) == sizeof(pntr)
	=5*n*sizeof(SCM) + headers

Obviously, this is a bad thing, though we can expect to never be that
stupid. 

Using small segments:

There shouldn't be major additional memory usage from these.


*Sixth bit

[Very incomplete... this will soon contain implementation details,
which isn't entirely sensible when the implementation isn't decided
upon yet, and will hopefully serve as a guide to the internals after
the gc is implemented]

How to think about it:

Operation of the gc:

The gc operates in several stages, and these need to be understood in
verifying the correctness of any proposed solutions. The order is
basically:

1) Scanning regions of memory conservatively.  i) Major changes from
   the current method are that it only needs to check objects in the
   generation's we are scanning, and that it sets the conservationally
   marked information. This allows us to know quickly what we can and
   can't move in the compacting scan. 

2) Determine the possible roots for the generations being collected.

3) Scan the generations being collected from the usual roots and the
   possible roots, stopping the trace of one object whenever it points
   to a generation we don't care about. Some conservational scanning
   also occurs, so we can't use this stage for compacting.


4) Sweep the heap segments of the collected generations. Some heap
   segments may be split if old generations have been significantly
   compacted.

There is still the issue of what to do with the memory in segments
populated by aged objects after a collection... should there be an
effort to get it then, or should we leave it until the next scan?
Possibly the splits could go first, and allow possibly skipping a gc
altogether if there is enough memory to get.

Heap tuning fun!

Depending on the memprotection, the storage for actual heap may
require page alignment. In any case, we want to keep the segments
small! Not only does this make it less of a worry to just let a badly
fragmented segment alone, it also kicks performance butt (really, even
with the current gc, you can get a 4*startup improvement by using 2048
cell segments). 
*Seventh bit

Things we may want in the future:

1) Incremental collection. I've not given this a whole lot of thought,
   and I don't know that there's enough call for guile as a hard
   real-time system to make this worth the effort and performance
   cost (by hard realtime, I'm talking don't gc longer for 10us at a
   swat or we launch the missiles, not interactive applications, who
   should fit quite snuggly into the new gc).

2) Threaded gc. The general case of allowing threads to run with a
   conservative gc is mostly impossible. Well-behaved threads, on the
   other hand, could keep chugging on while the gc works. I'm thinking
   of some approaches to this, but it isn't going to leap to 'have to
   do' until guile actually has posix threads.