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).
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.
http://stackoverflow.com/questions/19154607/how-actually-card-table-and-writer-barrier-works
