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