Transitioning to a type aware Garbage Collector

[Frits van Bommel]

Pragma wrote:
> Walter Bright wrote:
>> Frits van Bommel wrote:
>>> Walter Bright wrote:
>>>> Paul Findlay wrote:
>>>>> Walter Bright wrote:
>>>>>> To improve GC performance, we need to transition to a GC that is 
>>>>>> aware of the types of what it is allocating.
>>>>> Does this mean the D garbage collector will be an exact (or 
>>>>> precise) garbage collector?
>>>>
>>>> No.
>>>
>>> So what exactly *does* it mean?
>>> Is it, as Pragma put it, a "bool containsPointers" per block?
>>> Or is it mostly-precise?
>>>
>>> "Not exact/precise" still leaves a pretty big range...
>>
>> All it means is that a bit gets set per block meaning if it might 
>> contain pointers or does not contain pointers. In the future, it might 
>> give a list of which offsets contain pointers.
> 
> Just shooting from the hip here: one possibility for such a list that 
> won't eat much space would be having each bit of a word (or dword) 
> represent the presence of a pointer at that 4-byte offset.  The last bit 
> set could just signify "this is a big object, conservatively scan beyond 
> bits*4 bytes".  This would take advantage of the fact that most objects 
> typically aren't very big.

I think there should also be a way to annotate as "array, repeat". This 
would likely be useful since big objects are likely to be arrays.
This would require one bit for a flag and some way to note the element 
size, though.
If we go by the assumption that most structs/unions aren't very big, 
that could perhaps be implemented as a byte total: 1 bit = flag, 7 bits 
= size - 1 (since 0-length elements aren't useful anyway :) ) would 
allow elements up to 128 bytes, which should cover most arrays.

If we want no more than 4 bytes of meta-info[1], that would leave 23 
bits for pointer flags and one "big object/element" flag. Objects up to 
95 bytes could then be specified exactly (23 * 4 + 3 bytes, the last 3 
of which can't contain a pointer).

And yes, that's the optimum with these parameters; moving 1 bit from 
size to pointer flags leaves the size at a max of 64, which is under 95.

For 8 bytes of meta-info[2], the optimum would be
8 bits of elt/object size
1 bit array flag
1 bit big object flag
54 bits pointer flags
max exactly-specified size: 219 (54 * 4 + 3)


[1]: That's the minimum alignment for anything containing pointers on 32 
bit systems. This would allow it to be put at the start of the block 
without padding for align(4) contents.
[2]: Minimum align of anything containing ptrs on 64 bit systems 
(presumably). Can of course also be used on 32 bit systems; IIRC doubles 
and structs containing them already have align(8) as default.


[...]


Wait... Since size == 0 is useless, we can also use *that* as "big" 
'flag'. That would mean:
32 bits: 1 + 7 + 24, max exact size: 99
64 bits: 1 + 8 + 55, max exact size: 223

And if the array bit is 0, you can use the size bits as extra pointer 
flags (and one for the "big" flag), allowing normal objects up to 
123/251 bytes for 32/64 bits, respectively.


</obsess over details>