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.
