www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Reference counted containers prototype

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 26 2011
next sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
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/
Dec 26 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 26 2011
parent reply deadalnix <deadalnix gmail.com> writes:
Le 26/12/2011 20:49, Andrei Alexandrescu a écrit :
 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

This is nice for thread local data, but does it make sense for immuables/shared ? I'm not sure this design is secure regrading GC. What happen if the destructor of the RefCounted is called, (and will call dispose) and then the payload is destructed. We have a risk of double destruction.
Dec 27 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/27/11 5:43 AM, deadalnix wrote:
 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

This is nice for thread local data, but does it make sense for immuables/shared ?

Yes - when the GC reaps objects, they are past their useful lifetime so their qualifiers are gone.
 I'm not sure this design is secure regrading GC. What happen if the
 destructor of the RefCounted is called, (and will call dispose) and then
 the payload is destructed. We have a risk of double destruction.

I'm not sure I understand the scenario. Andrei
Dec 27 2011
parent deadalnix <deadalnix gmail.com> writes:
Le 27/12/2011 16:06, Andrei Alexandrescu a écrit :
 On 12/27/11 5:43 AM, deadalnix wrote:
 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

This is nice for thread local data, but does it make sense for immuables/shared ?

Yes - when the GC reaps objects, they are past their useful lifetime so their qualifiers are gone.

I'm 100% convinced that the GC should be aware of type qualifier. this lead to many possible optimizations, and can be simply ignored when not required.
 I'm not sure this design is secure regrading GC. What happen if the
 destructor of the RefCounted is called, (and will call dispose) and then
 the payload is destructed. We have a risk of double destruction.

I'm not sure I understand the scenario.

OK, let's use an exemple, this is usually easier to understand. You have something of type T with a destructor, and I'll call it Patrick. And a RefCount struct pointing to it. Let's consider the RefCount struct is on the heap and garbage collected. Yes, I know, this is useless but possible so this have to be considered. Now, the garbage collector run, and will mark both memory location to be deleted : Patrick and the RefCount struct. The RefCount, will call dispose on the something and the GC will call dtor on Patrick. You'll never know in which order and so you can ends up calling dispose on a destructed object. Or destruct something used in the destructor in dispose. This is confusing. Let's put in the fact that you cant to run thoses in the thread that created them and you possibly ends-up with something quite confusing. I think the dtor should be the only way to destruct something and not the dispose method, and we have to ensure that the dtor is called by the GC.
Dec 27 2011
prev sibling next sibling parent "jdrewsen" <jdrewsen nospam.com> writes:
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
Dec 26 2011
prev sibling next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
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.
Dec 26 2011
next sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
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.
Dec 26 2011
next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
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.
Dec 26 2011
next sibling parent reply deadalnix <deadalnix gmail.com> writes:
Le 27/12/2011 08:00, Robert Jacques a écrit :
 On Mon, 26 Dec 2011 17:30:54 -0800, Peter Alexander
 <peter.alexander.au gmail.com> wrote:

 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.

Yes, in theory, but no in practice. It's perfectly possible to use __name or __name__ in user code, just highly not recommended. And while I'd never do that in my user code, I think the runtime and the standard library should be able to use __ (or maybe ___) when needed.

+1 It is reasonable that standard lib and compiler could agree on keywords they use.
Dec 27 2011
next sibling parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 27/12/11 12:15 PM, Froglegs wrote:
 What is wrong with value containers? They work great in C++, a container
 is such a basic thing that ref counting and whatnot is rarely if ever
 needed, and in the unlikely event you need to share a container,
 wrapping it with a smart pointer of some sort is easy enough in C++, let
 alone D with its better support for type aliasing.

There's not much point in having value containers if you just pass them around by reference all the time (as you do in C++). If you treat them like reference types then they should be reference types.
Dec 27 2011
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/27/11 6:15 AM, Froglegs wrote:
 When I go to that link it just says

 Unknown Paste ID!

 Don't see any code anywhere.. hum




 What is wrong with value containers? They work great in C++, a container
 is such a basic thing that ref counting and whatnot is rarely if ever
 needed, and in the unlikely event you need to share a container,
 wrapping it with a smart pointer of some sort is easy enough in C++, let
 alone D with its better support for type aliasing.

Value containers are almost never used as values. Code that does manipulate them as values, e.g. void fun(vector<int> v); is technically correct but automatically suspicious and raises questions. (It only passes a code review at Facebook if the implementation of fun does need in fact a mutable temporary vector inside, which is rare.) There is only one place where C++ value containers work well, and that's as members inside value objects. But then those objects in turn must be effectively manipulated as references... Andrei
Dec 27 2011
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2011-12-27 02:30, Peter Alexander wrote:
 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.

It's not enforced by the compiler. -- /Jacob Carlborg
Dec 27 2011
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 26 2011
prev sibling parent Joshua Reusch <yoschi arkandos.de> writes:
Am 27.12.2011 02:14, schrieb Robert Jacques:
 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.

You can: container.opDispatch!"asConst"();
Dec 27 2011
prev sibling next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
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.
Dec 26 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/26/11 7:25 PM, Peter Alexander wrote:
 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
 }

We can easily have opDispatch look at field names. But I think it's poor design to expose bald data anyway.
 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
 }

This is a problem. Andrei
Dec 26 2011
next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 27/12/11 1:29 AM, Andrei Alexandrescu wrote:
 We can easily have opDispatch look at field names. But I think it's poor
 design to expose bald data anyway.

I disagree, especially with immutable structs. There's no point wrapping immutable data in functions or properties.
 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
 }

This is a problem.

I would recommend postponing any major additions to Phobos that use opDispatch to forward calls until it has been investigated in full. I am not convinced that it can be used seamlessly without some relatively large changes to the language. Another potential problem of the top of my head: what about operator overloads on the held object? Just forward from opUnary/opBinary etc.? What about held objects that overload opAssign? What if the held object is itself a RefCounted?
Dec 26 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/26/11 8:23 PM, Peter Alexander wrote:
 On 27/12/11 1:29 AM, Andrei Alexandrescu wrote:
 We can easily have opDispatch look at field names. But I think it's poor
 design to expose bald data anyway.

