www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.container: the advent of deterministic containers

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
http://erdani.com/d/phobos/std_container.html
http://erdani.com/d/phobos/container.d

I just implemented TightArray, which is a deterministically-allocated 
container that uses reference counting to free memory when the container 
and its last range go away. I have reasons to believe TightArray is 
entirely safe to use - cannot be broken by a  safe program.

Ranges are not invalidated upon insertion and removal, but they are 
presumably slower than the built-in ranges.

The implementation is unfinished but the steps to finishing it are more 
or less trivial.


Andrei
May 30 2010
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 http://erdani.com/d/phobos/std_container.html
 http://erdani.com/d/phobos/container.d
 I just implemented TightArray, which is a deterministically-allocated
 container that uses reference counting to free memory when the container
 and its last range go away. I have reasons to believe TightArray is
 entirely safe to use - cannot be broken by a  safe program.
 Ranges are not invalidated upon insertion and removal, but they are
 presumably slower than the built-in ranges.
 The implementation is unfinished but the steps to finishing it are more
 or less trivial.
 Andrei

This sounds great at least in the case of arrays of primitives (ints, floats, etc; the common case for large arrays in scientific computing). IMHO given D's current GC the memory for very large data structures should be managed deterministically. I wonder if there's a good argument that memory for very large data structures should be managed deterministically even in the case of better (Java/C#-like) GC's, especially if they're shared across threads. IIRC these GCs don't use bump allocation and copying for very large contiguous data structures. Furthermore, in a multicore/multithreaded/parallel environment, frequent collections are a killer (ignoring parallel collectors, which no mainstream language has implemented for production use AFAIK). A few questions/comments: 1. Reviewing the code, it looks like you forgot to use GC.addRange/GC/removeRange calls to make sure that the array is scanned by the GC if it has pointers in it. What if I make a TightArray of void*s? How will it get scanned by the GC? 2. How are cycles dealt with? Although ideally they would be dealt with somehow, I don't see putting the onus on the programmer as the worst thing in the world, since TightAA is probably mostly going to be used for storing primitives and structs w/o pointer indirection anyhow.
May 30 2010