[circular_buffer] some comments and suggestions
Hi Jan, #1 I was browsing through the docs in trunk. First I noticed that the default constructor has the follwoing postcondition: capacity() == max_size() && size() == 0 I find that somewhat unfortunate that it allocates a huge amount of memory. It seems to me that it is too easy to do that by coincidence. The usual rule for std containers is to never allocate by default and anticipate a call to reserve() or the first element. It also seems to me that this will create problems when the container is used in containers that might use default construction. #2 I think it would be useful to add a predicate called is_linearized(), so one can check if this property holds. Also, if this do hold, I should be able the get fast iterators to this linear segment, perhaps by calling .base() on the iterators which then simply return a pointer (I know I can get the pointers by array_one(), but I would more often need the iterators). #3 I think it would be useful to add rotate() as a member function. AFAICT, it can in many times (if not all) be much faster than std::rotate() because it can simply move a few elements and then simply adjust the iterators. -Thorsten
Hi! I agree with most of the comments from Thorsten. I do however disagree with point 1. The allocation in the constructor allows zero allocation in the subsequent push calls. Often a circular_buffer is used in tight loops of push operations. I would not want the additional overhead of the allocation check. With types with no-throw guarantee copy constructors I also would not want the additional possibility of an exception thrown from the push operation. I would not use this class if the push operation had this additional overhead. Neil Groves On Jan 21, 2008 10:40 AM, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Hi Jan,
#1 I was browsing through the docs in trunk. First I noticed that the default constructor has the follwoing postcondition:
capacity() == max_size() && size() == 0
I find that somewhat unfortunate that it allocates a huge amount of memory. It seems to me that it is too easy to do that by coincidence. The usual rule for std containers is to never allocate by default and anticipate a call to reserve() or the first element. It also seems to me that this will create problems when the container is used in containers that might use default construction.
#2 I think it would be useful to add a predicate called is_linearized(), so one can check if this property holds. Also, if this do hold, I should be able the get fast iterators to this linear segment, perhaps by calling .base() on the iterators which then simply return a pointer (I know I can get the pointers by array_one(), but I would more often need the iterators).
#3 I think it would be useful to add rotate() as a member function. AFAICT, it can in many times (if not all) be much faster than std::rotate() because it can simply move a few elements and then simply adjust the iterators.
-Thorsten _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Neil Groves skrev:
Hi!
I agree with most of the comments from Thorsten. I do however disagree with point 1. The allocation in the constructor allows zero allocation in the subsequent push calls. Often a circular_buffer is used in tight loops of push operations. I would not want the additional overhead of the allocation check. With types with no-throw guarantee copy constructors I also would not want the additional possibility of an exception thrown from the push operation. I would not use this class if the push operation had this additional overhead.
I don't see how you get into the troubles you mention. I don't want push_back() to regrow, but neither does it have to: simply can reserve() prior to use. Otherwise you get whetever push_back() does on an empty buffer (either we say as a precondition that it is not empty, or we allow it to do nothing at all). -Thorsten
On Jan 21, 2008 10:40 AM, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Hi Jan,
#1 I was browsing through the docs in trunk. First I noticed that the default constructor has the follwoing postcondition:
capacity() == max_size() && size() == 0
I find that somewhat unfortunate that it allocates a huge amount of memory. It seems to me that it is too easy to do that by coincidence. The usual rule for std containers is to never allocate by default and anticipate a call to reserve() or the first element. It also seems to me that this will create problems when the container is used in containers that might use default construction.
I am happy that you are not suggesting allocation in the push operation. I think that requiring a call to reserve() is surprising behaviour since one would have to call reserve() for the container to work. This is inconsistent with the standard containers in a different manner. I have always wanted my circular_buffer uses to be allocated at full size. Perhaps the default behaviour could remain the same but an additional constructor could be provided to avoid allocation during construction? Neil Groves On Jan 21, 2008 11:58 AM, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Neil Groves skrev:
Hi!
I agree with most of the comments from Thorsten. I do however disagree with point 1. The allocation in the constructor allows zero allocation in the subsequent push calls. Often a circular_buffer is used in tight loops of push operations. I would not want the additional overhead of the allocation check. With types with no-throw guarantee copy constructors I also would not want the additional possibility of an exception thrown from the push operation. I would not use this class if the push operation had this additional overhead.
I don't see how you get into the troubles you mention. I don't want push_back() to regrow, but neither does it have to: simply can reserve() prior to use. Otherwise you get whetever push_back() does on an empty buffer (either we say as a precondition that it is not empty, or we allow it to do nothing at all).
-Thorsten
On Jan 21, 2008 10:40 AM, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Hi Jan,
#1 I was browsing through the docs in trunk. First I noticed that the default constructor has the follwoing postcondition:
capacity() == max_size() && size() == 0
I find that somewhat unfortunate that it allocates a huge amount of memory. It seems to me that it is too easy to do that by coincidence. The usual rule for std containers is to never allocate by default and anticipate a call to reserve() or the first element. It also seems to me that this will create problems when the container is used in containers that might use default construction.
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Neil Groves skrev:
I am happy that you are not suggesting allocation in the push operation.
I think that requiring a call to reserve() is surprising behaviour since one would have to call reserve() for the container to work. This is inconsistent with the standard containers in a different manner. I have always wanted my circular_buffer uses to be allocated at full size.
But isn't that 2^32 objects (i.e. *huge*)? (Or am I misunderstanding something?)
Perhaps the default behaviour could remain the same but an additional constructor could be provided to avoid allocation during construction?
Hm. I don't know. There is a lot of existing code that relies on cheap default construction, e.g.: std::map<int,circular_buffer<T>> map; map[ 1 ] = circular_buffer<T>(...); -Thorsten
You are correct. The default capacity would be better as 0. I had misunderstood the default capacity arrangement. Neil Groves On Jan 21, 2008 1:32 PM, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
Neil Groves skrev:
I am happy that you are not suggesting allocation in the push operation.
I think that requiring a call to reserve() is surprising behaviour since one would have to call reserve() for the container to work. This is inconsistent with the standard containers in a different manner. I have always wanted my circular_buffer uses to be allocated at full size.
But isn't that 2^32 objects (i.e. *huge*)? (Or am I misunderstanding something?)
Perhaps the default behaviour could remain the same but an additional constructor could be provided to avoid allocation during construction?
Hm. I don't know. There is a lot of existing code that relies on cheap default construction, e.g.:
std::map<int,circular_buffer<T>> map; map[ 1 ] = circular_buffer<T>(...);
-Thorsten _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Mon, Jan 21, 2008 at 02:13:59PM +0000, Neil Groves wrote:
You are correct.
Who is correct? The whole day I always have to guess what you write! Please follow a proper quoting style, read the mailinglist policy again (http://www.boost.org/more/discussion_policy.htm) and avoid top posting! Jens
Thorsten Ottosen skrev:
Hi Jan,
#3 I think it would be useful to add rotate() as a member function. AFAICT, it can in many times (if not all) be much faster than std::rotate() because it can simply move a few elements and then simply adjust the iterators.
Also, it seems like adding reverse() with O(1) complexity would be useful too. -Thorsten
Thorsten Ottosen skrev:
Thorsten Ottosen skrev:
Hi Jan,
#3 I think it would be useful to add rotate() as a member function. AFAICT, it can in many times (if not all) be much faster than std::rotate() because it can simply move a few elements and then simply adjust the iterators.
Also, it seems like adding reverse() with O(1) complexity would be useful too.
Furthermore, I suggest void push_back(const_reference item = value_type()); void push_front(const_reference item = value_type()); be implemented (not specified) as 4 functions: 2 of them without any aguments, but with an inplace construction of the objects. This would be important for heavy objects. -Thorsten
participants (3)
-
Jens Seidel -
Neil Groves -
Thorsten Ottosen