Strange behavior on shrinking a Dynamic Array -- Capacity reduces to 0

[Steven Schveighoffer]

On Wed, 22 Jun 2011 23:38:30 -0400, d coder <dlang.coder at gmail.com> wrote:

> Hello List
>
> As per TDPL and D documentation, shrinking a dynamic array should not
> relocate it. But that is exactly what is happening.
> On shrinking an array, its capacity is getting reduced to 0. Surprisingly
> the capacity after a shrink is even less than the length
> of the array. As a result the array gets relocated as soon as another
> element is added to it.

A slice capacity of 0 does *not* indicate that 0 bytes are stored in the  
slice, it indicates that appending to the slice will reallocate into a new  
block.  It's a special token meaning "any append to this slice will  
reallocate".

There have been a few people that suggested capacity should return *at  
least* the number of bytes in the slice.  However, the zero indicator can  
be useful.  It's easier to check for, generates more efficient code when  
checking, plus the distinction between "not appendable" and "appendable,  
but the current block is full" can be very important.  We would lose this  
distinction if the default return was the length of the slice.

>
> I have to call reserve again after shrinking it to make sure that the  
> array
> is not relocated.

In fact, it is relocated.  Reserve will not overwrite data that is already  
valid, so it will reallocate the slice into a new array that can hold the  
requested size.

There is a function that allows you to reestablish appendability without  
reallocating:  assumeSafeAppend().  Call this on a slice, and it will  
become appendable again (non-zero capacity) at its current location.   
However, be cautious as this will *overwrite* any data that was valid  
after the slice.  This function has no effect on slices of non-heap data.


> import std.stdio;
>
> void main() {
>   uint [] arr;
>   reserve(arr, 2048);

The above line will allocate an array, and set arr to the first 2048  
elements.

>   writeln("After reservation:");
>   writefln("arr is at: %10s, length: %6s, capacity %6s",
>    arr.ptr, arr.length, capacity(arr));
>   // Grow the array
>   for (size_t i = 0; i < 64; ++i) arr ~= i;
>
>   writeln("After appending:");
>   writefln("arr is at: %10s, length: %6s, capacity %6s",
>    arr.ptr, arr.length, capacity(arr));

I expect arr.ptr to be unchanged, arr.length to be 64, and capacity to be  
unchanged.

>   arr.length = 32;

Note that even though you have effectively cut off 32 elements from your  
slice that latter data is *still valid*.  Another slice could be  
referencing that data, which is why arr is no longer appendable.

>   // reserve(arr, 2048); // does not relocate if uncommented
>
>   writeln("After setting length:");
>   writefln("arr is at: %10s, length: %6s, capacity %6s",
>    arr.ptr, arr.length, capacity(arr));

If you leave reserve commented out, I'd expect arr.ptr to remain  
unchanged, length to be 32, and capacity to be 0 (not appendable)
If you uncomment reserve, then arr.ptr will have moved, length will be 32,  
and capacity will be >= 2048.

>   // grow the array again
>   for (size_t i = 0; i < 32; ++i) arr ~= i;
>   writeln("After appending again:");
>   writefln("arr is at: %10s, length: %6s, capacity %6s",
>    arr.ptr, arr.length, capacity(arr));

Regardless of reserve, arr.ptr will have changed from it's original  
allocation, arr.length == 64 and capacity will vary depending on whether  
reserve was called or not.

-Steve