More precise GC

[Robert Jacques]

On Sun, 28 Mar 2010 12:32:22 -0300, bearophile <bearophileHUGS at lycos.com>  
wrote:
> Robert Jacques:
>
>> This would require structs/arrays/etc to contain a header with a vtable,
>> so the GC could know what to do.
>
> Do you mean a vtable pointer? Can you explain me why this is necessary?

Yes. What I think you're forgetting is that all compile-time type info is  
lost at runtime. All the GC knows about Node is that it's 16-bytes, it  
doesn't have an object finalizer and it contains pointers somewhere.  
Hopefully, in the future, it'll even know where those pointers are. But  
that's it. It doesn't know that that 16-byte memory chunk is a Node or  
that a gcfollow method exists. This is one reason struct destructors don't  
run when you allocate them on the heap: the GC simply doesn't know about  
any function to run. Naturally, this also applies to arrays and value  
types. So if you want to add type specific GC stuff, you have to add  
type-specific headers to each memory chuck.

>> remember, the GC allocates on
>> 16-byte boundaries so each Node* actually has 4-bits (8 total) in which  
>> to
>> hide an enum.
>
> They can't be used, the D specs say that pointers to memory managed by  
> the GC can't be used to store flags (so I too was wrong in an answer to  
> another person), probably because they are used by the garbage to color  
> the graph in two or three colors.
>
> Bye,
> bearophile

No, what you can't do is hide flags in high order bits or use tricks like  
XOR to store two pointers in a single field. The 4 low order bits are fair  
game: adding 0-15 to the base pointer with still cause the struct to be  
properly marked. As for using those bits for the mark colors; A) D  
supports pointers to bytes, so the GC has to leave those bits alone. B)  
D's GC isn't precise and has no clue what are pointers and what aren't, so  
it can't use pointers in this fashion. C) The color bits apply to the  
object pointed to, not the pointer pointing to it.