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
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
| -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
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
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.
snip
| 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 T, class Container = general_cyclic_bufferT
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
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.
snip
| 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 T, class Container = general_cyclic_bufferT
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
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
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
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
