Re: [boost] Linear circular buffer

Subject: Re: [boost] Linear circular buffer
From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2009-06-24 22:37:09

Hi Soren,

On Thu, Jun 25, 2009 at 4:35 AM, Soren Holstebroe<holstebroe_at_[hidden]> wrote:
>
> 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.

I use it just fine in my high performance applications where I
maintain the most recent N timings from API calls. Although iteration
through the dataset may be a little painful, N is not large enough for
me to notice (100 and 1000) the pain. The calls run in sub-microsecond
time and the maintenance of automatically evicting older entries gives
me (the user) a good guarantee that the data I'm getting is
consistent.

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

That makes two of us. :)

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

I agree about read performance, but I don't think you ever need to
call 'linearize' if you don't intend to build a vector out of your
circular buffer. Iterating through the container is O(N) where N is
the size of the container, and the check for borders is O(1); I can
imagine that you can use the modulo (%) function given that you know
the initial offset of the "first" entry in the buffer, and N being the
size of the buffer -- this doesn't require a check for borders then
because any increment will always be trimmed and offset to within the
buffer.

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

How about space efficiency then? I (the user) expect to have just 100
elements' worth of memory used when I allocate 100 elements' worth of
a circular buffer at construction time (same goes for the STL vector).

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

Linear access time is nice especially if you intend to always just go
through the whole data structure everytime -- having said this I don't
think I'd necessarily want to pay for extra space usage if I can
absolutely avoid it.

How do you intend to implement the internal buffer then without having
to use more memory than necessary to store the elements?

-- 
Dean Michael Berris | Software Engineer, Friendster, Inc.
blog.cplusplus-soup.com | twitter.com/mikhailberis |
linkedin.com/in/mikhailberis | profiles.friendster.com/mikhailberis |
deanberris.com