On 10/3/22 09:12, tsbockman wrote:
> On Monday, 3 October 2022 at 14:46:13 UTC, Ali Çehreli wrote:
>> CircularBlocks does not move elements. It just allocates and adds a
>> new block to its "array of slices" queue.
>
> Repeatedly appending `~=` to a dynamic array, as `CircularBlocks` does
> [here](https://github.com/acehreli/alid/blob/main/circularblocks/alid/circularblocks.d#L422), will reallocate and move the elements over to the new memory whenever the new `.length` would exceed `.capacity`:
> ```D
>      void addExistingBlock_(ubyte[] buffer)
>      {
>          import std.array : back;
>
>          blocks ~= ReusableBlock!T(buffer);
>          capacity_ += blocks.back.capacity;
>      }
> ```

Yes but blocks_ does not carry elements but blocks to place elements on.

CircularBlocks uses a circular buffer of blocks of elements. As elements are popped from the head, blocks that become empty are moved to the end of blocks_ array to be reused. (Here, we have O(M); if M (number of blocks) is small compared to N (number of live elements as in a sliding window), then we have just a few blocks to shuffle with std.algorithm.bringToFront.)

addExistingBlock_() is called only when existing blocks are all in use.

The typical use case is a sliding window of cached elements. Empty blocks at the frot are moved to the end and they get reused for new elements later.

If the window width is constant, there will either be no memory allocation (if the user provided initial buffers), or some during the preamble as the number of buffers stabilize. There may be occasional new block allocations if the window enlarges depending on the application, but this high water mark helps reduce block allocations in the future.

I appreciate your looking into this and I would be very happy to know about all performance issues. If my analysis is wrong above, please give me data for me to work with. :)

Ali