Interior pointers and fast GC

Chris Wright via Digitalmars-d digitalmars-d at puremagic.com
Sat Jan 21 22:28:35 PST 2017


On Sun, 22 Jan 2017 05:02:43 +0000, 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.

Overexplaining because I'm tired.

If you have fixed-size allocations, you get much better time: O(log 
#pools) to find the pool, O(1) to find the offset in that pool. The cost 
is you multiply the number of pools in existence by the number of 
allocation sizes you decide to support.

This obviously helps for structs and classes.

It also helps for small arrays: a small array is a fixed-size allocation 
that can potentially be reallocated.

For instance, I decide to support allocations of 16, 32, and 256 bytes. 
The string "A British tar is a soaring soul" fits into a 32-byte 
allocation, so I put it in the 32-byte pool.

If I append the string " as free as a mountain bird" to it, that no 
longer fits, so I copy it into the 256 byte pool and append there.

If you then take a slice from it, "a soaring soul", I can find the 
relevant pool by examining every pool (or by traversing a search tree). 
The pool says it's a 32-byte pool, so floor-32 of the pointer is the base 
pointer.

Large heap objects (anything above the maximum supported size, which will 
be about one OS page) don't afford this convenience -- they aren't of any 
particular size, so you still need to search through every allocation.

So the performance of D's GC is rather strongly dependent on how large 
arrays tend to get.

Unless I'm misunderstanding the GC yet again.


More information about the Digitalmars-d mailing list