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?)

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

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?

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

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.

Here is a test program that plays with this idea, starting with two identical slices with same capacity:

import std.stdio;
import std.array;
import std.algorithm;

void myRemove(ref int[] arr) {
    const cap = arr.capacity;

    arr = arr.remove!(e => e % 2);

    if (cap) {
        arr.assumeSafeAppend();
    }
}

void info(arrays...)(string title) {
    writefln("\n%s", title);
    foreach (i, arr; arrays) {
        writefln("  %s - ptr: %s, len: %s, cap: %s",
                 (arrays[i]).stringof, arr.ptr, arr.length, arr.capacity);
    }
}

void main() {
    auto a = [ 1, 2, 3, 4 ];
    auto b = a;

    info!(a, b)("before myRemove(a)");

    myRemove(a);
    info!(a, b)("after  myRemove(a)");

    myRemove(b);
    info!(a, b)("after myRemove(b)");
}

before myRemove(a)
  a - ptr: 7F15F40D4060, len: 4, cap: 7
  b - ptr: 7F15F40D4060, len: 4, cap: 7

after  myRemove(a)
  a - ptr: 7F15F40D4060, len: 2, cap: 7  <== 'a' grabbed capacity
  b - ptr: 7F15F40D4060, len: 4, cap: 0  <==

after myRemove(b)
  a - ptr: 7F15F40D4060, len: 2, cap: 7
  b - ptr: 7F15F40D4060, len: 3, cap: 0

Ali

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

On 06/05/2017 03:16 PM, ag0aep6g wrote:

> 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.

Cool. Thanks!

>> 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.

