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
