View mode: basic / threaded / horizontal-split · Log in · Help
December 26, 2011
Reference counted containers prototype
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
December 26, 2011
Re: Reference counted containers prototype
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/
December 26, 2011
Re: Reference counted containers prototype
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
December 26, 2011
Re: Reference counted containers prototype
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
December 27, 2011
Re: Reference counted containers prototype
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.
December 27, 2011
Re: Reference counted containers prototype
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.
December 27, 2011
Re: Reference counted containers prototype
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.
December 27, 2011
Re: Reference counted containers prototype
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.
December 27, 2011
Re: Reference counted containers prototype
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
December 27, 2011
Re: Reference counted containers prototype
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
« First   ‹ Prev
1 2 3 4 5
Top | Discussion index | About this forum | D home