October 28, 2015
On 10/28/2015 02:00 PM, Timon Gehr wrote:
>> void bar() {
>>      C c = new C();
>>      [[auto __t = c; __t.refs += 2;]]
>>      foo(c, c);
>>      [[__t.refs -= 2;]]
>> }
>
> +=2 seems arbitrary. Only one new reference is generated.

I was thinking conservatively - add 1 for anything passed in, whether by value or reference.

Generally I'm very optimistic about conservative analyses - analyses that look at a function statically and conclude that the reference count can't go beyond e.g. 12 or whatever. Then upon object creation there's __t.refs+=12 and upon exit there's a __t-=12 and inside the function proper there's no other refcount bump.

Basic idea being +=1 or +=100 have the same cost, and refcount doesn't need to precisely reflect the number of references, only >=. We can exploit these facts.

(There are other analyses that compute conservative bounds, such as our well-known VRP or computing the stack frame size for a function.)

> Anyway, the solution is indeed to make it the responsibility of the
> caller to keep the borrowed object alive. I.e. when passing a non-scope
> reference to a scope argument, the reference count must be increased for
> the duration of the call. The benefit is that scope references can be
> duplicated arbitrarily without updating the reference count.
> This applies to globals just as well as to other cases.

Sounds interesting. So it looks like one additional hidden variable per reference created in a scope may be necessary in order to avoid complicated inc/dec for references.

> (I haven't read DIP74 though, so I might be misinterpreting your
> intentions.)

I'm glad you didn't because (a) it's better to have a fresh mind, (b) DIP74 has progressively integrated cases we hadn't thought of, and became a mess.


Andrei
_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

October 28, 2015
On 10/28/2015 02:16 PM, Timon Gehr wrote:
> On 10/28/2015 04:07 PM, Andrei Alexandrescu wrote:
>>
>>> How does the compiler lose control with opInc/opDec? It could still fuse
>>> them.
>>
>> Fusing them relies on the compiler knowing the effects are additive
>> (three successive opInc()s mean += 3 etc) and also that opInc() and
>> opDec() cancel each other. Allowing the user to define them arbitrarily
>> prevents the compiler from doing some of these things, or limits what
>> the user can do drastically enough to just mandate one implementation.
>
> I disagree that it limits the user drastically enough to just mandate
> one implementation. E.g. (for whatever reason) a user might want to use
> reference counting with an allocator that does not allow individual
> deallocation of objects. (It is then sufficient to have only a single
> reference count, for the allocator itself.)

Point taken. The question is then whether we want to give the user control over individual inc/dec or only the deallocation process. The latter is akin to C++'s shared_ptr's deleter.

>>> How to specify the allocator for a @rc class?
>>
>> I don't know, it's a good topic for discussion. Ideas?
>
> It could be a special member that is either an alias or a reference to
> an allocator which is automatically filled by the typed part of
> std.allocator. Alternatively, one could make the references fatter and
> have an additional argument to (an overload of) opDec.

Noted, thanks.


Andrei

_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

October 28, 2015
Le 28 oct. 2015 à 14:27, Andrei Alexandrescu <andrei@erdani.com> a écrit :

> Nice notation. There is an amendment I'd need to add (I think I mentioned this already): at least in v1.0 we're considering having the callER do the increment and the callEE do the decrement. This is how D currently handles copy construction and destruction, and it turns out it has a number of advantages over C++ (where the caller does all the work).
> 
> So, the protocol in foo(getObject()) is, foo's caller gets an rvalue with the already-incremented refcount and bitblits it into the call to foo, no additional operation. The code generated by foo includes the refcount decrement.
> 
> This will make for a simple implementation for v1.0 (uses the same backend as the ctors/dtors), but we need to figure whether that is the optimal approach for manipulating refcounts.

It's always a tradeoff. What you are describing is a system where the callee "consumes" its argument. With Clang, you can get that behaviour by applying "__attribute((ns_consumed))" to a function parameter.
http://clang.llvm.org/docs/AutomaticReferenceCounting.html#consumed-parameters

A good case for the "consuming" behaviour is when you chain functions:

	O o = transformObject(getObject());

