Interior pointers and fast GC

[Chris Wright via Digitalmars-d]

On Sun, 22 Jan 2017 06:44:47 +0000, Araq wrote:

> On Sunday, 22 January 2017 at 06:28:35 UTC, Chris Wright wrote:
>> 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.
>>
>>
> Sure, O(log #pools) + O(1) is "much better" than O(1).

Much better than what's available today, unless I misunderstood the 
current GC again.

A tree lookup with < 100 elements in the tree won't be much slower than a 
hashtable lookup with O(# pages allocated) entries in the table. If you 
control virtual memory more strictly (and have virtual memory to burn -- 
so not on 32-bit), you can put a better constant on the hashtable lookup.

> To shorten the discussion: You're looking for a variant of "card
> marking". No overhead for interior pointers if you do it right. I think,
> never worked out the details though.

Card marking is about write barriers. Write barriers are about 
incremental collection, caching part of your past GC run information so 
you can update it using only those pages of memory that have changed 
since last time. It's low granularity because it's essentially free to 
read an entire page of memory once you've read one byte. It's also low 
granularity because one common strategy is to mprotect(3) the pages as 
read-only and install a fault handler, which is an expensive way of doing 
things that you want to repeat fewer times if possible.

It's not what I'm looking for.