[boost] Linear circular buffer

Subject: [boost] Linear circular buffer
From: Soren Holstebroe (holstebroe_at_[hidden])
Date: 2009-06-24 16:35:17

Hi,

The boost library contains a circular buffer template by Jan Gaspar. It
seems well written and STL robust, but I believe the design has some
performance shortcomings in many practical usages.
Every time I have used a circular buffer it has been to drag a window over a
huge or real time dataset. If the dataset is non real-time and small enough
to be contained in memory, there is no practical need for a circular buffer,
since the window data pointer can just be dragged in memory along the full
length of the dataset.
In many algorithms using a dragged window, you would need to process the
full length of the window for each time the window is moved. E.g. convolving
signal data. Thus, you read from the window a lot more than you write.
To maximize performance of your window reading and to utilize external
libraries, you need linear access to the data. While Gaspar's circular
buffer provide a linearize method, it requires a full reorganization of the
contained data. This yields an O(N*M) efficiency, just for dragging the
window (size N) over the data (size M).
For internal use, the circular buffer provides iterators, but each iteration
requires an internal buffer check, in order to wrap around the buffer
border.
Since the nature of a circular buffer in most practical scenarios (at least
that I can think of) is to be involved in the processing of large amount of
data, read performance is important.

If you allow the internal buffer to allocate more memory than the size of
the circular buffer, you can reduce the number of times you need to
reorganize the internal buffer to make it linear readable. If you allocate N
items more than the circular buffer size, you only need to reorganize every
N+1 pushes to the window. Thus, allocating additional 100 items will reduce
the reorganization overhead to 1%.

I have written to Jan Gaspar, who recognizes that the buffer is not
efficient for linear use, but he hasn't got the time anymore to add that
feature.

Is a circular buffer variant with linear access at a low maintenance cost
something that would have public interest?

Soren