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.