I disagree, especially with immutable structs. There's no point wrapping immutable data in functions or properties.

Good point. It can be done. Embedded type aliases are more of a problem, but still doable. For example say DListImpl defines a type DListImpl!(T).Range inside - that should be accessible also as DList!(T).Range.
 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
 }

This is a problem.

I would recommend postponing any major additions to Phobos that use opDispatch to forward calls until it has been investigated in full.

We're a long way from adding to Phobos, so no need to worry.
 I am
 not convinced that it can be used seamlessly without some relatively
 large changes to the language.

I repeat that opDispatch and auto ref were invented for this, so anything that doesn't work now is a bug. There are no changes needed to the language, only fix the bugs :o).
 Another potential problem of the top of my head: what about operator
 overloads on the held object? Just forward from opUnary/opBinary etc.?

Will work.
 What about held objects that overload opAssign?

Already works.
 What if the held object is itself a RefCounted?

Well I'd say it should all work as expected! Andrei
Dec 26 2011
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 27/12/11 3:05 AM, Andrei Alexandrescu wrote:
 On 12/26/11 8:23 PM, Peter Alexander wrote:
 I am
 not convinced that it can be used seamlessly without some relatively
 large changes to the language.

I repeat that opDispatch and auto ref were invented for this, so anything that doesn't work now is a bug. There are no changes needed to the language, only fix the bugs :o).

How do you call template member functions of the held object without changing opDispatch?
Dec 27 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/27/11 4:32 AM, Peter Alexander wrote:
 On 27/12/11 3:05 AM, Andrei Alexandrescu wrote:
 On 12/26/11 8:23 PM, Peter Alexander wrote:
 I am
 not convinced that it can be used seamlessly without some relatively
 large changes to the language.

I repeat that opDispatch and auto ref were invented for this, so anything that doesn't work now is a bug. There are no changes needed to the language, only fix the bugs :o).

How do you call template member functions of the held object without changing opDispatch?

The idea is to pass the entire template instantiation as the string. obj.foo!(bar, baz)(a, b); -> obj.opDispatch!("foo!(bar, baz)")(a, b); Andrei
Dec 27 2011
next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 27/12/11 3:10 PM, Andrei Alexandrescu wrote:
 On 12/27/11 4:32 AM, Peter Alexander wrote:
 On 27/12/11 3:05 AM, Andrei Alexandrescu wrote:
 On 12/26/11 8:23 PM, Peter Alexander wrote:
 I am
 not convinced that it can be used seamlessly without some relatively
 large changes to the language.

I repeat that opDispatch and auto ref were invented for this, so anything that doesn't work now is a bug. There are no changes needed to the language, only fix the bugs :o).

How do you call template member functions of the held object without changing opDispatch?

The idea is to pass the entire template instantiation as the string. obj.foo!(bar, baz)(a, b); -> obj.opDispatch!("foo!(bar, baz)")(a, b); Andrei

I don't believe this will work in general when the template parameter passed in requires name look-up in the local scope. struct Foo { int bar(alias f)() { return f(); } } void main() { static int fun() { return 1; } RefCounted!Foo foo; writeln(foo.bar!fun()); // "fun" isn't in scope when mixed in. }
Dec 27 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/27/11 9:34 AM, Peter Alexander wrote:
 I don't believe this will work in general when the template parameter
 passed in requires name look-up in the local scope.


 struct Foo
 {
 int bar(alias f)() { return f(); }
 }

 void main()
 {
 static int fun() { return 1; }

 RefCounted!Foo foo;
 writeln(foo.bar!fun()); // "fun" isn't in scope when mixed in.
 }

That is a problem. Andrei
Dec 27 2011
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/28/11 12:59 AM, Robert Jacques wrote:
 I would have thought that the template parameters would be passed to
 opDispatch i.e.

 obj.opDispatch!("foo",bar,baz)(a,b);

 although I don't know how opDispatch would be written to handle such a
 call in a generic manner, i.e. I would want to define it as

 obj.opDispatch!(string name, Targs..,Vargs..)(Vargs args) { ... }

 but stuff like that isn't possible currently.

 That said, parsing the string for "bar" and "baz" is both difficult and
 doesn't provide access inside opDispatch to "bar" and "baz".

I think we all ought to look closely at ProxyOf. https://github.com/D-Programming-Language/phobos/pull/300 Andrei
Dec 27 2011
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/26/11 7:49 PM, Andrej Mitrovic wrote:
 On 12/27/11, Andrei Alexandrescu<SeeWebsiteForEmail erdani.org>  wrote:
 We can easily have opDispatch look at field names. But I think it's poor
 design to expose bald data anyway.

opDispatch doesn't work with property functions,

It actually does, as per the unittests. Even if it currently does by property being too lax, it should continue to work.
 or opBinary,

Should work, as operators are just translated to regular methods.
 or
 opOpAssign.

Should work.
 And what about the ctor? I can't call the ctor with your
 RefCounted.

Well, construction is a delicate topic. Currently RefCounted handles all construction internally, e.g. it doesn't take over a pointer to an existing instance (as C++'s shared_ptr does). So construction of objects needs to be handled by RefCounted itself - e.g. by forwarding constructor parameters. Andrei
Dec 26 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/27/11 12:08 AM, Andrej Mitrovic wrote:
 On 12/27/11, Andrei Alexandrescu<SeeWebsiteForEmail erdani.org>  wrote:
 It actually does, as per the unittests. Even if it currently does by
  property being too lax, it should continue to work.

It actually doesn't: struct FooImpl { int _x; property int x() { return _x; } property void x(int val) { _x = val; } auto dup() { return FooImpl(); } auto dispose() { } } void main() { RefCounted!FooImpl foo; foo.x = 1; // NG } Sure you could make a property return ref, but that's circumventing the setter and allowing direct access to the field from client-code. I've ran into this issue before when playing with opDispatch but I couldn't figure out a workaround.

