[RFC]Proposal for better garbage collection

[Benjamin Thaut]

Am 22.02.2012 22:32, schrieb H. S. Teoh:
> On Wed, Feb 22, 2012 at 07:56:15PM +0100, Benjamin Thaut wrote:
> [...]
>> 2) Tracking references on the stack:
>>
>> The D compiler always needs to emit a full stack frame so that the
>> GC can walk up the stack at any time in the program. The stack frame
>> of every function generated by the D compiler starts which a
>> bitfield (usually the size of a machine register) where each bit
>> indicates that these bytes are a pointer / reference. The bitfield
>> needs to be large enough to cover the whole stack frame of the
>> function.
> [...]
>
> I was thinking about this a bit more, and I had an idea: why bother with
> storing bitfields on the stack? Any function's local pointer variables
> are known at compile-time. So store a function ID (probably a pointer)
> that maps to some static storage where this information is stored. Then
> we always only need 1 word of extra storage on the stack frame, and the
> GC can follow the pointer to get the info it needs. A recursively called
> function won't incur the cost of duplicated copies of bitfields, its ID
> points to same place. You can even have two different functions share
> the same ID if they have pointer variables in exactly the same places.
>
> The static storage can then be an array of relative stack offsets to the
> function's pointer variables, so the GC can easily use this info to find
> roots. No need to complicate the GC with manipulating bitfields, it's
> just an int[].
>
> If you want to get fancy, have the compiler reorder local variables so
> that pointers are clustered together in blocks, then in the static
> storage you can just encode pointer blocks by offset+length. (Although
> this may not help much with (pointer,length) pairs on the stack, like
> slices.) Or the compiler can reorder variables to maximize ID merges.
>
> The same thing can be done for scopes, since their local variables are
> also all known at compile-time.
>
>
> T
>

But where would you know from which scope variables are still (or 
already) valid and which are not?

void func()
{
   void* ptr = gc.alloc(...);
   //Ptr2, Ptr3 not valid yet
   void* ptr2 = gc.alloc(...);
   //ptr3 not valid yet
   {
     void* ptr3 = ptr1;
   }
   //ptr 3 not valid anymore
}

Also as the bitfiel is stored on the stack it will most likely ba 
already in the cache. Whereas with your approach scanning 1 stackframe 
would very likely also cause 1 cache miss because of the additional 
indirection. So if you are scanning 30 stack frames it will cause 30 
cache misses.

-- 
Kind Regards
Benjamin Thaut