Interior pointers and fast GC

[Rainer Schuetze via Digitalmars-d]

On 14.01.2017 05:37, Chris Wright wrote:
> Interior pointers are a barrier to performant garbage collection.
>
[...]
>  * In a binary search tree, a prefix tree, or the like
[...]
> The third strategy is O(log N) in the expected case and has similar data
> locality to the hashtable.
>
> Obviously, we prefer the first strategy. Unfortunately, given an interior
> pointer, you can't identify the base of its heap object in constant time.
> I believe D's garbage collector uses a binary search tree.
>
> D allows unrestricted interior pointers. This makes it difficult to
> experiment with other garbage collectors, except for those designed for D
> or C++.

The garbage collected memory is organized as pools of growing size. For 
each pool there are lookup tables for each page that has fixed sized 
memory blocks. That way finding the base of an allocation is a matter of 
finding the pool (currently O(log #pools); by N I assume you mean the 
number of allocations) but the rest is constant time.

IIRC an application that uses 1 GB of memory has about 20 pools, which 
means the time to figure out the base address and the size of an 
allocation is more or less constant.

In addition, you need to lookup the pool anyway to figure out if the 
pointer points to non-managed memory (stack, global data, malloc'd memory).

So, I don't think interior pointers are a performance problem of D's GC. 
Other GCs might not be able to deal with these, though.

The much larger problem with trying more sophisticated GCs is the lack 
of a fast write barrier. If we get one with compiler assisted 
(automatic) reference counting, we might aswell try this for other types 
of GC.