A bad case for the "consuming" convention is calling repeatedly a function with the same object parameter. It will require at a minimum one increment and one decrement for each call:

	int a = obj{+1}.evaluate(1); // callee does this{-1}
	int b = obj{+1}.evaluate(2); // callee does this{-1}
	int c = obj{+1}.evaluate(3); // callee does this{-1}

At best you could optimize like this:

	obj{+3};
	int a = obj.evaluate(1); // callee does this{-1}
	int b = obj.evaluate(2); // callee does this{-1}
	int c = obj.evaluate(3); // callee does this{-1}

Whereas if the function is non-consuming, you get this:

	int a = obj{+1}{-1}.evaluate(1);
	int b = obj{+1}{-1}.evaluate(2);
	int c = obj{+1}{-1}.evaluate(3);

Which can be simplified as this:

	obj{+1};
	int a = obj.evaluate(1);
	int b = obj.evaluate(2);
	int c = obj.evaluate(3);
	obj{-1};

... and still has room for further elision if the context allows.

Note that you can use a mix of both. Either with an explicit attribute for arguments like the one in Clang, or by having the compiler pick one or the other by recognizing some deterministic patterns in the function signature.

Supporting both also makes it possible to integrate with COM and most RC systems out there. Usually COM is non-consuming, but not always. See CoGetInterfaceAndReleaseStream:
https://msdn.microsoft.com/en-us/library/windows/desktop/ms691421(v=vs.85).aspx

-- 
Michel Fortin
michel.fortin@michelf.ca
https://michelf.ca


_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

October 28, 2015

On 10/28/2015 8:24 AM, Andrei Alexandrescu wrote:
>
> Interesting. Would it be sensible to add a restriction that no @rc object can be reachable from a global? (At least in @safe code.)

That doesn't solve the problem. It would need to be @rc objects from:

1. globals
2. outer scopes
3. fields of aggregates
4. array members
5. any data structure
_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

October 28, 2015

On 10/28/2015 11:00 AM, Timon Gehr wrote:
>
>
> Anyway, the solution is indeed to make it the responsibility of the caller to keep the borrowed object alive. I.e. when passing a non-scope reference to a scope argument, the reference count must be increased for the duration of the call. The benefit is that scope references can be duplicated arbitrarily without updating the reference count.
> This applies to globals just as well as to other cases.

Another option is, when doing an assignment to an rc handle, and the ref count goes to zero, to not delete the rc object, but to hand it to the garbage collector to eventually reap.

The advantage to this is you never have to inc/dec a ref count when passing a handle to a function. The downside is, of course, eventually the GC will have to run to reap them. But this may not be much of a problem in practice, as it can only happen on assignment (not initialization) of a non-local handle, and only happens if the ref count goes to 0.
_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

October 28, 2015
On 10/28/2015 04:01 PM, Walter Bright wrote:
> Another option is, when doing an assignment to an rc handle, and the ref
> count goes to zero, to not delete the rc object, but to hand it to the
> garbage collector to eventually reap.

Two matters:

1. Planning to let objects leak seems like a cop-out if we find ourselves in front of an insoluble problem. So it's at best an escape trap, but I'd very much suggest we don't rely on it throughout this discussion.

2. This won't work with non-GC allocators - it'll just leak.


Andrei
_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

October 28, 2015
On 10/28/2015 03:53 PM, Walter Bright wrote:
> That doesn't solve the problem. It would need to be @rc objects from:
>
> 1. globals
> 2. outer scopes
> 3. fields of aggregates
> 4. array members
> 5. any data structure

My assumption is that the compiler gets to "see" during modular analysis 2-5, but not 1. -- Andrei
_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

October 28, 2015
On 10/28/2015 08:20 PM, Andrei Alexandrescu wrote:
> On 10/28/2015 02:00 PM, Timon Gehr wrote:
>>> void bar() {
>>>      C c = new C();
>>>      [[auto __t = c; __t.refs += 2;]]
>>>      foo(c, c);
>>>      [[__t.refs -= 2;]]
>>> }
>>
>> +=2 seems arbitrary. Only one new reference is generated.
>
> I was thinking conservatively - add 1 for anything passed in, whether by
> value or reference.
> ...

