Re: Why does the garbage collector use a giant ring instead of lists?

Thanks for tip about the whitepaper.  I was trying to understand the Io garbage collector based on Dijkstra's original three color garbage collection paper, and getting rather confused at the parts of the algorithm that didn't match up.

By the way, in the end it turned out there was no bug in the GC after all (my original impetus for digging into the GC code).  The bug I had was that I was accidently creating the same C++ object twice (in an Io script).  Letting the original object slot get updated with the second instance allowed the first instance to become garbage, although the C++ half of my system still held a pointer to it.  It was fiendishly hard to debug because I didn't know until some careful pointer value inspection there were really two objects in play; what I thought I was observing was "object was marked" and "object gets collected" and both could not possibly be true at once for a single object.

--- In [email protected], Steve Dekorte <steve@...> wrote:
>
> 
> Off hand, I don't recall exactly - it may simplify the implementation. 
> You might check out Henry Baker's paper "The treadmill: real-time garbage collection without motion sickness" and see if there was a good reason.
> 
> On 2011-07-13 Wed, at 07:22 PM, dennisf486 wrote:
> > So I'm digging into the garbage collector trying to debug this strange problem with my Io block() object created in a do() getting freed even though my C++ code is consistently marking it.  There's a surprisingly small amount of code that implements Io's garbage collector.  There's one thing I don't understand though - what I at first took to be linked lists for the list of white, gray, black, and freed objects is not really linked lists, it's rings.  In fact, instead of four separate lists (or rings) all four colors are in one giant ring, and the list "heads" are just pointers into the ring.
> > 
> > My first clue was I expected COLLECTMARKER_FOREACH would be implemented like:
> > while (v->next != NULL) ...
> > 
> > but instead I found this:
> > while (v->color == c) ...
> > 
> > So, you could think of the structure as being like a big bracelet, and you count beads until you reach a band of a different color.  Although it conjures an interesting mental picture, it seems like a bizarre engineering choice.  What advantage is gained by doing this, versus just keeping them in four completely separate linked lists and using NULL to mark the end of the list?
> >
>