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.
