Re: [boost] cyclic buffer

From: Jan Gaspar (jga_at_[hidden])
Date: 2002-10-11 02:18:37

Hi Thomas!

Thank you very much for your effort. Your review is very helpful to me.

Thomas Wenisch wrote:

> (cc'd to boost mailing list)
>
> Hi Jan,
>
> Sorry for the delay in getting back to you on your circular buffer.
> Thanks for sending me the code!  (For anyone else interested, I beleive
> the code is in the files area on Yahoo - Jan, correct me if I am wrong).
>

Yes, the code is on Yahoo.

>
> First, some general comments:
>
> 1)
>     For me, the essential feature I require of a cyclic buffer is that
> insertion/removal at the head or the tail DOES NOT invalidate iterators
> that point into the middle.  In your documentation, I see that this is not
> guaranteed, and I assume this follows from the fact that it is not
> guaranteed by the underlying deque.  However, I do think it is very good
> that you documented the invalidation rules clearly in your HOWTO.
>
> 2)  I am a big fan of Doxygen, so I like your documentation ;)
>
> 3)
>     The current behavior of your implementation is that a write that
> "overflows" the buffer removes the tail element.  An alternative
> implementation would throw an exception - adding to a full circular buffer
> is an error.  Both are very useful behaviors, for different use cases, and
> most of the code would be the same.  I think it would be really cool if
> policy parameters could be used to select between the behaviors.  A
> similar choice exists for underflow (ie error or return a
> default-constructed value_type).

Good point!

> 4)
>    Your implementation basically constrains a deque to a specific
> capacity, and thus, provides the interface of a circular buffer.
> However, the performance characteristics are identical to a deque.  The
> main reason I choose to use a circular buffer over a deque is performance:
> I expect that a circular buffer will not perform allocations when it is
> being used.
>   This gives me a number of things: first, the push_front(), and
> push_back() methods could truly be constant time operations, rather than
> amortized constant time (ie you pay the allocation penalty at
> construction, but never again).  Second, I am guaranteed that allocations
> won't fail.
>   With a deque-backed implementation as you have implemented, the
> "circular buffer" is really marching forward in memory - when you allocate
> an element, you attach it at the end of the deque, which means after all
> previously allocated elements, and could mean that the deque has been
> relocated to a different address.  Then, you remove the head.
>
>    What I would really like to see is an implementation that is backed by
> a vector, with head and tail pointers used to know where the top and
> bottom of the buffer are.  In such a design, the hard part is writing a
> random-access iterator - the vector iterator will do the wrong
> thing.  With that, you get no invalidation of iterators on push or pops at
> either end (use vector assignment, not vector push/pop); constant time
> pushes and pops; no possibility of allocation failures; and you still have
> constant time random access.
>    But, it takes a lot more code to do it...
>

You are right. First I was considering implement the cyclic buffer as a vector
adaptor, but I was too lazy. I just wanted to create any cyclic buffer. Later
if someone would be interested in I would optimize the implementation.
Probably now is the time to do it.

>
> Comments on the Code:
>
> 1) Overall, it is very good and very readable.
>
> 2) There are several missing typename keywords.  Basically, everytime you
> have Container::xxx, it should read typename Container::xxx
>
> Regards,
> -Tom Wenisch
> Computer Architecture Lab
> Carnegie Mellon University

--
Jan Gaspar | jga_at_[hidden]
Whitestein Technologies | www.whitestein.com
Panenska 28 | SK-81103 Bratislava | Slovak Republic
Tel [phone] | Fax [phone]