Reference counted containers prototype

[Michel Fortin]

On 2011-12-26 17:25:10 +0000, Andrei Alexandrescu 
<SeeWebsiteForEmail at erdani.org> said:

> Hello,
> 
> 
> I've been playing with a new approach to reference counting, in 
> particular for the containers library.
> 
> A small prototype is at http://pastebin.com/WnSQY1Jw. The prototype 
> features a simple doubly-linked list implementation DListImpl. That is 
> not supposed to be manipulated directly (or it might, in case the user 
> wants a simple garbage collected implementation - this is a point in 
> the discussion).
> 
> DListImpl has only a couple of primitives implemented. The only 
> interesting points that it tries to make are:
> 
> (a) the presence of the dispose() primitive, which deallocates all 
> memory and brings the object back to its .init state
> 
> (b) the presence of the dup() primitive, which creates a full-blown 
> duplicate of the object.
> 
> The interesting part of the sample is RefImpl, which has a couple of 
> quite interesting details:
> 
> (a) All interaction with the held object is done via opDispatch. In 
> fact opDispatch can be engineered to statically enforce no reference to 
> the held object escapes.
> 
> (b) A const/immutable call against a non-existing is silently converted 
> into a call against a default-initialized object.
> 
> (c) If a call works and returns the same type for a non-const and a 
> const object, then the const version is preferred. This is to reduce 
> the number of calls to ensureUnique().
> 
> Destroy.

The overall design is quite sound and coherent. And you are cleanly 
separating the reference counting policy from the container's 
implementation. It fits with AAs. I also like that you can create a 
DListImpl without indirection (on the stack or as a struct member) or 
with a standard GC pointer if you so wish. So I don't see anything to 
complain about in this design. Although I am a little concerned by this 
small but important implementation detail:

Your RefCounted destructor is racy.

Just like other reference counted things in Phobos, if you somehow 
store a reference on the GC heap (as a class member for instance), the 
destructor for that reference struct is called from the GC thread and 
will decrement the counter from that thread, while another reference 
could play with the counter from another thread. I know you have plans 
for a general fix for that hole in destructors, but meanwhile it'd be 
wise to change the counter to a shared uint and use atomic operations 
to avoid low level races.


-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/