Sorry for being unclear - when I wrote "should work" I meant "it's a bug if it doesn't".
 So construction of objects
 needs to be handled by RefCounted itself - e.g. by forwarding
 constructor parameters.

But it doesn't do that currently?

The prototype does not define a variadic forwarding constructor. Andrei
Dec 27 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/27/11 5:27 AM, kenji hara wrote:
 I've already posted a dmd patch to fix all of opDispatch problems:

 https://github.com/D-Programming-Language/dmd/pull/280

As far a I understand you pass the whole template as a string inside opDispatch? For example, say obj defines opDispatch: obj.foo!(bar, baz)(a, b); Would that be rewritten as obj.opDispatch!("foo!(bar, baz)")(a, b); ? That would be great.
 With it, I've posted a useful library utility to implement
 'super-type' like D1 typedef:

 https://github.com/D-Programming-Language/phobos/pull/300

 I'm naming it 'ProxyOf', and it supports various of forwardings,
 function call, property access, and specialized template member
 function.

 Kenji Hara

Thanks! Sorry I didn't look over ProxyOf first, it might have saved me some work. I'll do so soon. Andrei
Dec 27 2011
parent reply deadalnix <deadalnix gmail.com> writes:
Le 27/12/2011 16:09, Andrei Alexandrescu a écrit :
 On 12/27/11 5:27 AM, kenji hara wrote:
 I've already posted a dmd patch to fix all of opDispatch problems:

 https://github.com/D-Programming-Language/dmd/pull/280

As far a I understand you pass the whole template as a string inside opDispatch? For example, say obj defines opDispatch: obj.foo!(bar, baz)(a, b); Would that be rewritten as obj.opDispatch!("foo!(bar, baz)")(a, b); ? That would be great.

I think a variadoic template is a better option because of scope issues. You may not know anymore what is bar or baz within opDispatch.
Dec 27 2011
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 27/12/11 4:32 PM, deadalnix wrote:
 Le 27/12/2011 16:09, Andrei Alexandrescu a écrit :
 On 12/27/11 5:27 AM, kenji hara wrote:
 I've already posted a dmd patch to fix all of opDispatch problems:

 https://github.com/D-Programming-Language/dmd/pull/280

As far a I understand you pass the whole template as a string inside opDispatch? For example, say obj defines opDispatch: obj.foo!(bar, baz)(a, b); Would that be rewritten as obj.opDispatch!("foo!(bar, baz)")(a, b); ? That would be great.

I think a variadoic template is a better option because of scope issues. You may not know anymore what is bar or baz within opDispatch.

How would that work? opDispatch already has variadic templates for the normal function parameters. Make opDispatch a template inside a template?
Dec 27 2011
next sibling parent deadalnix <deadalnix gmail.com> writes:
Le 27/12/2011 18:03, Peter Alexander a écrit :
 On 27/12/11 4:32 PM, deadalnix wrote:
 Le 27/12/2011 16:09, Andrei Alexandrescu a écrit :
 On 12/27/11 5:27 AM, kenji hara wrote:
 I've already posted a dmd patch to fix all of opDispatch problems:

 https://github.com/D-Programming-Language/dmd/pull/280

As far a I understand you pass the whole template as a string inside opDispatch? For example, say obj defines opDispatch: obj.foo!(bar, baz)(a, b); Would that be rewritten as obj.opDispatch!("foo!(bar, baz)")(a, b); ? That would be great.

I think a variadoic template is a better option because of scope issues. You may not know anymore what is bar or baz within opDispatch.

How would that work? opDispatch already has variadic templates for the normal function parameters. Make opDispatch a template inside a template?

You are right, that was stupid of me. I'm afraid that something like the template inside a template is something we should consider. Or passing templates arguements as a Tuple to opDispatch.
Dec 27 2011
prev sibling parent "Daniel Murphy" <yebblies nospamgmail.com> writes:
"Peter Alexander" <peter.alexander.au gmail.com> wrote in message 
news:jdct6a$2230$1 digitalmars.com...
 How would that work? opDispatch already has variadic templates for the 
 normal function parameters. Make opDispatch a template inside a template?

I suppose that's what this is for. http://d.puremagic.com/issues/show_bug.cgi?id=2599
Dec 28 2011
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 26 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 12/27/11, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:
 We can easily have opDispatch look at field names. But I think it's poor
 design to expose bald data anyway.

opDispatch doesn't work with property functions, or opBinary, or opOpAssign. And what about the ctor? I can't call the ctor with your RefCounted.
Dec 26 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 12/27/11, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:
 It actually does, as per the unittests. Even if it currently does by
  property being too lax, it should continue to work.

It actually doesn't: struct FooImpl { int _x; property int x() { return _x; } property void x(int val) { _x = val; } auto dup() { return FooImpl(); } auto dispose() { } } void main() { RefCounted!FooImpl foo; foo.x = 1; // NG } Sure you could make a property return ref, but that's circumventing the setter and allowing direct access to the field from client-code. I've ran into this issue before when playing with opDispatch but I couldn't figure out a workaround.
 or opBinary,

Should work, as operators are just translated to regular methods.
 or
 opOpAssign.

Should work.

Doesn't seem to work: struct FooImpl { auto opBinary(string op)(int val) { return this; } void opOpAssign(string op)(int val) { } auto dup() { return FooImpl(); } auto dispose() { } } void main() { RefCounted!FooImpl foo; auto f = foo + 1; // ng foo += 1; // ng }
 So construction of objects
 needs to be handled by RefCounted itself - e.g. by forwarding
 constructor parameters.

But it doesn't do that currently?
Dec 26 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 26 Dec 2011 17:30:54 -0800, Peter Alexander
<peter.alexander.au gmail.com> wrote:

 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.

Yes, in theory, but no in practice. It's perfectly possible to use __name or __name__ in user code, just highly not recommended. And while I'd never do that in my user code, I think the runtime and the standard library should be able to use __ (or maybe ___) when needed.
Dec 26 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 26 Dec 2011 19:00:57 -0800, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

 On 12/26/11 7:49 PM, Andrej Mitrovic wrote:
 On 12/27/11, Andrei Alexandrescu<SeeWebsiteForEmail erdani.org>  wrote:
 We can easily have opDispatch look at field names. But I think it's poor
 design to expose bald data anyway.

