 |
lua-l archive |
|
|
||
|
On Tuesday, August 27, 2002, at 10:37 AM, Thatcher Ulrich wrote:
On Aug 27, 2002 at 09:53 -0300, Roberto Ierusalimschy wrote:The idea is to keep separate lists for each type of object (thus eliminating the vtype variable) and not storing an explicit "marked" value -- instead, the marked status is determined by which list the object is linked into (white, gray, or black).Are you sure you can do that? You need a fast way to check the color of an object while running the mutator.Actually, I don't think you do -- IIRC with this algorithm, whenever you need to mark an object and you don't know its color, it's always correct to put it on the gray list.
I think you should mark it white in that case - gray means it's referenced, but may or may not itself reference a white.
That's just my recollection from the last time I worked on this, which was several months ago, so I could be mistaken.
I looked up tricolor gc on the web and it's a very cool algorithm. An efficient implementation is to have each object have two pointers - one to the next object of the same color, the other to the previous. So you have 3 linked lists(white, gray and black) and you move an object between lists to change it's mark. When the gray list is empty, you know you can free all the whites. The drawback from mark and sweep is that you use a few each bytes per object and you need to track when object links change.
Steve