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.

Andrei

On 2011-12-26 17:25:10 +0000, Andrei Alexandrescu <SeeWebsiteForEmail@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@michelf.com
http://michelf.com/

On 12/26/11 12:46 PM, Michel Fortin wrote:
> 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.

Does the current implementation unfreezes all threads before calling the destructors? If so, indeed there's a race.

BTW, the plan is to have the same thread that constructed objects to call their destructors; each thread would have a worklist of garbage objects to destroy. The list can be reduced during calls to allocation functions within each thread, and of course when the thread terminates.


Andrei

On Monday, 26 December 2011 at 17:25:12 UTC, Andrei Alexandrescu wrote:
> 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.
>
> Andrei

Maybe the fact that the container is duplicated on opDispatch call time and not on assignment time could be confusing to at least developers coming from c++. It does benefit from lazy duplication by doing it this way which might justify it.

Otherwise it seems good.

/Jonas

On 26/12/11 5:25 PM, Andrei Alexandrescu wrote:
> (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.

I have a separate, but very much related concern:

If the held object has a method with the same name as RefCounted (e.g. asConst) then how do you call the held object's method instead of RefCounted's method?

I've always felt very suspicious of opDispatch. It seems like exactly the kind of thing that seems good when you look at simple cases, but would cause subtle problems when used in conjunction with other D features (e.g. UFCS).

I'm not yet convinced that opDispatch has been thoroughly explored enough to be used in such a fundamental part of the standard library.

On Mon, 26 Dec 2011 17:09:02 -0800, Peter Alexander <peter.alexander.au@gmail.com> wrote:

> On 26/12/11 5:25 PM, Andrei Alexandrescu wrote:
>> (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.
>
> I have a separate, but very much related concern:
>
> If the held object has a method with the same name as RefCounted (e.g.
> asConst) then how do you call the held object's method instead of
> RefCounted's method?

You, can't. Looking at the source code asConst is a private member function and therefore, given we are using opDispatch for forwarding, these methods should have _ or __ prepended onto them.

> I've always felt very suspicious of opDispatch. It seems like exactly
> the kind of thing that seems good when you look at simple cases, but
> would cause subtle problems when used in conjunction with other D
> features (e.g. UFCS).
>
> I'm not yet convinced that opDispatch has been thoroughly explored
> enough to be used in such a fundamental part of the standard library.

There are several uses for opDispatch. For example, vector swizzling is an example of using opDispatch to replace a finite set of related functions. General forwarding, like alias this, requires a minimalistic design: the public interface should be as small as reasonable and the private functions should never use a 'good' function name.

On 27/12/11 1:09 AM, Peter Alexander wrote:
> On 26/12/11 5:25 PM, Andrei Alexandrescu wrote:
>> (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.
>
> I have a separate, but very much related concern:
>
> If the held object has a method with the same name as RefCounted (e.g.
> asConst) then how do you call the held object's method instead of
> RefCounted's method?
>
> I've always felt very suspicious of opDispatch. It seems like exactly
> the kind of thing that seems good when you look at simple cases, but
> would cause subtle problems when used in conjunction with other D
> features (e.g. UFCS).
>
> I'm not yet convinced that opDispatch has been thoroughly explored
> enough to be used in such a fundamental part of the standard library.

Following up to this, how do I access non-function members of the held object? e.g.

struct Foo
{
    int x = 1;
}

void main()
{
    RefCounted!Foo f;
    writeln(f.x); // Doesn't work
}


Also, what about template member functions of the held object?

struct Foo
{
    int get(int X)() { return X; }
}

void main()
{
    RefCounted!Foo f;
    writeln(f.get!123()); // Doesn't work either
}


I must admit that I haven't played around much with opDispatch, but neither of these appear to work with the current implementation, and that's a complete deal-breaker for me. Hopefully I'm just missing something though.

On 27/12/11 1:14 AM, Robert Jacques wrote:
> On Mon, 26 Dec 2011 17:09:02 -0800, Peter Alexander
>> If the held object has a method with the same name as RefCounted (e.g.
>> asConst) then how do you call the held object's method instead of
>> RefCounted's method?
>
> You, can't. Looking at the source code asConst is a private member
> function and therefore, given we are using opDispatch for forwarding,
> these methods should have _ or __ prepended onto them.

Identifiers starting with __ are reserved, which leaves you with _, which could be used by the held object also.


>> I've always felt very suspicious of opDispatch. It seems like exactly
>> the kind of thing that seems good when you look at simple cases, but
>> would cause subtle problems when used in conjunction with other D
>> features (e.g. UFCS).
>>
>> I'm not yet convinced that opDispatch has been thoroughly explored
>> enough to be used in such a fundamental part of the standard library.
>
> There are several uses for opDispatch. For example, vector swizzling is
> an example of using opDispatch to replace a finite set of related
> functions. General forwarding, like alias this, requires a minimalistic
> design: the public interface should be as small as reasonable and the
> private functions should never use a 'good' function name.

Stuff like swizzling is fine because you are just using it to generate other functions. Forwarding is what worries me because it has to cover absolutely *everything* and avoid namespace clashes in order to be useful.

On 12/26/11 7:09 PM, Peter Alexander wrote:
> On 26/12/11 5:25 PM, Andrei Alexandrescu wrote:
>> (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.
>
> I have a separate, but very much related concern:
>
> If the held object has a method with the same name as RefCounted (e.g.
> asConst) then how do you call the held object's method instead of
> RefCounted's method?

Good point. A convention I used successfully in the past was that all of RefCounted methods should have the RefCounted_ prefix in their name. I seem to recall Kenji or Shoo found a wicked technique to define and use "super-private" methods, but I need to find it. It's used somewhere in Phobos. But I think the convention of putting the name of the proxy in the methods of the proxy is powerful enough, anyway. It's a legit concern, but it can be addressed effectively.

> I've always felt very suspicious of opDispatch. It seems like exactly
> the kind of thing that seems good when you look at simple cases, but
> would cause subtle problems when used in conjunction with other D
> features (e.g. UFCS).
>
> I'm not yet convinced that opDispatch has been thoroughly explored
> enough to be used in such a fundamental part of the standard library.

No need to worry. The opDispatch and auto ref features have been _especially_ designed for allowing transparent forwarding. So they must work by definition - it's their primary role. They _will_ work. Think of it as a sort of anthropocentrism for opDispatch.

Already, I have been very surprised that opDispatch works for all cases it didn't work last time I tried it. The language implementation has improved by leaps and bounds.

=============

A question I have is container naming convention. Say we want to define a doubly-list structure in std.container.

1. Expose the unmanaged reference type (DListImpl in the example) and the managed reference as an alias. What naming convention?

2. Only expose the managed reference type (DList in the example) and disallow or at least discourage the use of DListImpl?

3. Only expose the unmanaged reference type (DListImpl) as e.g. DList, and let people who wanna reference counting use Refcounted!(DList!Whatevs) explicitly?

4. Something else?


Andrei

On 12/26/11 7:14 PM, Robert Jacques wrote:
> There are several uses for opDispatch. For example, vector swizzling is
> an example of using opDispatch to replace a finite set of related
> functions. General forwarding, like alias this, requires a minimalistic
> design: the public interface should be as small as reasonable and the
> private functions should never use a 'good' function name.

Yes, perfect.

Andrei