opDispatch doesn't work with property functions,

It actually does, as per the unittests. Even if it currently does by property being too lax, it should continue to work.

Currently, if opDispatch is only templated on a string, property assignment (i.e. foo.x = 1) syntax works. If opDispatch is templated on more than the method name, DMD 2.057 ICEes.
 or opBinary,

Should work, as operators are just translated to regular methods.
 or
 opOpAssign.

Should work.

But not in practice yet; DMD still treats opBinary, opAssign, etc as being special and doesn't forward them to opDispatch. However, it's straightforward to manually define them yourself.
Dec 26 2011
prev sibling next sibling parent kenji hara <k.hara.pg gmail.com> writes:
I've already posted a dmd patch to fix all of opDispatch problems:

https://github.com/D-Programming-Language/dmd/pull/280

With it, I've posted a useful library utility to implement
'super-type' like D1 typedef:

https://github.com/D-Programming-Language/phobos/pull/300

I'm naming it 'ProxyOf', and it supports various of forwardings,
function call, property access, and specialized template member
function.

Kenji Hara

2011/12/27 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:
 On 12/26/11 7:25 PM, Peter Alexander wrote:
 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
 }

We can easily have opDispatch look at field names. But I think it's poor design to expose bald data anyway.
 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
 }

This is a problem. Andrei

Dec 27 2011
prev sibling next sibling parent "SHOO" <zan77137 nifty.com> writes:
When I tried implementation of Unique which was not usable at all 
though it was listed in a document, I faced a similar problem.
The patch of Kenji is intended to just solve this.
Even if these patch applied, some problems are left. (e.g. 
Automatic definitions of the opEquals function for Objects / see 
also: https://github.com/D-Programming-Language/druntime/pull/72 )
However, I think that the priority of these pull request is high.

On Tuesday, 27 December 2011 at 11:27:43 UTC, kenji hara wrote:
 I've already posted a dmd patch to fix all of opDispatch 
 problems:

 https://github.com/D-Programming-Language/dmd/pull/280

 With it, I've posted a useful library utility to implement
 'super-type' like D1 typedef:

 https://github.com/D-Programming-Language/phobos/pull/300

 I'm naming it 'ProxyOf', and it supports various of forwardings,
 function call, property access, and specialized template member
 function.

 Kenji Hara

 2011/12/27 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:
 On 12/26/11 7:25 PM, Peter Alexander wrote:
 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
 }

We can easily have opDispatch look at field names. But I think it's poor design to expose bald data anyway.
 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
 }

This is a problem. Andrei


Dec 27 2011
prev sibling next sibling parent "Froglegs" <lugtug gmail.com> writes:
When I go to that link it just says

Unknown Paste ID!

Don't see any code anywhere.. hum




  What is wrong with value containers?  They work great in C++, a 
container is such a basic thing that ref counting and whatnot is 
rarely if ever needed, and in the unlikely event you need to 
share a container, wrapping it with a smart pointer of some sort 
is easy enough in C++, let alone D with its better support for 
type aliasing.
Dec 27 2011
prev sibling next sibling parent kenji hara <k.hara.pg gmail.com> writes:
ProxyOf rewrites the expression

 obj.foo!(bar, baz)(a, b);

obj.opDispatch!("foo").opDispatch!(bar, baz)(a, b) // opDispatch!("foo").opDispatch generates a temporary member template for forwarding. // And it is actually processed as 'eponymous template'. Thanks. Kenji Hara 2011/12/28 Andrei Alexandrescu <SeeWebsiteForEmail erdani.org>:
 On 12/27/11 5:27 AM, kenji hara wrote:
 I've already posted a dmd patch to fix all of opDispatch problems:

 https://github.com/D-Programming-Language/dmd/pull/280

As far a I understand you pass the whole template as a string inside opDispatch? For example, say obj defines opDispatch: obj.foo!(bar, baz)(a, b); Would that be rewritten as obj.opDispatch!("foo!(bar, baz)")(a, b); ? That would be great.
 With it, I've posted a useful library utility to implement
 'super-type' like D1 typedef:

 https://github.com/D-Programming-Language/phobos/pull/300

 I'm naming it 'ProxyOf', and it supports various of forwardings,
 function call, property access, and specialized template member
 function.

 Kenji Hara

Thanks! Sorry I didn't look over ProxyOf first, it might have saved me some work. I'll do so soon. Andrei

Dec 27 2011
prev sibling next sibling parent Jacob Carlborg <doob me.com> writes:
On 2011-12-27 02:09, 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?

You can always call opDispatch directly. -- /Jacob Carlborg
Dec 27 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Tue, 27 Dec 2011 07:10:14 -0800, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

 On 12/27/11 4:32 AM, Peter Alexander wrote:
 On 27/12/11 3:05 AM, Andrei Alexandrescu wrote:
 On 12/26/11 8:23 PM, Peter Alexander wrote:
 I am
 not convinced that it can be used seamlessly without some relatively
 large changes to the language.

I repeat that opDispatch and auto ref were invented for this, so anything that doesn't work now is a bug. There are no changes needed to the language, only fix the bugs :o).

How do you call template member functions of the held object without changing opDispatch?

The idea is to pass the entire template instantiation as the string. obj.foo!(bar, baz)(a, b); -> obj.opDispatch!("foo!(bar, baz)")(a, b); Andrei

obj.opDispatch!("foo",bar,baz)(a,b); although I don't know how opDispatch would be written to handle such a call in a generic manner, i.e. I would want to define it as obj.opDispatch!(string name, Targs..,Vargs..)(Vargs args) { ... } but stuff like that isn't possible currently. That said, parsing the string for "bar" and "baz" is both difficult and doesn't provide access inside opDispatch to "bar" and "baz".
Dec 27 2011
prev sibling parent "Tove" <tove fransson.se> writes:
Is work ongoing on this container prototype? Sounds quite 
interesting...
Mar 13 2012
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/26/11 11:25 AM, Andrei Alexandrescu wrote:
[snip]
 Destroy.

