Interior pointers and fast GC

[Araq via Digitalmars-d]

On Saturday, 21 January 2017 at 17:42:46 UTC, deadalnix wrote:
>
> 1. Split the heap in chunk of size n being a power of 2, say 
> 4M. Align them 4M.
> 2. Find the chunk an alloc is part of in O(1) bu masking the 
> lower bits (22 bits to mask in our 4M case).
> 3. Have a table of page descriptor in the chunk header. Lookup 
> the page the alloc is in in O(1).
> 4a. If the alloc is large (flag in the page descriptor), find 
> the base pointer in O(1).
> 4b. if the alloc is small, compute the index of the item in the 
> page from the size class in the page descriptor (on addition, 
> one multiply and one shift) in O(1).
>
> Start on false premise, end up nowhere.

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.