www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Reference Counting Template

reply dsimcha <dsimcha yahoo.com> writes:
I'm starting to think it would be both useful and feasible to have a general
reference counting template struct in Phobos:

struct RefCounted(T, alias onZero) {
    // Implementation
}

Basically, you would provide it with a type T that it's supposed to count
references to and an action (a function that takes a T and returns void)
that's supposed to happen when the amount of references drop to zero.

Reference counting is a pretty useful general technique for managing resources
that can't have cycles and I think it makes sense to have a generic template
for it instead of having people reimplement the same code over and over for
file handles, large arrays of primitives that they allocate on the C heap and
want freed deterministically, database connections, etc.  Does this sound
worthwhile?
Dec 13 2009
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
dsimcha: 

 Reference counting is a pretty useful general technique for managing resources
 that can't have cycles and I think it makes sense to have a generic template
 for it instead of having people reimplement the same code over and over for
 file handles, large arrays of primitives that they allocate on the C heap and
 want freed deterministically, database connections, etc.  Does this sound
 worthwhile?


In real-world D programs the built-in GC is not enough, and forcing the
programmer to re-invent everything is bad in a modern language. So putting
alternative allocators (or resource managers as in your case) in Phobos will be
necessary. For example I have D1 programs that become two times faster when I
use a pool allocator.

Your reference counter can even contain a cycle detection&break routine.

One memory allocator (that can be used in D with memory from the C heap too)
that I'd like to see in Phobos is a Hierarchical allocator, this is the
simplest, really easy to use, you can allocate memory blocks with a tree
topology and then free a whole subtree. It's easy to remember and use this API:
http://www.swapped.cc/halloc/
This is a more complex implementation, that's more complex to use too:
http://talloc.samba.org/

Bye,
bearophile
Dec 13 2009
prev sibling next sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
dsimcha wrote:
...

  Does this sound worthwhile?


Yes, we need this.
Dec 13 2009
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:

 I'm starting to think it would be both useful and feasible to have a general
 reference counting template struct in Phobos:
 
 struct RefCounted(T, alias onZero) {
     // Implementation
 }
 
 Basically, you would provide it with a type T that it's supposed to count
 references to and an action (a function that takes a T and returns void)
 that's supposed to happen when the amount of references drop to zero.
 
 Reference counting is a pretty useful general technique for managing resources
 that can't have cycles and I think it makes sense to have a generic template
 for it instead of having people reimplement the same code over and over for
 file handles, large arrays of primitives that they allocate on the C heap and
 want freed deterministically, database connections, etc.  Does this sound
 worthwhile?


Sounds great.

Andrei
Dec 13 2009
prev sibling next sibling parent reply Lutger <lutger.blijdestijn gmail.com> writes:
What are you planning to with multithreading? 

With the current type system, is it possible to statically detect inside the 
template if the refcount is used in shared scenario's, and base the 
implementation on that information? That would be ideal, if it is indeed 
possible.

std.stdio.File is refcounted, perhaps you can see to replace it's 
implementation with your template. 

Thanks you for this, I think it's great that D will have it out-of-the-box.
Dec 14 2009
next sibling parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Mon, 14 Dec 2009 11:04:15 +0300, Lutger <lutger.blijdestijn gmail.com>  
wrote:


 What are you planning to with multithreading?

 With the current type system, is it possible to statically detect inside  
 the
 template if the refcount is used in shared scenario's, and base the
 implementation on that information? That would be ideal, if it is indeed
 possible.

 std.stdio.File is refcounted, perhaps you can see to replace it's
 implementation with your template.

 Thanks you for this, I think it's great that D will have it  
 out-of-the-box.



In fact, multi-threading should be easy: shared versions of opAssign would  
use atomicIncrement(_counter), whereas thread-local would fallback to  
++_counter.
Dec 14 2009
parent Lutger <lutger.blijdestijn gmail.com> writes:
Denis Koroskin wrote:


 On Mon, 14 Dec 2009 11:04:15 +0300, Lutger <lutger.blijdestijn gmail.com>
 wrote:
 

 What are you planning to with multithreading?

 With the current type system, is it possible to statically detect inside
 the
 template if the refcount is used in shared scenario's, and base the
 implementation on that information? That would be ideal, if it is indeed
 possible.

 std.stdio.File is refcounted, perhaps you can see to replace it's
 implementation with your template.

 Thanks you for this, I think it's great that D will have it
 out-of-the-box.



 
 In fact, multi-threading should be easy: shared versions of opAssign would
 use atomicIncrement(_counter), whereas thread-local would fallback to
 ++_counter.


Awesome, that means you can still write a fast(er) single-threaded version 
of anything without the client even having to think about it!
Dec 14 2009
prev sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Lutger (lutger.blijdestijn gmail.com)'s article

 What are you planning to with multithreading?
 With the current type system, is it possible to statically detect inside the
 template if the refcount is used in shared scenario's, and base the
 implementation on that information? That would be ideal, if it is indeed
 possible.


I was thinking just make all increments and decrements of the reference count
field atomic.  x86 and probably most other architectures have an atomic
increment
and atomic decrement snippet.  If the full semantics of shared get implemented,
I'll reconsider.


 std.stdio.File is refcounted, perhaps you can see to replace it's
 implementation with your template.
 Thanks you for this, I think it's great that D will have it out-of-the-box.


Yeah, that's what gave me the idea.  That and working with very large data
structures for which false pointers and slow GC times bite hard, and I'd rather
allocate on the C heap and delete deterministically.





Yeah, good GC is part of the answer, but I don't understand why they don't even
attempt to make it easy to manage other resources.  Finally blocks are basically
an invitation to write tons of boilerplate code.
Dec 14 2009
prev sibling parent LMB <anonymous nowhere.com> writes:
dsimcha Wrote:


 I'm starting to think it would be both useful and feasible to have a general
 reference counting template struct in Phobos:
 [...]
 Does this sound
 worthwhile?


Yes it does :-)

I believe this would be great for working with many C-based APIs. I recently
needed this when creating yet another wrapper for SQLite. I did my own (not
reusable, and possibly buggy -- I am just beginning to learn D) implementation
of referencing counting with some help from the people on these forums, but I
really wished Phobos had it ready to use.

LMB
Dec 14 2009