Can assumeSafeAppend() grab more and more capacity?

[ag0aep6g via Digitalmars-d-learn]

On 06/05/2017 11:08 PM, Ali Çehreli wrote:
> Imagine an array that wants to reuse its buffer after removing elements 
> from it. For example, a PID waiting list can remove completed elements 
> and add new ones at the end.
> 
> The code would call assumeSafeAppend like this:
> 
>      arr = arr.remove!(e => e % 2);
>      arr.assumeSafeAppend();
> 
> 1) Assuming that the array is not relocated, is it possible that the 
> capacity will grow and grow? (Imagine that a new memory page from the GC 
> beyond the current capacity becomes available? Would assumeSafeAppend() 
> grab that as capacity as well?)

As far as I understand, assumeSafeAppend only grabs the existing 
capacity. New capacity gets created when appending or by calling `reserve`.

When there's free space beyond the capacity, then appending/`reserve` 
may extend the memory block instead of relocating. A quick test says 
this is done with large arrays (multiple KiB). For smaller arrays, the 
GC likely uses pools of fixed-width chunks.

> For example, if capacity was non-zero before the two lines above, would 
> that assumeSafeAppend() call find more capacity than before?

I don't think so.

> 2) If so, is the capacity "allocated" for this buffer or can the GC use 
> those pages for other purposes, effectively reducing the array's capacity?

The spec says [1]: "one may use the .capacity property to determine how 
many elements can be appended to the array without reallocating." So the 
space indicated by `.capacity` is reserved for the array.

But I guess you should claim it by appending, so that the GC is knows 
what's happening. I.e., don't claim it by slicing a pointer.

> In other words, is having capacity a guarantee like having called 
> reserve()?

As far as I know, it's exactly the same. `reserve` makes capacity.

> 3) Bonus: Shouldn't the array specialization of std.algorithm.remove 
> call assumeSafeAppend if the array has capacity to begin with? (The 
> equivalent of following code?)
> 
>      const oldCap = arr.capacity;
>      // ... do std.algorithm.remove magic on arr ...
>      if (oldCap) {
>          arr.assumeSafeAppend();
>      }
> 
> I'm aware that there can be multiple slices with non-zero capacity until 
> one of them grabs the capacity for itself but it's ok for remove() to 
> give the capacity to just one of them.

Seems safe, but you'll have to justify claiming the capacity like that. 
How is it better than leaving it for the other slices? As it is, a user 
can do what you did there when they want the capacity. When `remove` 
claims the capacity eagerly, unrelated code may end up relocating 
without need.


[1] http://dlang.org/spec/arrays.html#resize