Interior pointers and fast GC

deadalnix via Digitalmars-d digitalmars-d at puremagic.com
Sat Jan 21 09:42:46 PST 2017


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.


More information about the Digitalmars-d mailing list