Array slices and copy on write

[Jonathan M Davis]

On 2011-04-03 07:29, simendsjo wrote:
> On 03.04.2011 14:55, spir wrote:
> > On 04/03/2011 02:29 PM, simendsjo wrote:
> >> D will copy the original content if a slice expands, but is the
> >> following behavior
> >> implementation specific, or part of the specification?
> >> 
> >> auto a = [0,1,2];
> >> auto b = a[0..2];
> >> a.length = 2; // is a[3] already marked for collection by the gc?
> >> assert(a.ptr == b.ptr);
> >> b.length += 1; // as b cannot reuse it even though noone is using it
> >> assert(a.ptr == b.ptr); // ooops, fails.. b is reallocated
> > 
> > As I understand it (there is no real spec for D), this is consistent
> > with the often commented design of D slices.
> > People often explain that slices are like views on (implicite or
> > explicit) ordinary arrays. Then, change on either is seen by both, just
> > like references --*except* when change require resizing.
> > Another point of view is that slices somewhat work like copy-on-write:
> > there is no actual copy until one variable value is changed, then only
> > copy happens --expect when change can happen on place.
> > 
> > Denis
> 
> I know the dangers of slices and copy on write. I was thinking of a very
> specific example. I'll try to explain better.
> 
> auto a = [0,1,2];
> auto b = a[0..2];
> a.length = 2;
> // a[3] should now not be referenced, but my guess is it's not collected
> by the gc
> assert(a.ptr == b.ptr);
> b.length += 1;
> // b could potentionally use the last part of a instead of reallocating
> // Could another implementation reuse a's old memory without reallocating?

What the GC does and doesn't choose to collect is implementation-specific and 
doesn't necessarily have anything to do with the compiler. Also, remember that 
memory allocation is done in blocks, so there's pretty much no way that the 
last element of an array would be collected simply because you shrunk the 
length of the array by one. And you may not want it to anyway. There is at 
least a chance that b.length += 1 would cause b to use the now unreferenced 
3rd element of a, so giving that one element's worth of memory to the OS could 
be very ineffecient. Regardless, whether b.length +=1 manages to avoid a 
reallocation is implementation-dependent.

You should _not_ generally rely on when you are or aren't going to get a 
memory reallocation with an array. If you want to guarantee that a 
reallocation takes place, use dup or idup. If you want to guarantee that one 
doesn't take place, then don't increase the size of any array/slice which 
points to a particular block of memory. Beyond that, you don't really have any 
guarantees about reallocation. druntime will guarantee that you don't end up 
with your arrays stomping on each other, and it will try and minimize 
reallocations, but how it does all that is implementation-dependent.

- Jonathan M  Davis