Related to my DConf 2022 lightning talk, I am noticing that D runtime's in-place array extension optimization is available only for array data that are at certain memory alignments.

I used the following program to test it. In addition to repeatedly adding an element to an array,

- 'version = neither' does not drop any element (this is "good" as well)

- 'version = bad' case drops the front element (a moving window of 1)

- 'version = good' case drops elements only when element data will hit a certain alignment value.

Is this expected?

import std.stdio;
import std.range;

// PLEASE UNCOMMENT ONLY ONE:
// version = bad;        // No in-place extension
// version = good;       // In-place extension happens
// version = neither;    // In-place extension happens

mixin assertSingleVersionOf!("bad", "good", "neither");

void main() {
  struct S {
    ubyte[4] data;  // Try different reasonable sizes.
                    // For example, 5 will not work even
                    // for the "good" case.
  }

  S[] arr;

  foreach (i; 0 .. 100_000) {
    const oldCap = arr.capacity;
    const oldPtr = arr.ptr;

    arr ~= S.init;

    if (arr.capacity != oldCap) {
      // The array needed to be extended...
      if (arr.ptr == oldPtr) {
        // ... but the pointer did not change
        writefln!"In-place extension -- element: %,s  capacity: %,s -> %,s  ptr: %s"(
          i, oldCap, arr.capacity, arr.ptr);
      }
    }

    version (neither) {
      // Do not remove any element; just extend
    }

    version (bad) {
      // Dropping 1 element inhibits in-place extension
      // (Many values other than 1 will inhibit as well.)
      arr = arr[1..$];

      // Even this does not help
      arr.assumeSafeAppend();
    }

    version (good) {
      // Dropping front elements equaling 2048 bytes works.
      // (Likely a GC magic constant.)

      enum magic = 2048;
      enum elementsPerPage = magic / S.sizeof;

      if (arr.length == elementsPerPage) {
        arr = arr[elementsPerPage..$];
      }
    }
  }
}

// A useful template that has nothing to do with this problem.
mixin template assertSingleVersionOf(args...) {
  import std.format : format;

  static assert (1 >= {
    size_t count = 0;
    static foreach (arg; args) {
      static assert (is (typeof(arg) == string));
      mixin (format!q{
        version (%s) {
          ++count;
        }
      }(arg));
    }
    return count;
  }(), format!"Please pick only one or none of %(%s, %)"([args]));
}

Ali

Thank you for the quick response.

On 8/16/22 12:31, Steven Schveighoffer wrote:
> On 8/16/22 2:11 PM, Ali Çehreli wrote:
>> Related to my DConf 2022 lightning talk, I am noticing that D
>> runtime's in-place array extension optimization is available only for
>> array data that are at certain memory alignments.
>>
>
> No, it's based on 2 factors:
>
> 1. Is it a page-size-or-greater block?

I assume the length of the new block.

> 2. Is there a free page after it?

Makes sense.

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

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);
}

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

> Note that once you reach page size, the optimization can happen, *even
> if you are only appending to an end slice*. Here's something to try:
> when the capacity is less than the "magic" number of elements, `reserve`
> that number of elements. Then the "drop one element each loop" should
> use the optimization.

.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 I seem to need is this function:

void increaseCapacityWithoutAllocating(T)(ref T[] arr) {
  // ...
}

Only the runtime seems to be able to implement that function. Can I call something in the runtime similar to how assumeSafeAppend() calls _d_arrayshrinkfit() in object.d?

>
> -Steve

Ali

On 8/16/22 19:33, Steven Schveighoffer wrote:

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

Thank you. I am appreciating this discussion a lot.

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

That's how it should be because we wouldn't want to work to know which blocks are glued.

>>  > The reason why your `bad` version fails is because when it must
>>  > reallocate, it still is only allocating 1 element.

I will get back to this 1 element allocation below.

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

I think my problem was caused by my test data being 16 bytes and (I think) the runtime picked memory from the 16-byte pool without any hope of future growth into adjacent block.

Using a 16-byte block sounds like a good strategy at first because nobody knows whether an array will get more than one element.

However, if my guess is correct (i.e. the first element of size of 16-bytes is placed on a 16-byte block), then the next allocation will always allocate memory for the second element.

