In-place extension of arrays only for certain alignment?

[Steven Schveighoffer]

On 8/16/22 4:53 PM, Ali Çehreli wrote:
> On 8/16/22 12:31, Steven Schveighoffer wrote:
>  >
>  > No, it's based on 2 factors:
>  >
>  > 1. Is it a page-size-or-greater block?
> 
> I assume the length of the new block.

No, the length of the *existing* block.

Everything in the memory allocator is in terms of pages. A pool is a 
section of pages. The large blocks are a *multiple* of pages, whereas 
the small blocks are pages that are *divided* into same-sized chunks.

When you want to allocate a block, if it's a half-page or less, then it 
goes into the small pool, where you can't glue 2 blocks together.

If it's greater than 1/2 page, then it needs page+ sized blocks. These 
are too big really to set aside, so the allocator will just grab some 
pool that has enough free pages, and return it. These blocks can be 
stitched together depending on what is needed. Once freed, they can also 
be split up into pages.

It's here where the capacity can grow without copying.

>  > The reason why your `bad` version fails is because when it must
>  > reallocate, it still is only allocating 1 element.
> 
> That part I still don't understand. The same block of e.g. 16 bytes 
> still has room. Why not use that remaining portion?

It does until it doesn't. Then it needs to reallocate.

Note that if you remove the front element, then you are pointing at a 
*slice* of the array.

Maybe some ASCII art? `A` is "used by the current slice", `x` is 
"allocated, but not referenced by the array". `.` is "part of the block 
but not used (i.e. can grow into this)". `M` is "metadata"

```d
auto arr = new ubyte[10];      // AAAA AAAA AA.. ...M
arr = arr[1 .. $];             // xAAA AAAA AA.. ...M
arr ~= 0;                      // xAAA AAAA AAA. ...M
arr ~= 0;                      // xAAA AAAA AAAA ...M
arr = arr[3 .. $];             // xxxx AAAA AAAA ...M
arr ~= cast(ubyte[])[1, 2, 3]; // xxxx AAAA AAAA AAAM // full!
arr ~= 1;                      // AAAA AAAA AAAA ...M // reallocated! 
arr.ptr has changed
```

Note in the last instance, it has now moved into a different 16-byte 
block -- the original is still intact, but just not pointed at. It will 
be garbage collected eventually.

But you can see that it only allocates enough to hold what the slice 
already contains + the new elements.

> 
> Here is a simpler test with better-than-expected results. Array c is 
> what I want to do. In this test it works and I don't even need to call 
> assumeSafeAppend() (this must be what you call "end slice"):
> 
> import std.stdio;
> 
> void main() {
>    ubyte[] a;
>    a ~= 0;
>    a.length = 0;
>    a.assumeSafeAppend();         // Needed
>    assert(a.capacity == 15);
> 
>    // Essentially, the same as above
>    ubyte[] b;
>    b ~= 0;
>    b = b[0..0];
>    b.assumeSafeAppend();        // Needed
>    assert(b.capacity == 15);
> 
>    ubyte[] c;
>    c ~= 0;
>    c = c[1..$];
>    // c.assumeSafeAppend();
>    assert(c.capacity == 14);
> }

Yes, the "appendability" of an array slice depends on whether it *ends* 
at the end of the "used" space. Otherwise, if it ends earlier, appending 
would stomp on memory possibly referenced elsewhere. If it ends later, 
then you did something wrong in your code, and now the situation is 
corrupted.

>  > metadata (e.g. typeinfo for destruction and append capacity).
> 
> I think it is 16 bytes total (on 64 bits): void* + size_t and I see this 
> when I print .ptr: The change is always 0x10.

Metadata isn't always stored. Plus, it's optimized for the block size. 
For example, any block that is 256 bytes or less only needs a single 
byte to store the "used" space.

The TypeInfo needed for destruction of array elements is only stored if 
needed (e.g. an array of `int` does not need one).

> .reserve sounds promising but it will sometimes allocate memory and move 
> elements even if I will not really need e.g. more than just one more 
> element. (In my case, I may not know how many will be needed.) In other 
> words, I really don't know how much to reserve.

What is your focus? Why do you really want this "optimization" of gluing 
together items to happen?

> 
> What I seem to need is this function:
> 
> void increaseCapacityWithoutAllocating(T)(ref T[] arr) {
>    // ...
> }

You can make one with:

https://dlang.org/phobos/core_memory.html#.GC.extend

-Steve