RC and GC coexistence

[Oren Tirosh via Digitalmars-d]

On Sunday, 21 September 2014 at 00:45:49 UTC, deadalnix wrote:
> On Saturday, 20 September 2014 at 19:48:14 UTC, Oren Tirosh 
> wrote:
>> Hi everyone. Unlurking to make my first comment here.
>>
>> Here is an idea for making RC and GC coexist peacefully. I 
>> think this technique may be used to make the Throwable 
>> transition to RC while keeping full backward compatibility.
>>
>> A Throwable object would have a reference counter to track the 
>> number of RC references to it. It would also have a flag 
>> indicating whether there are any outstanding GC references to 
>> the object as well. This flag may be implemented by setting 
>> the MSB of the reference counter.
>>
>
> I was thinking about this recently (and also, Andrei's talk at 
> cppcon provided some interesting data).
>
> Most reference count are small. I think it make sense for us to 
> propose a ref count system, that allocate on the GC heap, and 
> that do not free when the counter saturate.

This is not what I was proposing. What you are describing (small,
saturating RC) is one of the  schemes mentioned in this article:

Shahriyar, Rifat, Stephen M. Blackburn, and Daniel Frampton.
"Down for the count? Getting reference counting back in the
ring." ACM SIGPLAN Notices. Vol. 47. No. 11. ACM, 2012.
http://users.cecs.anu.edu.au/~steveb/downloads/pdf/rc-ismm-2012.pdf

Reading this article is recommended for everyone here. It
demonstrates that advanced implementations of reference counting
systems are viable competition for GC and even outperform them
under certain workloads. The authors have implemented several
reference counting and hybrid schemes for the Java runtime and
benchmarked them. One of the schemes uses a small, saturating
reference counter in the object header similar to what you have
described.

> It would help to:
>  - get intrusive refcount without putting too much crap into 
> objects (it is all about cache line).
>  - get a way to escape RC object to the GC heap (by saturating 
> the refcount).

My idea is, indeed, to enable RC objects to be participate in
classic GC, but not by saturation. The MSB is, by definition, big
enough so the real reference count will not reach it. I suggest
using it as a flag to indicate whether there are any GC
references to the object. If clear, the object may be destroyed
when the counter reaches 0. If set, it means that a GC cycle is
still required to find if there are any more outstanding
references to it.

* No modification to the binary structure of Throwable. It
remains fully link-compatible with object files generated by
older compiler versions.
* "new Throwable" is modified to allocate extra space for a
counter just before the instance and returns a pointer just past
it. The counter is initialized to 0 with MSB set.
* The deallocator is modified to clear the counter MSB and
actually deallocate the object only if the counter is zero.

That's it for regular ("@gc") code.

In @nogc code, an alternative "new" is used that sets the counter
to 1 (MSB clear) and returns a pointer to the counter rather than
the instance that follows it. Whenver this reference is copied,
overwritten or goes out of scope the reference counter must be
updated and deallocated when it reaches 0. Dereferencing the
Throwable via this type of reference-counter pointer uses
different offsets to compensate for the presence of the counter.
This reference-counted reference may be automatically converted
to a regular pointer that is safely used in code not aware of
reference counting by setting the MSB of the reference counter
and incrementing the pointer to point to the instance. Taking the
address of a field inside an object referenced through a
reference-counter pointer is either disallowed or required to set
the counter MSB because reference counted references do not
support internal pointers and

This would provide full backward compatibility even with .o code
already compiled before the feature was introduced.

> The GC is still there, but do kick in randomly, it simply act 
> as a safety net.
>
> Also given the type qualifier in D, the whole synchronization 
> thing is embeded in the type, so we can be safe and fast on 
> that one. All of this can be done as library.

The point of my scheme is to ensure that a thread that contains
no GC references may be safely excluded from "stop the world"
when GC kicks in. This is currently the biggest "lie" in the D
story about GC being optional. While @nogc code will not trigger
collection, it is NOT excluded from random pauses caused by GC in
other threads.