Re: [boost] Re: Review Request: cyclic_buffer
On Thursday, June 12, 2003, at 12:43 PM, Nigel Stewart wrote: I can see the appeal here in using a circular buffer in this manner, while at the same time I'm cooling against the compromise of "insert auto-resizes, while push doesn't" which seems inconsistant. Given that we both seem to have a real-time orientation, we're probably not so far apart in our thinking. Perhaps we simply need to make a distinction between a circular_buffer and a circular_deque which are only different in terms of resizing semantics. Each provides different characteristics, and stand independently as boost containers. Code re-use by itself doesn't seem to be a good enough reason to mix the concepts and overload the namespace unnecessarily. I'm beginning to think you're correct. An informed process would be to create both containers, and adapt both types to the other, and measure the results. I'm afraid I'm asking somebody else to do work here though. I've got a resizing circular buffer (Metrowerks::cdeque has shipped with CodeWarrior for years), but I'm not at liberty to share the source. And my schedule is tight enough that even higher priority things are slipping right now, so I can't donate cycles to a non-resizing variant to compare to. One idea that came to my mind was to have "forward insertion", "backward insertion" to resolve the question of semantics of arbitrary insertion into a circular_buffer. insert() pushes rightmost items forwards, overwriting leftmost items as necessary. rinsert() pushes leftmost items backwards, overwriting rightmost items as necessary. Likewise for the circular_deque which would reallocate as necessary to accomodate any kind of insertion - items would never be implicitly lost by a circular_deque. This sounds very interesting for the non-resizing version. I think for the resizing version, the insert should simply minimize the elements that it is going to move. Either way, all pointers and iterators must be considered invalidated (unlike the non-resizing variant with insert and rinsert). In my mind, when you insert into the middle of a resizing circular buffer, the behavior (mental model) is very deque-like, except of course for the ability to predict whether it will require a reallocation or not. -Howard ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
On Wednesday, June 11, 2003, at 05:55 PM, Dave Gomboc wrote: Why is a deque inadequate? deque is more expensive than a resizing circular buffer in both performance and code size. One also can not control *when* deque will allocate as one can with a resizing circular buffer. In a nutshell, a resizing circular buffer is often a better deque than std::deque is. ;-( A resizing circular buffer is absolutely awesome when plugged into std::queue. If your queue on average doesn't constantly grow, a resizing circular buffer is efficient, predictable and safe. A std::deque in std::queue will likely continually rellocate buffers as it drops one off one end and adds one to the other (and at annoyingly unpredictable times if you're doing real-time). -Howard ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
RE: [boost] Re: Review Request: cyclic_buffer
| -Original Message- | From: [EMAIL PROTECTED] | [mailto:[EMAIL PROTECTED] Behalf Of Nigel Stewart | Sent: Wednesday, June 11, 2003 2:03 AM | To: [EMAIL PROTECTED] | Subject: [boost] Re: Review Request: cyclic_buffer | | The "generally accepted" concept of a circular buffer | is a fixed size contiguous memory buffer. Following | the principle of "least surprise" a circular_buffer | should not decide to resize itself. On the "Keep It Simple Sir" principle, I agree with this. Indeed, I think that most uses specifically require a fixed at construction size, and I suspect the code will be smaller, faster and correcter if this is the specification. Paul Paul A Bristow, Prizet Farmhouse, Kendal, Cumbria, LA8 8AB UK +44 1539 561830 Mobile +44 7714 33 02 04 Mobile mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED] ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
Hi all Cyclics! I want to summarize what we have till now. What should be changed in the proposed cyclic_buffer. - Rename to circular_buffer. - Add push_front() and pop_front(). - resize() to behave similarly to vector::resize(). - change_capacity() becomes again change_capacity(). I think the name change_capacity best reflects what the method really does. The vector::reserve() can only increase the capacity, never decrease - which may be confusing. And at last the circular_buffer is not vector so it can have different methods from vector. - insert() will always increase the size and possibly can increase the capacity (if not sufficient). Regards, Jan ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
On Tuesday, June 10, 2003, at 11:33 AM, Nigel Stewart wrote: Constant time push/pop_front, constant time push/pop_back. When begin and end collide, reallocation automatically happens vector-like. Another point to consider: Constant time push/pop can not be combined with std::vector automatic re-allocation due to the linear cost of copying into the realloc'd buffer. Given that circular buffers are often used in the context of real-time applications, it seems to be consistant that push/pop from each end should be truely constant time, and as a consequence the the capacity is never implicitly changed unless explicitly requested via reserve() or resize(). Clearly there is a need for what you are describing. And clearly there is a need for what I am describing. And clearly there are a few more closely related needs. My opinion is that it is much easier to adapt a reallocating circular buffer to a non-reallocating one than vice-versa. It is non-trivial to get a reallocating circular buffer correct with respect to exception safety, iterator/pointer invalidation, possible optimizations for types with trivial assign and copy, etc. I would rather get the detailed, complicated work encapsulated in the container, and then have relatively simple adaptors a-la std::stack and std::queue. An adapted construct-time-fixed-capacity circular buffer is no more inefficient or dangerous than a "native container" version. And the adaptor is simple to write. And because the adaptor is simple to write, there can be a different adaptor for every different need. insert doesn't make sense? Hide it. It will never even be instantiated. Don't want to reallocate? Override push_back to check for size()==capacity() and then perform your favorite action (overwrite front, throw an exception, burn the toast, whatever). Can only afford a reallocation if not at interrupt time? Not a problem. etc. -Howard ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
On Tuesday, June 10, 2003, at 10:48 AM, Jan Gaspar wrote: insert in general should have the basic exception safety guarantee. But when inserting only one element at either end, the strong guarantee is in place. I think the strong guarantee can reached only in case the cyclic_buffer is not full (if there is no reallocation). You can do it with push_back/front too regardless. vector::push_back has the strong guarantee. If you're using copy semantics (which I would expect instead of move semantics), you basically have to build a whole new vector in a temp (with the push_back), and then swap it in when everything is set (just describing the realloc branch here). If you're looking ahead to use move semantics to perform this operation, it is a little more tricky, but not too much. In fact it is easier with cyclic_buffer than it is with vector! :-) You have to push_back the new element into the temporary first. If it throws, the temporary cleans up the new buffer. If it doesn't, *then* move the old data over (move must be nothrow). -Howard ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
Hi Howard! Howard Hinnant wrote: > For the general container I propose that insert reallocates if size() > would exceed capacity (invalidating all iterators, pointers and > references). And if size() does not exceed capacity, all iterators, > pointers and references are still invalidated, unless the insert > happens at one end or the other, in which case no pointers or > references are invalidated (iterators still are invalidated). I would > expect a quality implementation to minimize the number of elements that > need to be shifted. This is an interesting idea! > > insert in general should have the basic exception safety guarantee. > But when inserting only one element at either end, the strong guarantee > is in place. I think the strong guarantee can reached only in case the cyclic_buffer is not full (if there is no reallocation). > Also if the value_type's copy constructor and assignment > operator do not throw, then the strong guarantee is in place. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
For the general container I propose that insert reallocates if size() would exceed capacity (invalidating all iterators, pointers and references). And if size() does not exceed capacity, all iterators, pointers and references are still invalidated, unless the insert happens at one end or the other, in which case no pointers or references are invalidated (iterators still are invalidated). I would expect a quality implementation to minimize the number of elements that need to be shifted. insert in general should have the basic exception safety guarantee. But when inserting only one element at either end, the strong guarantee is in place. Also if the value_type's copy constructor and assignment operator do not throw, then the strong guarantee is in place. For any given adaptor, I think you could restrict or eliminate insert as appropriate for that model. -Howard On Tuesday, June 10, 2003, at 05:20 AM, Jan Gaspar wrote: Hi Howard! I like your idea. But (referring to the Nigel Stewart's posting) what would you propose for the insert? Should I not provide it? Jan Howard Hinnant wrote: In article <[EMAIL PROTECTED]>, Alisdair Meredith <[EMAIL PROTECTED]> wrote: | "The one true circular buffer template" is a nigh impossible goal, | because it means so many things to different people. | I would certainly like the documentation to explain the tradeoffs made | in the implementation, and why this particular variation was chosen as | most appropriate for the general case. Indeed! Excellent post! Perhaps container adaptors could be applied to a sufficiently generalized circular buffer. What is the one true queue? There isn't one. It is best a container adaptor (policy based if you prefer). I suspect that a more general circular buffer, restricted by various adaptors, might serve more uses with less code. The circular buffer I've needed (and coded) fits none of aforementioned descriptions. But it is a circular buffer nonetheless. For my money, the general circular buffer is one that exists in a contiguous array, but with an arbitrary begin and end within that array, capable of wrapping around the end of the physical memory: +---+---+---+---+---+---+---+---+---+---+ | 4 | 5 | | | | | 0 | 1 | 2 | 3 | +---+---+---+---+---+---+---+---+---+---+ ^ ^ | | endbegin Constant time push/pop_front, constant time push/pop_back. When begin and end collide, reallocation automatically happens vector-like. This data structure can be efficiently coded with a 4-word data structure. For example: data_ptr, capacity, size, begin_ptr (there are other variations that also only take 4 words). From this you can write adaptors to constrain capacity, have push_back overwrite front(), throw an exception on size() exceeding capacity(), or whatever else you need to do. You can't adapt any other std::container to do this job because vector is the only one with capacity, but vector doesn't have a constant time push/pop_front. But I believe you can adapt the above described container to meet the needs of other "circular buffer" requirements. For example: template > class my_cyclic_buffer { public: // typedefs ... my_cyclic_buffer(size_type cap) {c.reserve(cap);} reference operator[](size_type n) {return c[n];} // etc. void push_back(const value_type& x) { if (capacity() != 0) { if (c.size() == c.capacity()) c.pop_front(); c.push_back(x); } } change_capacity(size_type new_cap) { if (new_cap > c.capacity()) c.reserve(new_cap); else if (new_cap < c.capacity()) { c.erase(c.begin(), c.begin() + c.size() - new_cap); Container tmp(c); // assumes tmp.capacity() == c.size() c.swap(tmp); } } // etc. private: Container c; }; -- Howard Hinnant Metrowerks ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost -- Jan Gaspar | [EMAIL PROTECTED] Whitestein Technologies | www.whitestein.com Panenska 28 | SK-81103 Bratislava | Slovak Republic Tel +421(2)5930-0734 | Fax +421(2)5443-5512 ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
Hi Howard! I like your idea. But (referring to the Nigel Stewart's posting) what would you propose for the insert? Should I not provide it? Jan Howard Hinnant wrote: > In article <[EMAIL PROTECTED]>, Alisdair Meredith > <[EMAIL PROTECTED]> wrote: > > | "The one true circular buffer template" is a nigh impossible goal, > | because it means so many things to different people. > > | I would certainly like the documentation to explain the tradeoffs made > | in the implementation, and why this particular variation was chosen as > | most appropriate for the general case. > > Indeed! Excellent post! > > Perhaps container adaptors could be applied to a sufficiently > generalized circular buffer. > > What is the one true queue? There isn't one. It is best a container > adaptor (policy based if you prefer). I suspect that a more general > circular buffer, restricted by various adaptors, might serve more uses > with less code. > > The circular buffer I've needed (and coded) fits none of aforementioned > descriptions. But it is a circular buffer nonetheless. > > For my money, the general circular buffer is one that exists in a > contiguous array, but with an arbitrary begin and end within that > array, capable of wrapping around the end of the physical memory: > > +---+---+---+---+---+---+---+---+---+---+ > | 4 | 5 | | | | | 0 | 1 | 2 | 3 | > +---+---+---+---+---+---+---+---+---+---+ > ^ ^ > | | > endbegin > > Constant time push/pop_front, constant time push/pop_back. When begin > and end collide, reallocation automatically happens vector-like. > > This data structure can be efficiently coded with a 4-word data > structure. For example: data_ptr, capacity, size, begin_ptr (there > are other variations that also only take 4 words). > > >From this you can write adaptors to constrain capacity, have push_back > overwrite front(), throw an exception on size() exceeding capacity(), > or whatever else you need to do. > > You can't adapt any other std::container to do this job because vector > is the only one with capacity, but vector doesn't have a constant time > push/pop_front. But I believe you can adapt the above described > container to meet the needs of other "circular buffer" requirements. > For example: > > template > > class my_cyclic_buffer > { > public: >// typedefs ... > >my_cyclic_buffer(size_type cap) {c.reserve(cap);} > >reference operator[](size_type n) {return c[n];} >// etc. > >void push_back(const value_type& x) >{ > if (capacity() != 0) > { > if (c.size() == c.capacity()) > c.pop_front(); > c.push_back(x); > } >} > >change_capacity(size_type new_cap) >{ > if (new_cap > c.capacity()) > c.reserve(new_cap); > else if (new_cap < c.capacity()) > { > c.erase(c.begin(), c.begin() + c.size() - new_cap); > Container tmp(c); // assumes tmp.capacity() == c.size() > c.swap(tmp); > } >} >// etc. > > private: >Container c; > }; > > -- > Howard Hinnant > Metrowerks > > ___ > Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost -- Jan Gaspar | [EMAIL PROTECTED] Whitestein Technologies | www.whitestein.com Panenska 28 | SK-81103 Bratislava | Slovak Republic Tel +421(2)5930-0734 | Fax +421(2)5443-5512 ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
Ok, ok, but what with insert? What element should be removed: the first or the last one? And why the first approach or the latter. Jan Nigel Stewart wrote: > >> So the issue here seems to be whether a cyclic_buffer > >> should be circular-list-like or FIFO-like. > > > > I designed the cyclic_buffer mainly for adding the elements at the end of the > > container and automatic removal of elements from the beginning - it is just plain > > FIFO, nothing else. > > (Please excuse the tone here if it sounds too officious, > just intending to be precise...) > > Therefore, here is the case for extending the proposed > cyclic_buffer: > > - Rename to circular_buffer > > Relate the container more closely to the concept of > a circular list. The proposed cyclic_buffer appears > to support a subset of circular_buffer interface > and functionality. > > - Add push_front() and pop_front() > > For the purpose of generality, allow manipulation of > the container at both ends of the buffer, rather than > pushing to the back and popping from the front. > > front() is already included in the interface. > > This would allow use as a LIFO (last-in, last-out) > with fixed sized "event horizon". (As an example.) > > - resize() to behave similarly to vector::resize() > > Inserts or erases elements at the end such that > the size becomes n. (Applications not concerned > with underlying capacity management need not > explicitly reserve capacity for a particular > desired size: principle of "minimal surprise".) > > Semantics of reducing the size of a circular_buffer: > follow std::vector and keep only first n items. > > - change_capacity() becomes reserve() > > For consistency with std::vector. > > Otherwise, should cyclic_buffer be named cyclic_fifo ? > > Cheers, and thanks for being open to input and review... > > Nigel Stewart > > ___ > Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost -- Jan Gaspar | [EMAIL PROTECTED] Whitestein Technologies | www.whitestein.com Panenska 28 | SK-81103 Bratislava | Slovak Republic Tel +421(2)5930-0734 | Fax +421(2)5443-5512 ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
Hi Nigel, Nigel Stewart wrote: > > So the issue here seems to be whether a cyclic_buffer > should be circular-list-like or FIFO-like. Given > that there is already a queue container adapter, > perhaps it's worth listing some applications > of cyclic_buffer that depend on either > circular-list-like or FIFO-like semantics. I designed the cyclic_buffer mainly for adding the elements at the end of the container and automatic removal of elements from the beginning - it is just plain FIFO, nothing else. I don't want to add elements at the beginning. I think it will be less confusing - just keep it rather simple. > > > Could a queue adaptor using a cyclic_buffer instead > of a deque provide the explicitly FIFO-like mode of > operation? (While leaving cyclic_buffer to be > circular-list-like?) Queue cannot use the cyclic_buffer because the queue's size is not restricted. Probably I don't understand this question. > > > >> Semantics of resize should probably follow vector: > >> 1. The capacity is implicitly adjusted to fit the > >> requested size. > > http://www.sgi.com/tech/stl/Vector.html > > vector::resize > > Inserts or erases elements at the end such that > the size becomes n. > > (I think a developer may find it surprising for a > cyclic_buffer::resize to be clamped to the capacity.) > OK, you're right. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
Hi Nigel! Quoting Nigel Stewart <[EMAIL PROTECTED]>: > Jan, > > I'm looking forward to the opportunity of having a close look > at your cyclic_buffer. But for now, a few perhaps shallow > comments... > > 1.How about push_front()? (in std::list style) > And pop_front()? > For the sake of generality. > Imagine you have a cyclic buffer which is full. When you add (push_back or insert) a new item into this buffer the first (oldest) item will be removed. I want to emphasize the "oldest". So if you want to push_front an item you want to add the oldest one. But as soon as you add it the item will be removed because it is the oltest item in the buffer. The buffer's content won't change. (The same is valid for inserting at the beginning of the cyclic buffer.) This is the reason why I didn't encompassed push_front in the implementation. If there is no push_front then it is not logical to have pop_front. You can use erase(begin) instead. > The vague concept I have in mind is some kind > of sliding window algorithm that could be moving > either left or right, using a circular buffer as > a cache. (Currently pondering a 2D version of a > circular buffer, anyone come across such a beast?) > > 2.How about reserve(..) and resize(..)? > Shouldn't change_capacity be called reserve, like vector? If you look more closely at the documentation you will find out that change_capacity is different from reserve. The capacity can be also decreased; by reserve not. > Shouldn't max_size be called capacity, like vector? > max_size in the vector is the largest possible size, not the reserved capacity. > One context I which I've made happy use of a circular > buffer is for storing history in the form of a 3D > trail for moving particles. It's handy to allow the > GUI to adjust the size of trails dynamically. > > Semantics of resize should probably follow vector: > 1. The capacity is implicitly adjusted to fit the > requested size. (Optional to explicitly manage > capacity in addition to size) > 2. Items are lost from the end if the container is > to be shrunk. Are you sure you want to lost the items at the end ? Not at the beginning (the oldest) ? BTW if you change_capacity in order to shrunk the container the oldest items will be removed. > > (Oops, just noticed that resize is in one part of >the documentation, but not the non-doxygen page). Thank you for this! > > For your reference, my somewhat more modest circular buffer: > http://www.nigels.com/glt/doc/classcbuffer.html > > I am new to boost, but liking it very, very much... > > Cheers, > > Nigel Stewart > > > The cyclic buffer implementation and documentation (cyclic_buffer.zip) can > be > > found at: > > http://groups.yahoo.com/group/boost/files/ > > > ___ > Unsubscribe & other changes: > http://lists.boost.org/mailman/listinfo.cgi/boost > > ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost