On the subject of an XML parser

[Ali Çehreli]

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