Interior pointers and fast GC

[deadalnix via Digitalmars-d]

On Sunday, 22 January 2017 at 05:02:43 UTC, 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.

Huge allocs are always handled specifically by allocators. The 
usual technique is via a radix tree. But it doesn't really matter 
for the discussion at hand: huge alloc are not numerous. If you 
have 4G of RAM, by definition, you need to have less than a 1000 
of them with he above mentioned scheme. The whole lookup 
datastructure can fit in cache.