Transitioning to a type aware Garbage Collector

[Pragma]

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.

Example (16 bit list):
0000 0000 0000 0000 - zero = no pointers present
0000 0000 0000 1001 - pointers at offsets 0 and 12
1111 1111 1111 1111 - max = I'm all pointers
1000 0000 1000 0001 - pointers at offsets 0 and 28, and force scan at offsets 60 through end of block.

Another option would be to make the resolution of the high-order bits more logarithmic, making it behave something like 
a bloom filter.

> 
>> And if it's just a bool, what was the reasoning behind this decision?
>> Ease of implementation? The overhead of the metadata needed to get to 
>> mostly-precise? All of the above?
> 
> It's a fairly significant improvement for a small change.


-- 
- EricAnderton at yahoo