My justification was that it feels to be a bug anyway to have multiple slices to data where one is about to remove() elements from (hence jumbling the others' elements). My thinking was, if capacity were not guaranteed for any slice to begin with, then why not pull it under some slices arbitrarily. But I agree with you that remove() should still not decide on its own.

However, I've noticed an inconsistency when writing the previous paragraph: If capacity is guaranteed reserved space, multiple slices start their lives with a lie! :) From my earlier program:

    auto a = [ 1, 2, 3, 4 ];
    auto b = a;

Both of those slices have non-zero capacity yet one of them will be the lucky one to grab it. Such semantic issues make me unhappy. :-/

Ali

On Monday, 5 June 2017 at 23:17:46 UTC, Ali Çehreli wrote:
>     auto a = [ 1, 2, 3, 4 ];
>     auto b = a;
>
> Both of those slices have non-zero capacity yet one of them will be the lucky one to grab it. Such semantic issues make me unhappy. :-/
>
> Ali

You have to remember that slices don't own their memory. So while capacity show a guaranteed reserved memory, it is reserved for the dynamic array the slice has a window into.

Remove probably shouldn't try to reclaim capacity, while it is destructive for any other slice, it shouldn't make string appending also destructive.

untested:

     auto a = [ 1, 2, 3, 4 ];
     auto b = a[$-1, $];
     a.remove(2);
     assert(b == [4]);
     a ~= 6;
     assert(b == [4]);

On 06/06/2017 12:13 PM, Jesse Phillips wrote:
> On Monday, 5 June 2017 at 23:17:46 UTC, Ali Çehreli wrote:
>>     auto a = [ 1, 2, 3, 4 ];
>>     auto b = a;
>>
>> Both of those slices have non-zero capacity yet one of them will be
>> the lucky one to grab it. Such semantic issues make me unhappy. :-/
>>
>> Ali
>
> You have to remember that slices don't own their memory. So while
> capacity show a guaranteed reserved memory, it is reserved for the
> dynamic array the slice has a window into.
>
> Remove probably shouldn't try to reclaim capacity, while it is
> destructive for any other slice, it shouldn't make string appending also
> destructive.
>
> untested:
>
>      auto a = [ 1, 2, 3, 4 ];
>      auto b = a[$-1, $];
>      a.remove(2);
>      assert(b == [4]);
>      a ~= 6;
>      assert(b == [4]);

Agreed.

The only issue remaining for me is the part that you've quoted: If we can trust capacity per spec, like we would trust after calling reserve(), then a and b in my code above are counter examples where both a and b have capacity initially but one of them will lose its capacity as soon as the other one gains an element.

Although I like the fact that the current semantics are more efficient (because capacity is given lazily), they conflict with the other part of the spec.

Ali

On 06/07/2017 12:12 AM, Ali Çehreli wrote:
> On 06/06/2017 12:13 PM, Jesse Phillips wrote:
>  > On Monday, 5 June 2017 at 23:17:46 UTC, Ali Çehreli wrote:
>  >>     auto a = [ 1, 2, 3, 4 ];
>  >>     auto b = a;
[...]
> 
> The only issue remaining for me is the part that you've quoted:

Jesse Phillips didn't quote the spec. I guess you mean me.

For reference, the spec quote again [1]: "one may use the .capacity property to determine how many elements can be appended to the array without reallocating."

> If we can trust capacity per spec, like we would trust after calling reserve(), then a and b in my code above are counter examples where both a and b have capacity initially but one of them will lose its capacity as soon as the other one gains an element.

`reserve` works the same. `reserve`d capacity is still capacity and it can get snapped away by another slice.

----
void main()
{
    import std.stdio;

    int[] foo;
    writeln(foo.capacity); /* 0 */

    foo.reserve(10);
    writeln(foo.capacity); /* 15 */

    int[] bar = foo;
    bar ~= 1;
    writeln(foo.capacity); /* 0 -- bar took the capacity */
    writeln(bar.capacity); /* 15 */
}
----

You understand the spec to say that because `foo.capacity` is 15 at one point, you should then be able to put 15 elements into `foo` without relocation. And what `bar` does in the meantime shouldn't matter.

I don't think the spec is supposed to make that strong a guarantee, but I see how it can be interpreted that way. Maybe it should be reworded/amended to describe the actual behavior more precisely.


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

On Wednesday, June 07, 2017 07:43:06 ag0aep6g via Digitalmars-d-learn wrote:
> You understand the spec to say that because `foo.capacity` is 15 at one point, you should then be able to put 15 elements into `foo` without relocation. And what `bar` does in the meantime shouldn't matter.
>
> I don't think the spec is supposed to make that strong a guarantee, but I see how it can be interpreted that way. Maybe it should be reworded/amended to describe the actual behavior more precisely.

Given the nature of dynamic arrays in D, it doesn't actually make sense to guarantee the capacity when another dynamic array referring to the same memory does something which could affect that capacity. As far as I can tell, it would actually be impossible to do so, because the runtime doesn't actually have any idea how many dynamic arrays refer to the same memory without doing the work that it would do with a collection of the GC to find everything that points to that block of memory. For it to work otherwise would basically require that a dynamic array manage its own memory rather than having the GC do it. The fact that a dynamic array in D is just a struct with a pointer and a length pretty much forces the semantics that we currently have.

- Jonathan M Davis

On Wednesday, 7 June 2017 at 05:43:06 UTC, ag0aep6g wrote:
> [snip]

It seems to me this is a topic worthy of a more in-depth article. If only I felt up to that. :p

When you create a slice 'a' in D (with the current GC and druntime, at least), what happens behind the scenes is the allocator chops off a block of N bytes, where N is some number larger than a.length*typeof(a[0]).sizeof. For an array of two ints, N is 16.
For good measure, let's make a copy 'b' of that slice (it will come in handy later):

int[] a = [1, 2];
int[] b = a;

import std.stdio;
writeln(a.capacity);
> 3
writeln(b.capacity);
> 3

The capacity is 3. Intriguing, as a block of 16 bytes should be able to hold 4 ints.

We can ask the GC for more info on this block:

import core.memory;
auto info = GC.query(a.ptr);
writefln("0x%x, %s, %s ", info.base, info.size, info.attr);
> 0x2211010, 16, 10

That's the pointer to the start of the block, the size of the block, and various attributes (appendable, e.g.).
We can get the raw data of the block:

auto block = (cast(ubyte*)info.base)[0..info.size];
writeln(block);
> [1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8]

We can see our 1 and 2 in there, and a curious 8 at the end. That's the currently used data, in bytes. That's also the reason the capacity is 3, not 4 - this info has to live somewhere. If we were to append another element, and print the data again:

a ~= 3;
writeln(block);
> [1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 12]

See how the last byte changed to a 12? That just so happens to be a.length*int.sizeof.

Remember how we made a copy of the slice above? The copy's capacity is now 0, while a's capacity is 3. The algorithm for capacity is actually pretty simple:

int capacity;
if (a.length*int.sizeof == block[$-1])
    capacity = (block.length - 1) / int.sizeof;
else
    capacity = 0;
writeln(capacity);
> 3

What happens when we call assumeSafeAppend?

b.assumeSafeAppend;
writeln(block);
> [1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 8]

Hey, the 'used' byte is 8 again. That means a.capacity is 0, while b.capacity is 3.

Now for a curious thing: what happens to a's capacity when we append to b?

b ~= 4;
writeln(a.capacity);
> 3

As above, the length of a in bytes equals the used bytes in the allocated memory block, and so both a and b have capacity again.

This has of course overwritten a[2], which used to be 3 and is now 4. assumeSafeAppend breaks part of D's type system for optimization purposes, and this is the result.

Note that the details in this post are only correct for small blocks (<=256 bytes). For larger blocks, the 'used' field is larger, but the algorithms and concepts are the same.

For the actual implementation of a.capacity, you can have a look-see at https://github.com/dlang/druntime/blob/master/src/rt/lifetime.d#L734, which is called from https://github.com/dlang/druntime/blob/master/src/object.d#L2968.

--
  Biotronic

On 6/7/17 3:56 AM, Biotronic wrote:
> On Wednesday, 7 June 2017 at 05:43:06 UTC, ag0aep6g wrote:
>> [snip]
>
> It seems to me this is a topic worthy of a more in-depth article. If
> only I felt up to that. :p

Your understanding and explanation is excellent actually!

>
> When you create a slice 'a' in D (with the current GC and druntime, at
> least), what happens behind the scenes is the allocator chops off a
> block of N bytes, where N is some number larger than
> a.length*typeof(a[0]).sizeof. For an array of two ints, N is 16.
> For good measure, let's make a copy 'b' of that slice (it will come in
> handy later):
>
> int[] a = [1, 2];
> int[] b = a;
>
> import std.stdio;
> writeln(a.capacity);
>> 3
> writeln(b.capacity);
>> 3
>
> The capacity is 3. Intriguing, as a block of 16 bytes should be able to
> hold 4 ints.
>
> We can ask the GC for more info on this block:
>
> import core.memory;
> auto info = GC.query(a.ptr);
> writefln("0x%x, %s, %s ", info.base, info.size, info.attr);
>> 0x2211010, 16, 10
>
> That's the pointer to the start of the block, the size of the block, and
> various attributes (appendable, e.g.).
> We can get the raw data of the block:
>
> auto block = (cast(ubyte*)info.base)[0..info.size];
> writeln(block);
>> [1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8]
>
> We can see our 1 and 2 in there, and a curious 8 at the end. That's the
> currently used data, in bytes. That's also the reason the capacity is 3,
> not 4 - this info has to live somewhere. If we were to append another
> element, and print the data again:
>
> a ~= 3;
> writeln(block);
>> [1, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 12]
>
> See how the last byte changed to a 12? That just so happens to be
> a.length*int.sizeof.

