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