Walter indeed just destroyed me over the phone: I conflated reference counting with copy-on-write. Essentially instead of defining a reference type that's garbage-collected, I defined a value type that has cow. Which is not bad! Check out the quick fix at http://pastebin.com/HHw06qrc. With that, cow is a sheer policy. With the magic of opDispatch it looks like we can define reference counted containers _and_ value containers - all in very little code. The perspectives here are extremely exciting. The question remains how to best package this awesome array of options to maximize coherence. So we have: 1. "Basic" containers - reference semantics, using classic garbage collection 2. Reference counted containers - still reference semantics, using reference counting 3. COW containers - value semantics, using reference counting to make copying O(1). How to we provide an Apple-style nice wrapping to all of the above? Andrei
Dec 26 2011
next sibling parent Michel Fortin <michel.fortin michelf.com> writes:
On 2011-12-27 02:47:50 +0000, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 On 12/26/11 11:25 AM, Andrei Alexandrescu wrote:
 [snip]
 Destroy.

Walter indeed just destroyed me over the phone: I conflated reference counting with copy-on-write. Essentially instead of defining a reference type that's garbage-collected, I defined a value type that has cow. Which is not bad! Check out the quick fix at http://pastebin.com/HHw06qrc. With that, cow is a sheer policy. With the magic of opDispatch it looks like we can define reference counted containers _and_ value containers - all in very little code. The perspectives here are extremely exciting. The question remains how to best package this awesome array of options to maximize coherence. So we have: 1. "Basic" containers - reference semantics, using classic garbage collection 2. Reference counted containers - still reference semantics, using reference counting 3. COW containers - value semantics, using reference counting to make copying O(1). How to we provide an Apple-style nice wrapping to all of the above?

Apple just doesn't give you this kind of options. It picks one for you, documents the semantics and keep the implementation opaque. Containers in Objective-C are regular objects, so they follow object semantics (not that I like it though). Ideally for D we'd follow the natural language semantics, where the first would be a DList*, the second is a RefCounted!DList, and the last is a RefCopy!DList. The only "problem" is that the default 'DList' is a value-type and it seems you don't want that to be the default. Unfortunately, I don't think there is a clean way to solve this: there are just too many options, some who must be implemented by library types and another by a language type. Reminds me of Rebindable… -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Dec 26 2011
prev sibling next sibling parent "Martin Nowak" <dawg dawgfoto.de> writes:
On Tue, 27 Dec 2011 03:47:50 +0100, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 12/26/11 11:25 AM, Andrei Alexandrescu wrote:
 [snip]
 Destroy.

Walter indeed just destroyed me over the phone: I conflated reference counting with copy-on-write. Essentially instead of defining a reference type that's garbage-collected, I defined a value type that has cow. Which is not bad! Check out the quick fix at http://pastebin.com/HHw06qrc. With that, cow is a sheer policy. With the magic of opDispatch it looks like we can define reference counted containers _and_ value containers - all in very little code. The perspectives here are extremely exciting. The question remains how to best package this awesome array of options to maximize coherence. So we have: 1. "Basic" containers - reference semantics, using classic garbage collection

as a field might be an option that mixes well with the other wrappers.
 2. Reference counted containers - still reference semantics, using  
 reference counting

 3. COW containers - value semantics, using reference counting to make  
 copying O(1).

anything like that in C++. It deserves to be a separate wrapper in std.typecons or so.
 How to we provide an Apple-style nice wrapping to all of the above?


 Andrei

providing the three wrappers seems the most flexible approach. The are applications where values are sufficient, e.g. global lists. for the naming: struct DListImpl; // public alias ClassWrapper!DListImpl DList; optionally add aliases: alias RefCounted!DListImpl RefCountedDList; alias CopyOnWrite!DListImpl CopyOnWriteDList; Given that it would be used consistently across the whole std.container modules it's an easy scheme to learn.
Dec 26 2011
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, December 26, 2011 20:47:50 Andrei Alexandrescu wrote:
 On 12/26/11 11:25 AM, Andrei Alexandrescu wrote:
 [snip]
 
 Destroy.

Walter indeed just destroyed me over the phone: I conflated reference counting with copy-on-write. Essentially instead of defining a reference type that's garbage-collected, I defined a value type that has cow.

That would explain a few things. ensureUnique is a rather bizarre thing to have just for reference counting.
 Which is not bad! Check out the quick fix at http://pastebin.com/HHw06qrc.
 
 With that, cow is a sheer policy. With the magic of opDispatch it looks
 like we can define reference counted containers _and_ value containers -
 all in very little code.
 
 The perspectives here are extremely exciting. The question remains how
 to best package this awesome array of options to maximize coherence. So
 we have:
 
 1. "Basic" containers - reference semantics, using classic garbage
 collection
 
 2. Reference counted containers - still reference semantics, using
 reference counting
 
 3. COW containers - value semantics, using reference counting to make
 copying O(1).
 
 How to we provide an Apple-style nice wrapping to all of the above?

I'd be inclined to argue that reference counting and COW should be kept separate as opposed to being different versions of the same type simply to make it easier to understand. Not to mention, how often is COW needed for containers? It's useful for many things, but it's only useful for value-type containers, and the use cases for value-type containers are fairly limited I should think. I'm sure that they're very useful under certain circumstances, but as has been pointed out in the past, the fact that C++ defaults to having value-type containers is a big problem. So, I don't think that it's a bad thing to make it possible to have value-type containers and/or COW containers, but if they're going to seriously complicate things, then they should be separate IMHO. They're more specialized as opposed to being the normal use case. By the way, I'm surprised to see the use of delete in that code, since delete is supposed to be going away. - Jonathan M Davis
Dec 27 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/27/11 2:24 AM, Jonathan M Davis wrote:
 On Monday, December 26, 2011 20:47:50 Andrei Alexandrescu wrote:
 1. "Basic" containers - reference semantics, using classic garbage
 collection

 2. Reference counted containers - still reference semantics, using
 reference counting

 3. COW containers - value semantics, using reference counting to make
 copying O(1).

 How to we provide an Apple-style nice wrapping to all of the above?

