On Saturday, 14 January 2017 at 04:37:01 UTC, Chris Wright wrote:
Unfortunately, given an interior pointer, you can't identify the base of its heap object in constant time.
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.
