www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Reference counting with fat pointers

reply "Kagamin" <spam here.lot> writes:
http://wiki.dlang.org/FatPointer
Thoughts on possible implementation of reference counting.
Mar 30 2014
parent reply "Kagamin" <spam here.lot> writes:
Looks like I got the core logic working.

The scheme takes advantage of D type system and distinction 
between shared and unshared data to decide on interlocked 
reference counting at compile time. Unshared mutable data and 
shallow shared data (like strings) are counted with the fastest 
possible non-atomic arithmetic. Cycles should be handled by the 
user, see an example at the end. Language interface is not 
considered, assess if the approach itself is ok.
Jul 25 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Friday, 25 July 2014 at 21:01:00 UTC, Kagamin wrote:

 Looks like I got the core logic working.

 The scheme takes advantage of D type system and distinction 
 between shared and unshared data to decide on interlocked 
 reference counting at compile time. Unshared mutable data and 
 shallow shared data (like strings) are counted with the fastest 
 possible non-atomic arithmetic. Cycles should be handled by the 
 user, see an example at the end. Language interface is not 
 considered, assess if the approach itself is ok.


Interesting proposal. It seems that you want to change the 
default for pointers in D, but Walter will probably not like that 
;-). But I wonder how much language support this actually needs, 
much of it seems implementable with templates, which is probably 
much more acceptable.

Some random comments:


 Scoped: "The reference count is incremented when escaped or 
 copied to a fat pointer."


Could you explain that? A scoped pointer can by definition never 
be escaped; therefore there should be no need to pass the 
reference counter along.


 Function parameters: "Caller doesn't increment the counter when 
 passing a pointer as a function argument."


There are some corner cases here. For example when an r-value is 
moved into a function as an argument. The callee will not 
decrement the RC of its parameters, with the consequence that the 
RC never goes to 0. There might be other problems, in particular 
in the presence of optimizations.

It's probably safer just to keep the traditional behaviour of 
reference counting, without specific optimizations: Increment on 
copying, decrement on destruction. Of course this is inefficient, 
but `scope` can ameliorate that significantly. There needs to be 
language support for implicit conversion to scope for certain 
types (maybe as part of implicit conversion in general), and 
Phobos needs to use scope as much as possible. See also my 
writeup on borrowing, will add more examples there:
http://wiki.dlang.org/User:Schuetzm/scope
Jul 26 2014
next sibling parent reply "Kagamin" <spam here.lot> writes:
On Saturday, 26 July 2014 at 10:49:25 UTC, Marc Schütz wrote:

 Interesting proposal. It seems that you want to change the 
 default for pointers in D, but Walter will probably not like 
 that ;-). But I wonder how much language support this actually 
 needs, much of it seems implementable with templates, which is 
 probably much more acceptable.


What language interface should be provided for RC is up to 
debate. Getting it working at the binary level is problematic 
enough, so I focused on it.


 Some random comments:


 Scoped: "The reference count is incremented when escaped or 
 copied to a fat pointer."


 Could you explain that? A scoped pointer can by definition 
 never be escaped; therefore there should be no need to pass the 
 reference counter along.


Disallowing escaping of scoped parameters implies strict scoping 
can work. I was trying to get escaping working. It's easy to deny 
it if the need be.


 Function parameters: "Caller doesn't increment the counter 
 when passing a pointer as a function argument."


 There are some corner cases here. For example when an r-value 
 is moved into a function as an argument. The callee will not 
 decrement the RC of its parameters, with the consequence that 
 the RC never goes to 0. There might be other problems, in 
 particular in the presence of optimizations.


Ouch, probably there is the same problem with tail call 
optimization. As of now, I was trying to get sharing and casting 
work, protocol for function parameters needs more work, will 
think about conservative counting here.


 See also my writeup on borrowing, will add more examples there:
 http://wiki.dlang.org/User:Schuetzm/scope


Hmm, if you got strict scoping work, that will be interesting.
Jul 26 2014
parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Saturday, 26 July 2014 at 12:43:28 UTC, Kagamin wrote:

 On Saturday, 26 July 2014 at 10:49:25 UTC, Marc Schütz wrote:

 See also my writeup on borrowing, will add more examples there:
 http://wiki.dlang.org/User:Schuetzm/scope


 Hmm, if you got strict scoping work, that will be interesting.


Well, I'm pretty convinced it is possible, and it isn't even too 
complex, i.e. it doesn't need flow analysis. I'm just not in a 
position to implement it. But at least I can try to make a DIP. 
Walter seems not too opposed to it, he recently mentioned `scope` 
as one of the open tasks that need to be solved.
Jul 26 2014
prev sibling next sibling parent reply "Kagamin" <spam here.lot> writes:
On Saturday, 26 July 2014 at 10:49:25 UTC, Marc Schütz wrote:

 There are some corner cases here. For example when an r-value 
 is moved into a function as an argument. The callee will not 
 decrement the RC of its parameters, with the consequence that 
 the RC never goes to 0. There might be other problems, in 
 particular in the presence of optimizations.


How about this: an r-value is moved to caller's stack, then 
passed to the callee? This way the callee still won't have to 
maintain the counter. And this probably prohibits tail call 
optimization.
Jul 26 2014
parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Saturday, 26 July 2014 at 13:01:13 UTC, Kagamin wrote:

 On Saturday, 26 July 2014 at 10:49:25 UTC, Marc Schütz wrote:

 There are some corner cases here. For example when an r-value 
 is moved into a function as an argument. The callee will not 
 decrement the RC of its parameters, with the consequence that 
 the RC never goes to 0. There might be other problems, in 
 particular in the presence of optimizations.


 How about this: an r-value is moved to caller's stack, then 
 passed to the callee? This way the callee still won't have to 
 maintain the counter. And this probably prohibits tail call 
 optimization.


Yes. And it needs stack unwinding on exceptions, but this is 
needed anyway.

On the other hand, if `scope` works and is used wherever 
possible, all of this probably doesn't matter too much. Most 
utility functions would just take `scope`, and won't need to pay 
the costs.
Jul 26 2014
prev sibling next sibling parent "Kagamin" <spam here.lot> writes:
Added protocol for parameters, COM and Objective-C.

On Saturday, 26 July 2014 at 10:49:25 UTC, Marc Schütz wrote:

 Interesting proposal. It seems that you want to change the 
 default for pointers in D, but Walter will probably not like 
 that ;-). But I wonder how much language support this actually 
 needs, much of it seems implementable with templates, which is 
 probably much more acceptable.


Also added escaping and uniqueness checks. Because RC tracks all 
references it becomes possible to check if scoped data was 
escaped or non-unique unshared data was casted to shared. Code 
written for GC can benefit from these checks too, it would be 
beneficial, if these checks could be applicable to such code too 
without modification.
Jul 26 2014
prev sibling parent IGotD- <nise nise.com> writes:
On Saturday, 26 July 2014 at 10:49:25 UTC, Marc Schütz wrote:

 Interesting proposal. It seems that you want to change the 
 default for pointers in D, but Walter will probably not like 
 that ;-). But I wonder how much language support this actually 
 needs, much of it seems implementable with templates, which is 
 probably much more acceptable.


We should not change the default behaviour of the pointers in D. 
However, we can add a fat pointer type, Let's say

int^ p = new int;

That would have zero breaking changes. I would even take further 
and allow several types of fat pointers in order to have allow 
several different types of fat pointers.

int^(RefCounted) = new int;

What happens if.

auto p = new int;

Well, in order not to break anything we have make p an int*.

Fat pointers are obviously needed but nothing happens. Why?
Jun 24 2020