One might argue that dynamic arrays are likely to have more than a single element, so the initial block should at least be twice the element size. This would cut memory allocation by 1 count for all arrays. And in my case of 1-element arrays, allocation count would be halved. (Because I pay for every single append right now.)

Of course, I can understand that there can be applications where a large number of arrays (e.g. a 2D array) may have zero-elements or one-element, in which case my proposal of allocating the first element on a e.g. 32-byte block would be wasteful.

I think such cases are rare and we incur 1 extra allocation penalty for all arrays for that strategy.

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

That all makes sense. I didn't think the meta data would be at the end but I sense it's related to the "end slice", so it's a better place there. (?)

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

That's pretty interesting and smart.

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

This is about what you and I talked about in the past and something I mentioned in my DConf lightning talk this year. I am imagining a FIFO-like cache where elements of a source range are stored. There is a sliding window involved. I want to drop the unused front elements because they are expensive in 2 ways:

1) If the elements are not needed anymore, I have to move my slice forward so that the GC collects their pages.

2) If they are not needed anymore, I don't want to even copy them to a new block because this would be expensive, and in the case of an infinite source range, impossible.

The question is when to apply this dropping of old front elements. When I need to add one more element to the array, I can detect whether this *may* allocate by the expression 'arr.length == arr.capacity' but not really though, because the runtime may give me adjacent room without allocation. So I can delay the "drop the front elements" computation because there will be no actual copying at this time.

But the bigger issue is, because I drop elements my array never gets large enough to take advantage of this optimization and there is an allocation for every single append.

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

Ok, that sounds very useful. In addition to "I can detect when it *may* allocate", I can detect whether there is adjacent free room. (I can ask for just 1 element extension; I tested; and it works.) (I guess this GC.extend has to grab a GC lock.)

However, for that to work, I seem to need the initial block pointer that the GC knows about. (My sliding array's .ptr not work, so I have to save the initial arr.ptr).

Conclusion:

1) Although understanding the inner workings of the runtime is very useful and core.memory has interesting functions, it feels too much fragile work to get exactly what I want. I should manage my own memory (likely still backed by the GC).

2) I argue that the initial allocation should be more than 1 element so that we skip 1 allocation for most arrays and 50% for my window-of-1 sliding window case.

Ali

On 8/17/22 18:31, Steven Schveighoffer wrote:

> 1. I highly recommend trying out the ring buffer solution to see if it
> helps. The disadvantage here is that you need to tie up at least a page
> of memory.

I started to think holding on to multiple pages of memory should not matter anyway. If really needed, an array of Appenders could be used; when really really needed, they may come from a free list.

Aside: I looked at Appender's implementation and saw that extending is one of its concerns as well.

> 2. All my tests using the ring buffer showed little to no performance
> improvement over just copying back to the front of the buffer. So
> consider just copying the data back to the front of an already allocated
> block.

That makes sense as well. One worry would be types with copy constructors. (I am not sure whether D is still a language where structs can freely be moved around.)

> IIRC, your data does not need to be sequential in *physical memory*,
> which means you can use a ring buffer that is segmented instead of
> virtually mapped, and that can be of any size.

I thought about that as well. But I would like the sizes of blocks (Appenders?) be equal in size so that opIndex still can provide O(1) guarantee. (Compute the block + an offset.)

>
> -Steve

Ali

On 8/17/22 19:27, Steven Schveighoffer wrote:
> On 8/17/22 10:09 PM, Ali Çehreli wrote:
>>  > IIRC, your data does not need to be sequential in *physical memory*,
>>  > which means you can use a ring buffer that is segmented instead of
>>  > virtually mapped, and that can be of any size.
>>
>> I thought about that as well. But I would like the sizes of blocks
>> (Appenders?) be equal in size so that opIndex still can provide O(1)
>> guarantee. (Compute the block + an offset.)
>
> It's still O(1). You only have 2 slices to worry about.

Sometimes 2... I wanted to leave the sliding window width dynamic.

So, there will be M buffers, not 2. If their lengths are not equal, opIndex must be O(M). M is expected to be small but still...

M buffers of 'pageSize - (meta data).sizeof' each.

BeerConf... Sure... :)

Ali