To be more specific, for blocks <= 256 bytes, 1 byte is reserved at the end of the array to store the length. For blocks > 256 bytes and <= 2048 bytes, 2 bytes are reserved at the end of the block to store the length of the array. For larger blocks, those are PAGE size and larger, and they have a special feature. Such blocks are not limited to a power of 2, and can be extended literally in-place by tacking on additional PAGEs. I wanted to just put a size_t at the end, but my problem with this is that the length then would move around as you appended or shrunk blocks. Given how the runtime works, it's possible that 2 threads could be potentially appending at the same time to a shared array, so I decided to store it at the beginning of the block instead.

I would actually like to replace this mechanism with one that stores the length outside the block and into a separate memory space, as it is horrible for caches. Allocate a page of bytes, and you actually get 2 pages - size_t.sizeof.

Note, for types with destructors, more bytes are reserved to store the type info of the array elements. I didn't write that part, so I'm not 100% sure how it works.

> Now for a curious thing: what happens to a's capacity when we append to b?
>
> b ~= 4;
> writeln(a.capacity);
>> 3
>
> As above, the length of a in bytes equals the used bytes in the
> allocated memory block, and so both a and b have capacity again.

Yes, for this reason, calling assumeSafeAppend is unsafe and can *never* be part of the normal treatment of arrays. It is on you, the programmer, to ensure that no references to the no-longer-allocated portion of the array exist. The compiler can't ensure it, a library function can't ensure it, and they are similar to dangling pointers.

Only a library type which encapsulates the array completely can use assumeSafeAppend.

For example, imagine if these are immutable arrays, you have now overwritten immutable data!

-Steve