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 "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
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
parent reply "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
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 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
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
next sibling parent reply 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
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 "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 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 reply "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


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".
Dec 27 2011
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 parent reply 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
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 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
next sibling 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 reply "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
parent "Tove" <tove fransson.se> writes:
Is work ongoing on this container prototype? Sounds quite 
interesting...
Mar 13 2012
prev sibling parent kenji hara <k.hara.pg gmail.com> writes:
ProxyOf rewrites the expression


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


to

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 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 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 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


Creating a final class wrapper using opDispatch and a value container
as a field might be an option that mixes well with the other wrappers.


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


Can't this be merged with std.typecons.RefCounted?


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


If it works correctly this is a fully transparent COW wrapper, never seen  
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


Implementing containers as value types with deep-copy and
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