Idea #1 on integrating RC with GC

[Ola Fosheim Grøstad" <ola.fosheim.grostad+dlang at gmail.com>]

On Wednesday, 5 February 2014 at 15:01:27 UTC, Manu wrote:
> Or I wonder if there's opportunity to pinch a single bit from 
> pointers to
> mark that it is raw or RC allocated? Probably fine on 64bit.

Yes, on 64 bit that is ok. I think current x86 map something like 
53 bits, the top and bottom half of the 64 bit address space. The 
middle is unused. Anyway, you could have two heaps if the OS 
allows you to.

> 32bit probably needs to match a bit pattern or something.

Or one could forget about 32 bit for ARC.

> Aligned data is a challenge. I have often wondered if it would 
> be feasible
> to access the RC via a pointer hash or something, and keep it 
> in a side
> table... sounds tricky, but I wonder if it's possible.

If you have your own allocator you probably could? Segment memory 
regions into allocations of a particular size and have a RC-count 
index at the start indexed by the masked MSBs of the pointer 
address and have smart pointers that know the object size. Kind 
of tricky to get acceptable speed, but possible to do. The 
problem is that you will get a latency of perhaps 200+ cycles on 
a cache miss. Then again, you could probably make do with 32 bit 
counters and they are probably accessed in proximity if they hold 
the same type of object. One cache line is 64 bytes, so you get 
16 counters per cache line. With smart allocation you might get 
good cache locality of the counters (8MB of L3 cache is quite a 
bit).

(I guess alignment is primarily a problem when you want 4KiB 
alignment (page size), maybe not worth worrying about.)

> Rather than (allocated_base, offset), I suspect (pointer, 
> offset_from_base)
> would be better; typical dereferences would have no penalty.

Yes, probably. I was thinking about avoiding GC of internal 
pointers too. I think scanning might be easier if all pointers 
point to the allocation base. That way the GC does not have to 
consider offsets.

> You mean like the smart pointer double indirection? I really 
> don't like the
> double indirection, but it's a possibility. Or did I 
> misunderstand?

Yes:

struct {
     void* object_ptr;
     /* offset */
     uint weakcounter;
     uint strongcounter;
}

The advantage is that it works well with RC ignorant 
collectors/allocators. "if in doubt just set the pointer to null 
and forget about freeing".

> I'm sure there's a clever solution out there which would allow 
> the ARC to
> detect if it's a raw C pointer or not...

Well, for a given OS/architecture you could probably always 
allocate your heap in a fixed memory range on 64 bit systems then 
test against that range.