• Andrei Alexandrescu (11/11) May 30 2010 http://erdani.com/d/phobos/std_container.html
• dsimcha (19/30) May 30 2010 This sounds great at least in the case of arrays of primitives (ints, fl...

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

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.