I'd be inclined to argue that reference counting and COW should be kept separate as opposed to being different versions of the same type simply to make it easier to understand. Not to mention, how often is COW needed for containers? It's useful for many things, but it's only useful for value-type containers, and the use cases for value-type containers are fairly limited I should think. I'm sure that they're very useful under certain circumstances, but as has been pointed out in the past, the fact that C++ defaults to having value-type containers is a big problem. So, I don't think that it's a bad thing to make it possible to have value-type containers and/or COW containers, but if they're going to seriously complicate things, then they should be separate IMHO. They're more specialized as opposed to being the normal use case.

Someone coming from C++ would instantly recognize value containers, and might prefer using them in spite our judgment that reference containers are preferable. COW is a great bridge because it keeps the copy constructor cheap.
 By the way, I'm surprised to see the use of delete in that code, since delete
 is supposed to be going away.

It's just a prototype. Andrei
Dec 27 2011
prev sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-12-27 02:47:50 +0000, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 The perspectives here are extremely exciting. The question remains how 
 to best package this awesome array of options to maximize coherence. So 
 we have:
 
 1. "Basic" containers - reference semantics, using classic garbage collection
 
 2. Reference counted containers - still reference semantics, using 
 reference counting
 
 3. COW containers - value semantics, using reference counting to make 
 copying O(1).

I like the idea, but... I worry about fragmentation. Say we have those three variant of each container and you write a function accepting a container, which one do you use for the parameter? The only type common to all three is "DListImpl", except it shouldn't work because: 1. you barred access to the underlying DListImpl in RefCounted (using opDispatch instead of alias this) 2. you want to spare users of writing "ref" every time they write a function prototype Those two design constrains makes it impossible to have a common type independent of the "packaging" policy. I worry also about const and immutable. It's nice to have reference counting, but it works poorly with const and immutable. If a function declares it takes a const container, you'll have to pass the reference counted container by ref to avoid mutating the reference count, which goes contrary one of your goals. - - - Let me make a language suggestion that will address both of these problems. Allow structs to be flagged so they are always passed by reference to a function, like this: ref struct DListImpl {…} Now a function accepting a DListImpl will implicitly have it passed by "ref" with no unnecessary copy, and no need to mutate a reference count: void func(DListImpl list) {…} Then you can use alias this in RefCounted giving access to a "ref DListImpl" which can be passed to functions always by ref, regardless of the packaging policy, and without the need to remember to write "ref" every time you write a function accepting a container (because it is a ref struct which is always implicitly passed by ref). Functions that don't need to store a reference to the container won't have to care about whether the container they get is maintained using a reference counter, COW, or the GC. And those functions can accept a const container, or even a value-type container (which gets implicitly passed by ref). So with implicit ref parameters for "ref struct" types you solve the issue of fragmentation and of passing const containers to functions. The underlying principle is that how to efficiently pass a type to functions should be decided at the type level. You're trying to figure out how it should work for containers, but I think it should apply more broadly to the language as a whole. But there is one more thing. ;-) Implicit ref parameters could also solve elegantly the more general problem of passing rvalues by reference if you make them accept rvalues. Only parameters explicitly annotated with "ref" would refuse rvalues, those implicitly passed by ref would accept them. -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Dec 27 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/27/11 8:21 AM, Michel Fortin wrote:
 On 2011-12-27 02:47:50 +0000, Andrei Alexandrescu
 1. "Basic" containers - reference semantics, using classic garbage
 collection

 2. Reference counted containers - still reference semantics, using
 reference counting

 3. COW containers - value semantics, using reference counting to make
 copying O(1).

I like the idea, but... I worry about fragmentation. Say we have those three variant of each container and you write a function accepting a container, which one do you use for the parameter? The only type common to all three is "DListImpl", except it shouldn't work because: 1. you barred access to the underlying DListImpl in RefCounted (using opDispatch instead of alias this) 2. you want to spare users of writing "ref" every time they write a function prototype Those two design constrains makes it impossible to have a common type independent of the "packaging" policy.

Things could be arranged to make that happen (e.g. by making "cow" a runtime parameter), but I think that would be a wrong turn. These options are important design choices, not happenstance details; one should _not_ naively mix them. For example, say we arrange things such that "cow" is opaque. Then code using a DList would have dramatically different semantics depending on what DList you pass in, or would need to guard everything with lst.isCow vs. not.
 I worry also about const and immutable.

 It's nice to have reference counting, but it works poorly with const and
 immutable. If a function declares it takes a const container, you'll
 have to pass the reference counted container by ref to avoid mutating
 the reference count, which goes contrary one of your goals.

I talked a lot about this with Walter and we concluded that the story with const and immutable goes like this: in a RefCounted!T object, the T is constant, not the RefCounted. So it would be RefCounted!(immutable T).
 - - -

 Let me make a language suggestion that will address both of these problems.

 Allow structs to be flagged so they are always passed by reference to a
 function, like this:

 ref struct DListImpl {…}

 Now a function accepting a DListImpl will implicitly have it passed by
 "ref" with no unnecessary copy, and no need to mutate a reference count:

 void func(DListImpl list) {…}

 Then you can use alias this in RefCounted giving access to a "ref
 DListImpl" which can be passed to functions always by ref, regardless of
 the packaging policy, and without the need to remember to write "ref"
 every time you write a function accepting a container (because it is a
 ref struct which is always implicitly passed by ref).

 Functions that don't need to store a reference to the container won't
 have to care about whether the container they get is maintained using a
 reference counter, COW, or the GC. And those functions can accept a
 const container, or even a value-type container (which gets implicitly
 passed by ref).

 So with implicit ref parameters for "ref struct" types you solve the
 issue of fragmentation and of passing const containers to functions.

 The underlying principle is that how to efficiently pass a type to
 functions should be decided at the type level. You're trying to figure
 out how it should work for containers, but I think it should apply more
 broadly to the language as a whole.

 But there is one more thing. ;-)

 Implicit ref parameters could also solve elegantly the more general
 problem of passing rvalues by reference if you make them accept rvalues.
 Only parameters explicitly annotated with "ref" would refuse rvalues,
 those implicitly passed by ref would accept them.

