Interior pointers and fast GC

[Araq via Digitalmars-d]

On Sunday, 22 January 2017 at 06:28:35 UTC, Chris Wright wrote:
> On Sun, 22 Jan 2017 05:02:43 +0000, Araq wrote:
>> It's an O(1) that requires a hash table lookup in general 
>> because allocations can exceed the chunk size and so you 
>> cannot just mask the pointer and look at the chunk header 
>> because it might not be a chunk header at all. Know any 
>> production GCs that use hash table lookups for pointer 
>> assignments? Me neither. Ok ok, maybe Go does, it's the only 
>> language with GC that embraces interior pointers as stupid as 
>> that is.
>
> Overexplaining because I'm tired.
>
> If you have fixed-size allocations, you get much better time: 
> O(log #pools) to find the pool, O(1) to find the offset in that 
> pool. The cost is you multiply the number of pools in existence 
> by the number of allocation sizes you decide to support.
>

Sure, O(log #pools) + O(1) is "much better" than O(1).

To shorten the discussion: You're looking for a variant of "card 
marking". No overhead for interior pointers if you do it right. I 
think, never worked out the details though.

http://stackoverflow.com/questions/19154607/how-actually-card-table-and-writer-barrier-works