Can assumeSafeAppend() grab more and more capacity?

[Steven Schveighoffer via Digitalmars-d-learn]

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