Re: Outline for Guile Generational GC

[Greg Harvey <Greg.Harvey@thezone.net>]

Dale Jordan <dalej@alum.mit.edu> writes:

> Greg Harvey wrote:
> 
> > To keep the correspondance between what we're currently calling heap
> > segments (larger chunks of contiguous memory), let's call them
> > chunklets (which also has the benefit that, if they're implemented,
> > and there are bugs, I can say 'Argh!  Chunklet fudge!').
> 
> > Actually, one of the reasons I went beyond a byte is that we probably
> > should be keeping more than (8-16) possible generations. In the small
> > case, it seems like overkill, but if we stop at such a small number,
> > the last generation is likely to become large quickly. Also, since we
> > are going to have extra info per object, it's a good idea to put the
> > regular gc marks in there as well (we'll need two to flip flop, I
> > think), so that we don't need to trot all over a bunch of heap
> > segments removing marks to prevent guile from seeing illegal values (I
> > learned that one the hard way ;).
> >
> 
> OK, how about:struct Cell_Info {    int generation:8;
>     int car_newer:1;
>     int car_older:1;
>     int cdr_newer:1;
>     int cdr_older:1;
>     int gc_mark:1;
>     int hunoz:3;
>     };
> 
>  struct Chunklet {   /*  sizeof(Chunklet) == 128 */
>     Cell_Info cell_info[12];
>     Cell cells[12];
>     char any_out;
>     char junk[7];
>    };
> 
> Another possibility is 25 cells per chunklet, which wastes only 4 cells.
> Basically pick some n such that 10*n + 2 is near but less than a power of 2.
> The larger n is the more probable any_out will be set and you have to scan the
> chunklet.

I really like this, as well. I do have a vague, nagging suspicion that
it's missing for some out of heap objects, but I want to investigate
this a bit further, to make sure that problems I had initially (with
the vector per segment approach) were from a buggy implementation
(which it certainly was). Tenatively, I think this is the best way to
do it, since it is a very good tradeoff between mem usage and time.

> I briefly considered putting mark bits in the Cell_Info, but thought the less
> disruption to the rest of guile the better.  It does
> make unmarking in the sweep phase less disruptive, though.  Could you elaborate
> on why a second mark bit might be needed?

Basically, if we want to be able to leave a gc mark, and don't remove
them, we also need to be able to distinguish a dead gc mark from a
live . My thinking here was that we could flip between the two gc
marks each time we leave a mark on an object during a particular
collection, in a particular generation. I think this is might only be
useful when doing a full mark phase (I'm intending to have both as
options, in the cases where a write barrier turns out to be more
expensive than just tracing the live objects). In this case, if we are
collecting the 10th generation, we do a full scan using the first gc
bit. On the next gc, during the mark phase, we set the second mark,
and any objects in the segments we are collecting that don't have the
second bit set are thrown out. It's also enough to facilitate the tree
colouring algorithms that usually make up an incremental collector (so
one could probably be plugged in without requiring another change to
heap objects).

It shouldn't be disruptive for the rest of guile, since the only real
interface to marks is via the SCM_GCMARK things, so it'll never notice
that the marks aren't on the objects anymore.

> > An improvement here is to keep at least some minimal information on a
> > per segment basis (where we could point... it's not perfect, but
> > avoids some unnecessary scanning). The part we really want to avoid is
> > scans through any large amount of heap space, because this is almost
> > always going to cost more than tracing live objects.
> >
> 
> Well, if segments aren't too big we could keep a bit map of the any-out flags on
> a segment basis.  That could greatly accelerate scanning a segment if there were
> few pointers leading out it.  It would slow down the write barriersomewhat,
> though.

I was thinking more along the lines of a per segment list that
contained the possible generations this segment could have objects
pointing to. For example, when we're collecting generation 2, we only
have to scan over segments that have generation 2 in their
possible_pointers list. Then, we can take the time to jump through the
segment, checking for pointers (if we don't find one, we beat up the
segment for lying to us, and remove 2 from the possible pointers
list). A lot of this depends on the implementation of the write
barrier, though I think it could work well with this. 

> > > We may prematurely
> > > copy some babies created at the end of the cycle that will soon become
> > > garbage.
> >
> >
> > This can still be avoided by keeping a bit per object in the incubator
> > (I like that :), and moving them on if the bit is set (means a bit
> > more junk in the incubator, but we are talking about a very small
> > space, that won't be too difficult to scan). Or a second incubator
> > (probably better) that they have to live through to make it to the
> > heap proper. This is definately worth the mem, since the overhead for
> > an object that graduates is greater.
> >
> 
> I think the second incubator is a better idea; leaving them in the first would
> mean having to builda free list.

I agree. The first bit was only in there because it was the first
thing I thought of. 
 
> > 1) Normal 'scheme c' code will use something like SCM_ASSIGN(x, val),
> >    rather than x=val.
> 
> What's SCM_ASSIGN?  My (rather outdated now) sources don't mention it.


Possibly what will be required in c code with a write barrier, to do
the appropriate calculations. Not looking at the first letter right
now, I'm not quite sure how I fell into talking about the write
barrier (the dangers of rambling).
 
> > 2) User smobs will have to take special care when they can contain
> >    pointers to the heap
> >
> 
> Won't the required call to scm_gc_mark handle this?

Not for alerting the write barrier of the location of possible
pointers. We can't catch these otherwise, since they're outside the
heap. 

> > My inclination is to make all segments small (currently, a small
> > multiple of the page size, though it can go to the page size
> > itself).
> 
> I would agree with this.
> 
> > Would it be alright with you if I put up your mail on my guile page?
> > There's certainly enough here that it will take a while for me to
> > integrate the ideas with the notes (is that ok, as well?)
> >
> 
> Go for it.  I'm happy to contribute any way I can.
> 

Great!

-- 
Greg