Not to seem dismissive, but this sounds quite complicated for what it does. Could we implement it as a library feature? And assuming your motivating argument wasn't as strong, is it needed? Andrei
Dec 27 2011
parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2011-12-27 14:57:18 +0000, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 On 12/27/11 8:21 AM, Michel Fortin wrote:
 On 2011-12-27 02:47:50 +0000, Andrei Alexandrescu
 1. "Basic" containers - reference semantics, using classic garbage
 collection
 
 2. Reference counted containers - still reference semantics, using
 reference counting
 
 3. COW containers - value semantics, using reference counting to make
 copying O(1).

I like the idea, but... I worry about fragmentation. Say we have those three variant of each container and you write a function accepting a container, which one do you use for the parameter? The only type common to all three is "DListImpl", except it shouldn't work because: 1. you barred access to the underlying DListImpl in RefCounted (using opDispatch instead of alias this) 2. you want to spare users of writing "ref" every time they write a function prototype Those two design constrains makes it impossible to have a common type independent of the "packaging" policy.

Things could be arranged to make that happen (e.g. by making "cow" a runtime parameter), but I think that would be a wrong turn. These options are important design choices, not happenstance details; one should _not_ naively mix them. For example, say we arrange things such that "cow" is opaque. Then code using a DList would have dramatically different semantics depending on what DList you pass in, or would need to guard everything with lst.isCow vs. not.

Indeed, COW must not be a runtime parameter.
 I worry also about const and immutable.
 
 It's nice to have reference counting, but it works poorly with const and
 immutable. If a function declares it takes a const container, you'll
 have to pass the reference counted container by ref to avoid mutating
 the reference count, which goes contrary one of your goals.

I talked a lot about this with Walter and we concluded that the story with const and immutable goes like this: in a RefCounted!T object, the T is constant, not the RefCounted. So it would be RefCounted!(immutable T).

That'll work, but I'm not sure where you're getting at with this. Instead of writing "const DList!T" as the parameter type in your function you have to write "RefCounted!(const DListImpl!T)"? Isn't that worse than "ref const DList!T"?
 - - -
 
 Let me make a language suggestion that will address both of these problems.
 
 Allow structs to be flagged so they are always passed by reference to a
 function, like this:
 
 ref struct DListImpl {…}
 
 Now a function accepting a DListImpl will implicitly have it passed by
 "ref" with no unnecessary copy, and no need to mutate a reference count:
 
 void func(DListImpl list) {…}
 
 Then you can use alias this in RefCounted giving access to a "ref
 DListImpl" which can be passed to functions always by ref, regardless of
 the packaging policy, and without the need to remember to write "ref"
 every time you write a function accepting a container (because it is a
 ref struct which is always implicitly passed by ref).
 
 Functions that don't need to store a reference to the container won't
 have to care about whether the container they get is maintained using a
 reference counter, COW, or the GC. And those functions can accept a
 const container, or even a value-type container (which gets implicitly
 passed by ref).
 
 So with implicit ref parameters for "ref struct" types you solve the
 issue of fragmentation and of passing const containers to functions.
 
 The underlying principle is that how to efficiently pass a type to
 functions should be decided at the type level. You're trying to figure
 out how it should work for containers, but I think it should apply more
 broadly to the language as a whole.
 
 But there is one more thing. ;-)
 
 Implicit ref parameters could also solve elegantly the more general
 problem of passing rvalues by reference if you make them accept rvalues.
 Only parameters explicitly annotated with "ref" would refuse rvalues,
 those implicitly passed by ref would accept them.

Not to seem dismissive, but this sounds quite complicated for what it does. Could we implement it as a library feature? And assuming your motivating argument wasn't as strong, is it needed?

It can't be a library feature because it requires the compiler to implicitly add a "ref" to functions parameters when they are of a "ref struct" type. That's pretty much all it does: add a flag to struct types, implicitly add "ref" to parameters based on that flag. I'm not sure why you think it's complicated. Perhaps I should just not have talked about rvalues: that's a separate benefit you can built on top of it by adding one or two lines of code in DMD, but it's a separate thing. -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Dec 27 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/27/11 9:27 AM, Michel Fortin wrote:
 On 2011-12-27 14:57:18 +0000, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> said:
 I talked a lot about this with Walter and we concluded that the story
 with const and immutable goes like this: in a RefCounted!T object, the
 T is constant, not the RefCounted. So it would be
 RefCounted!(immutable T).

That'll work, but I'm not sure where you're getting at with this. Instead of writing "const DList!T" as the parameter type in your function you have to write "RefCounted!(const DListImpl!T)"? Isn't that worse than "ref const DList!T"?

That's an issue we're thinking about how to address.
 Not to seem dismissive, but this sounds quite complicated for what it
 does. Could we implement it as a library feature? And assuming your
 motivating argument wasn't as strong, is it needed?

It can't be a library feature because it requires the compiler to implicitly add a "ref" to functions parameters when they are of a "ref struct" type. That's pretty much all it does: add a flag to struct types, implicitly add "ref" to parameters based on that flag.

Anyhow, I think a feature would need to be tremendously justified and with a huge power/weight ratio. This one I actually find ill-designed because now I can't look at the body of a function to figure pass-by-value vs. pass-by-reference - I also need to look at the definition (what if it was a ref struct?). One more non-modular thing to keep in mind. This is not going to fly.
 I'm not sure why you think it's complicated. Perhaps I should just not
 have talked about rvalues: that's a separate benefit you can built on
 top of it by adding one or two lines of code in DMD, but it's a separate
 thing.

