Re: In-place extension of arrays only for certain alignment?
On 8/18/22 1:16 AM, Ali Çehreli wrote: 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... Once you need more size, you can reallocate (it should stabilize). A ring buffer of N values where N doesn't change should only require one buffer, 2 slices of that buffer. -Steve
Re: In-place extension of arrays only for certain alignment?
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
Re: In-place extension of arrays only for certain alignment?
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. Perhaps next beerconf we can discuss! -Steve
Re: In-place extension of arrays only for certain alignment?
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
Re: In-place extension of arrays only for certain alignment?
On 8/17/22 2:40 PM, Ali Çehreli wrote: On 8/16/22 19:33, Steven Schveighoffer wrote: 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. A 16-byte element size must be put in a 32-byte block, you still need one byte for the metadata. 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.) So yes, if you have a 32-byte block for 16-byte elements, it means you can only fit one element in the block. If you are using a sliding window approach, where you remove the first element and then append another, you will in effect reallocate on every append. Using the append/popFront mechanism to implement your sliding window is going to perform badly. Appending is not designed to make this situation perform well. 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. (?) It's for alignment. If I put 1 byte at the front, this means I have to always skip 7 or 15 more bytes (depending on alignment requirements). BUT, I put the metadata at the front on big (page+ size) blocks, because I can both afford to skip 16 bytes in a block of 4096, and if you extend the block, there is no need to move the metadata later. Consider that the metadata lookup cache could be out of date if it had to move. > 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. Ah! I actually have a solution for this in iopipe -- a ring buffer. Basically, you map the same physical pages of memory sequentially. It allows you to simply change the pointer, and never need to copy anything. See this code for an example (I only have it for Posix, but Windows has similar features, I have to add them): https://github.com/schveiguy/iopipe/blob/6a8c10d2858f92978d72c55eecc7ad55fcc207e2/source/iopipe/buffer.d#L306 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. Even if you could do this, this doesn't help because at the end of the pool, you need to reallocate into a another pool (or back to the beginning of the pool), because there can be no free pages after the last page in the pool (you can't merge pools together). > 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). You can get this via `GC.query`, but that means 2 calls into the GC. 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. So 2 things here: 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. 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
Re: In-place extension of arrays only for certain alignment?
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]; // AA.. ...M > arr = arr[1 .. $]; // xAAA AA.. ...M > arr ~= 0; // xAAA AAA. ...M > arr ~= 0; // xAAA ...M > arr = arr[3 .. $]; // ...M > arr ~= cast(ubyte[])[1, 2, 3]; // AAAM // full! > arr ~= 1; // ...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
Re: In-place extension of arrays only for certain alignment?
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]; // AA.. ...M
arr = arr[1 .. $]; // xAAA AA.. ...M
arr ~= 0; // xAAA AAA. ...M
arr ~= 0; // xAAA ...M
arr = arr[3 .. $]; // ...M
arr ~= cast(ubyte[])[1, 2, 3]; // AAAM // full!
arr ~= 1; // ...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
Re: In-place extension of arrays only for certain alignment?
On Tuesday, 16 August 2022 at 18:11:54 UTC, Ali Çehreli wrote:
```d
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..$];
}
}
```
First I tried it on an older version (2.0.87). And with
version(good) I got interesting results:
```d
(length == 1, capacity: 2031 -> 6127)
i = 4079, 8175
(length == 2, capacity: 1015 -> 3063)
i = 2039, 4087, 6135, 8183
(length == 3, null)
i > 10.000 = ?
(length == 4, capacity: 507 -> 1531)
i = 1019, 2043, 3067, 4091, 5115, 6139, 7163, 8187, 9211
(length == 5, 6, 7..., null)
i > 10.000 = ?
```
For some reason the capacity changed frequently when data.length
== 4 . And I didn't see a result in 3, 5, 6, 7 since I tested
less than 10k loops. I got more interesting results with the
extra version:
```d
version(extra) arr.length++; /*
2087
291 elements, capacity: 582 -> 1167, ptr: 7F1306346010
1169 elements, capacity: 2338 -> 4093, ptr: 7F1306346010
2339 elements, capacity: 4678 -> 8189, ptr: 7F1306346010
4387 elements, capacity: 8774 -> 14626, ptr: 7F1306346010
7313 elements, capacity: 14626 -> 23403, ptr: 7F1306346010
Process finished.
*/
```
version(neither) is concurrent with i:
```d
(length == 1, capacity: i)
i = 4079, 8175..16367
(length == 2)
i = 2039, 4087, 8183..14327
(length == 3, capacity: i)
i = 1359, 2725, 5455, 9551..16378
(length == 4, capacity: i)
i = 1019, 2043, 4091, 7163..12283
(length == 5, capacity: i)
i = 815, 1635, 3273, 5731, 9827..16380
```
SDB@79
Re: In-place extension of arrays only for certain alignment?
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
Re: In-place extension of arrays only for certain alignment?
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? 2. Is there a free page after it? The smaller blocks are stored in page-sized pools and *cannot* be combined together. e.g. you can't have 2 16-byte blocks joined to form a 32 byte block. The reason why your `bad` version fails is because when it must reallocate, it still is only allocating 1 element. Now a page is 4096 bytes typically. So why does the 2048 amount work? Because in order to store a 2048 byte array, you need 2048 bytes AND the metadata (e.g. typeinfo for destruction and append capacity). This requires a full page. 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. -Steve