By reference does not actually pass in the reference, but a reference to the reference. Ultimately there is no difference. RC does not care about how many times the same reference is counted, as long as it is counted with the same (positive) multiplicity when it is generated as when it is destroyed.

> Generally I'm very optimistic about conservative analyses - analyses
> that look at a function statically and conclude that the reference count
> can't go beyond e.g. 12 or whatever. Then upon object creation there's
> __t.refs+=12 and upon exit there's a __t-=12 and inside the function
> proper there's no other refcount bump.
>
> Basic idea being +=1 or +=100 have the same cost, and refcount doesn't
> need to precisely reflect the number of references, only >=. We can
> exploit these facts.
> ...

Actually, we do not need #references <= count.
It's just (#references > 0) -> (count > 0).
(The converse should also hold, but then #references has to include cyclic references.)

> (There are other analyses that compute conservative bounds, such as our
> well-known VRP or computing the stack frame size for a function.)
> ...

The analysis does not need to determine the maximal number of increments in the scope. They can in principle all be fused into one inc upon object creation and one dec upon exit (both multiplicity 1), with the obvious caveat that the reference may now live longer than before the transformation. Increments are then only necessary within the method body if there is a chance that the copied reference escapes.

>> Anyway, the solution is indeed to make it the responsibility of the
>> caller to keep the borrowed object alive. I.e. when passing a non-scope
>> reference to a scope argument, the reference count must be increased for
>> the duration of the call. The benefit is that scope references can be
>> duplicated arbitrarily without updating the reference count.
>> This applies to globals just as well as to other cases.
>
> Sounds interesting. So it looks like one additional hidden variable per
> reference created in a scope may be necessary in order to avoid
> complicated inc/dec for references.
> ...

IMHO it's not all that complicated even without the lowering.

_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

October 28, 2015
On 10/28/2015 06:39 PM, Timon Gehr wrote:
> Actually, we do not need #references <= count.
> It's just (#references > 0) -> (count > 0).
> (The converse should also hold, but then #references has to include
> cyclic references.)

That's right. Interesting!

>> (There are other analyses that compute conservative bounds, such as our
>> well-known VRP or computing the stack frame size for a function.)
>> ...
>
> The analysis does not need to determine the maximal number of increments
> in the scope. They can in principle all be fused into one inc upon
> object creation and one dec upon exit (both multiplicity 1), with the
> obvious caveat that the reference may now live longer than before the
> transformation. Increments are then only necessary within the method
> body if there is a chance that the copied reference escapes.
>
>>> Anyway, the solution is indeed to make it the responsibility of the
>>> caller to keep the borrowed object alive. I.e. when passing a non-scope
>>> reference to a scope argument, the reference count must be increased for
>>> the duration of the call. The benefit is that scope references can be
>>> duplicated arbitrarily without updating the reference count.
>>> This applies to globals just as well as to other cases.
>>
>> Sounds interesting. So it looks like one additional hidden variable per
>> reference created in a scope may be necessary in order to avoid
>> complicated inc/dec for references.
>> ...
>
> IMHO it's not all that complicated even without the lowering.

Fantastic. That's why you're paid the big bucks! :o)


Andrei
_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study

October 28, 2015

On 10/28/2015 3:28 PM, Andrei Alexandrescu wrote:
> On 10/28/2015 04:01 PM, Walter Bright wrote:
>> Another option is, when doing an assignment to an rc handle, and the ref
>> count goes to zero, to not delete the rc object, but to hand it to the
>> garbage collector to eventually reap.
>
> Two matters:
>
> 1. Planning to let objects leak seems like a cop-out if we find ourselves in front of an insoluble problem. So it's at best an escape trap, but I'd very much suggest we don't rely on it throughout this discussion.

We've already talked about relying on the GC to pick up cyclic graphs. I do understand the sentiment, yet I have never seen such a scheme proposed before. As such, it also may inspire new ways of thinking about how to deal with this problem.

>
> 2. This won't work with non-GC allocators - it'll just leak.
>
>

That's right.

_______________________________________________
Dlang-study mailing list
Dlang-study@puremagic.com
http://lists.puremagic.com/cgi-bin/mailman/listinfo/dlang-study