I think the "But there's one more thing" did it to me. Andrei
Dec 27 2011
parent Michel Fortin <michel.fortin michelf.com> writes:
On 2011-12-27 15:48:56 +0000, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 On 12/27/11 9:27 AM, Michel Fortin wrote:
 
 It can't be a library feature because it requires the compiler to
 implicitly add a "ref" to functions parameters when they are of a "ref
 struct" type. That's pretty much all it does: add a flag to struct
 types, implicitly add "ref" to parameters based on that flag.

Anyhow, I think a feature would need to be tremendously justified and with a huge power/weight ratio. This one I actually find ill-designed because now I can't look at the body of a function to figure pass-by-value vs. pass-by-reference I also need to look at the definition (what if it was a ref struct?). One more non-modular thing to keep in mind. This is not going to fly.

I think the appeal is that it solves two common problems cleanly. It can solve the passing of rvalue by reference so you wouldn't need to add yet another parameter attribute for that (if the type is a ref struct, this is done implicitly). And it solves the problem of passing containers to functions (they'd be implicitly passed by ref). Basically, it solves the general problem where you have to decide every time you write a function accepting a struct whether it should be by value or by reference. The designer of the type chooses one behaviour and that behaviour is the same everywhere. It's true that it blurs a little more the line between by-value and by-ref. But note that the line is already quite blurry: You already don't know by looking at a type name whether a type is an alias or a class. Or even a struct that mimics reference semantics through internal trickery (like RefCounted). And what about dynamic arrays? or ranges? That whole pass-by-value vs. pass-by-reference dichotomy isn't as black and white as we'd like to think. You can never tell just by looking at the name what semantics the type has when "copied". One thing it does change is it makes function parameters a special case where there was none before. But why do you think "const T &" is used all over the place for parameters but almost none elsewhere in C++? Simply because function parameters *are* a special case. Function parameters need to be passed around efficiently (hence the "&"), and they need to accept rvalues (hence the "const"). Everyone forget to write the "&" and the "const" once in a while in C++, and like you I'd like to avoid this mess in D. I'd say just make the best way the default: make types that should be passed by reference passed by reference by default. Trying to force everyone to use heap-allocated objects, reference counting, or other wrapping schemes is adding also adding much complexity, probably more than what I'm proposing. For containers, the "ref struct" solution prevents fragmentation by packaging because whatever packaging you use for your container (GC, RefCounted, COW, or no packaging at all) the underlying implementation can always be passed by "ref" to a function. And peeling the packaging part also makes it easier to add const to the container (no mutable reference counter to update). If you can find a better idea to solve the fragmentation problem and the const problem (and separately the rvalue problem), then go on. I'm just pointing at what seems a good idea to me. You're still free to find better solutions, even though I'm not convinced there are, at least not without forcing a one-size-fit-all packaging to everyone. - - - Note that I still am in agreement with your current container prototype design. One important criterion to me is whether I can use the "Impl" part of it directly and pass it around by ref if I want. Seems like I can. -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Dec 27 2011
prev sibling next sibling parent "Martin Nowak" <dawg dawgfoto.de> writes:
On Mon, 26 Dec 2011 18:25:10 +0100, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> 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

// "empty" object intended for static and immutable methods when // the data pointer is null. It won't be modified. We assume the // empty object is equivalent to a null stored pointer. private static immutable T _empty; I don't see much need for this. Instances without identity are rarely useful, i.e. you will mostly initialize them to a particular value before using them. I could think of some strategy constructs being used with templates, but then you would not wrap them in RefCounted in the first place. Of course RefCounted should not create a value when accessing static members.
Dec 26 2011
prev sibling parent reply deadalnix <deadalnix gmail.com> writes:
Le 26/12/2011 18:25, Andrei Alexandrescu a écrit :
 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

The first thing that I see looking at the source code is how many null check you'll find in RefCounted . As the RefCounted struct is useless without a payload, we should ensure that the payload exists, in all cases, and not null check at every operation.
Dec 27 2011
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, December 27, 2011 12:32:01 deadalnix wrote:
 The first thing that I see looking at the source code is how many null
 check you'll find in RefCounted . As the RefCounted struct is useless
 without a payload, we should ensure that the payload exists, in all
 cases, and not null check at every operation.

But then it would be impossible to declare a container before initializing it, and that would be a problem. - Jonathan M Davis
Dec 27 2011
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/27/11 5:32 AM, deadalnix wrote:
 The first thing that I see looking at the source code is how many null
 check you'll find in RefCounted . As the RefCounted struct is useless
 without a payload, we should ensure that the payload exists, in all
 cases, and not null check at every operation.

D's take on default constructor makes it impossible to initialize the object 100% automatically. What can be done is a test inside opDispatch followed by default construction if the object is null. That's not terribly useful and intuitive. Consider: void fun(DList!int lst) { lst.insertFront(42); } void main() { DList!int lst1; lst1.insertFront(43); fun(lst1); assert(lst1.front == 42); // fine DList!int lst2; fun(lst2); assert(lst2.front == 42); // gaaaaaaa! } This is the behavior of any reference type that can be null, because null doesn't refer to any object. IMHO this, and not null pointer exceptions, is the largest liability of null. Andrei
Dec 27 2011
parent deadalnix <deadalnix gmail.com> writes:
Le 27/12/2011 16:04, Andrei Alexandrescu a écrit :
 On 12/27/11 5:32 AM, deadalnix wrote:
 The first thing that I see looking at the source code is how many null
 check you'll find in RefCounted . As the RefCounted struct is useless
 without a payload, we should ensure that the payload exists, in all
 cases, and not null check at every operation.

D's take on default constructor makes it impossible to initialize the object 100% automatically. What can be done is a test inside opDispatch followed by default construction if the object is null. That's not terribly useful and intuitive. Consider:

That is just moving the problem around. It is even worse I think.
 This is the behavior of any reference type that can be null, because
 null doesn't refer to any object. IMHO this, and not null pointer
 exceptions, is the largest liability of null.


 Andrei

Yes, the problem is way larger. I think null is a very poor solution to a real instanciation problem. This cause more trouble than solution. It is error prone (forget a null check and you are doomed) and have a runtime cost.
Dec 27 2011