The review of Jan Gaspar's Circular Buffer library starts today (March 5th) and runs for 10 days. Latest version of the library is available at: http://groups.yahoo.com/group/boost/files/circular_buffer_v3.6.zip What it is: Circular buffer (also known as ring or cyclic buffer) is container with fixed upper limit on number of elements inside. When capacity gets exhausted newly inserted elements will cause oldest elements to get dropped out. What makes the library Boost candidate: - it provides often used functionality, - it is STL compliant generic solution, - it is designed for CPU/memory efficiency, - it is fully documented and tested, - it contains extensive debug support, - it has been informally reviewed for long time. Discovered problems in code or in documentation, missing features, portability issues and finally opinion whether the library belongs to Boost is welcomed. /Pavel
The review of Jan Gaspar's Circular Buffer library starts today (March 5th) and runs for 10 days.
Here's result of first look into 3.6. More details will follow later. /Pavel ________________________________________________ 1. docs: the table "Friend Functions" should be rather "Standalone Functions" and should mention swap, <=, >= as well. ________________________________________________ 2. base.hpp: standalone function bool operator > (...) should be added. ________________________________________________ 3. docs: why is the (SGI) in paragraph "Model of" and why it is twice there? ________________________________________________ 4. docs: "Type Requirements": doesn't the T need to be DefaultConstructible as well, e.g. to support push_back(void)? Maybe the title should be "Element Type Requirements". ________________________________________________ 5. compiling test on BCB 6.4, adaptor.hpp: in snippet: #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) reference operator [] (size_type n) { return circular_buffer<T, Alloc>::operator[](n); } return_value_type operator [] (size_type n) const { return circular_buffer<T, Alloc>::operator[](n); } <<<=== here #else using circular_buffer<T, Alloc>::operator[]; #endif the line starting with "return_value_type" fails to compile with error: ------------ [C++ Error] adaptor.hpp(67): E2303 Type name expected Full parser context base_test.cpp(9): #include C:\Temp\temp\circular_buffer3.6\circular_buffer\libs\circular_buffer\test\te st.hpp test.hpp(16): #include C:\Temp\temp\circular_buffer3.6\circular_buffer\libs\circular_buffer\test\.. /../../boost/circular_buffer.hpp circular_buffer.hpp(54): #include C:\Temp\temp\circular_buffer3.6\circular_buffer\libs\circular_buffer\test\.. /../../boost/circular_buffer/adaptor.hpp adaptor.hpp(16): namespace boost adaptor.hpp(32): class circular_buffer_space_optimized<T,Alloc> [C++ Error] adaptor.hpp(67): E2139 Declaration missing ; Full parser context base_test.cpp(9): #include C:\Temp\temp\circular_buffer3.6\circular_buffer\libs\circular_buffer\test\te st.hpp test.hpp(16): #include C:\Temp\temp\circular_buffer3.6\circular_buffer\libs\circular_buffer\test\.. /../../boost/circular_buffer.hpp circular_buffer.hpp(54): #include C:\Temp\temp\circular_buffer3.6\circular_buffer\libs\circular_buffer\test\.. /../../boost/circular_buffer/adaptor.hpp adaptor.hpp(16): namespace boost adaptor.hpp(32): class circular_buffer_space_optimized<T,Alloc> ------------ When I change return type to "value_type" all compiles OK. This could be some BCB quirk. ________________________________________________ 6. compiling test on Intel C++ 7.0: all is OK. ________________________________________________ 7. compiling base_test.cpp on VC6.5: I am getting "user breakpoint" within Boost.Test. This may be regression of Test, though. I'll try to dig deeper. ________________________________________________ EOF
Hi Pavel!
________________________________________________ 1. docs: the table "Friend Functions" should be rather "Standalone Functions" and should mention swap, <=, >= as well. Agree.
________________________________________________ 2. base.hpp: standalone function bool operator > (...) should be added. It is there!
________________________________________________ 3. docs: why is the (SGI) in paragraph "Model of" and why it is twice there? The (SGI) is there because it is different from the standard. See http://boost.org/libs/concept_check/reference.htm for
template <class T, class Alloc> inline bool operator >(const circular_buffer<T,Alloc>& lhs, const circular_buffer<T, Alloc>& rhs) { return rhs < lhs; } details.
________________________________________________ 4. docs: "Type Requirements": doesn't the T need to be DefaultConstructible as well, e.g. to support push_back(void)? Yes, but DefaultConstructible is needed only if you use such a method. In general it is not needed. For example you can just create empty circular_buffer and use push_back(T&). In this case T doesn't have to be DefaultConstructible.
Maybe the title should be "Element Type Requirements". OK.
Jan __________________________________ Do you Yahoo!? Yahoo! Search - Find what you�re looking for faster http://search.yahoo.com
3. docs: why is the (SGI) in paragraph "Model of" and why it is twice there? The (SGI) is there because it is different from the standard. See http://boost.org/libs/concept_check/reference.htm for
"Jan Gaspar" <jano_gaspar@yahoo.com> wrote ________________________________________________ details. Maybe it could be (SGI specific). /Pavel
On Friday, March 5, 2004, at 01:42 AM, Jan Gaspar wrote:
________________________________________________ 4. docs: "Type Requirements": doesn't the T need to be DefaultConstructible as well, e.g. to support push_back(void)? Yes, but DefaultConstructible is needed only if you use such a method. In general it is not needed. For example you can just create empty circular_buffer and use push_back(T&). In this case T doesn't have to be DefaultConstructible.
That means you have to mention this type requirement in the documentation for the push_back() method. Cheers, Jeremy
Jeremy Siek wrote:
On Friday, March 5, 2004, at 01:42 AM, Jan Gaspar wrote:
________________________________________________ 4. docs: "Type Requirements": doesn't the T need to be DefaultConstructible as well, e.g. to support push_back(void)?
Yes, but DefaultConstructible is needed only if you use such a method. In general it is not needed. For example you can just create empty circular_buffer and use push_back(T&). In this case T doesn't have to be DefaultConstructible.
That means you have to mention this type requirement in the documentation for the push_back() method.
Standard containers do not have push_back()/push_front() methods that take no arguments, so I don't agree with the decision of having them. I would remove them entirely. Moreover, I once had a discussion against having both a foobar() and a foobar(T) or foobar(T&) signature. The argument was that explicit instantiation of the entire class requires both methods to be instantiated so it requires T to be DefaultConstructible even if foobar() is never called. That's why the standard defines, for example, std::vector::resize with a default argument, like this: void resize(size_type sz, T c = T()); this definition effectively works around this kind of problem as the default argument expression is not evaluated unless the method is invoked with less than a full set of arguments. Alberto
Hi Jeremy!
That means you have to mention this type requirement in the documentation for the push_back() method.
Yes, I agree. __________________________________ Do you Yahoo!? Yahoo! Search - Find what you�re looking for faster http://search.yahoo.com
Pavel Vozenilek wrote:
Discovered problems in code or in documentation, missing features, portability issues and finally opinion whether the library belongs to Boost is welcomed.
I'm trying to compile the library with GCC 3.4. I get the following errors: ../../../boost/circular_buffer/debug.hpp: In member function `void boost::cb_details::cb_iterator_registry::invalidate_iterators(const Condition&)': ../../../boost/circular_buffer/debug.hpp:60: error: invalid use of undefined type `const struct boost::cb_details::cb_iterator_base' ../../../boost/circular_buffer/debug.hpp:22: error: forward declaration of `const struct boost::cb_details::cb_iterator_base' The type appears to be undefined at the point of use. I know this is within a template function, but the type is non-dependent, so it must be defined before its use. An out-of-class definition at the end of the file seems to suffice. ../../../boost/circular_buffer/base.hpp:139: error: using typedef-name `boost::circular_buffer<T, Alloc>::iterator' after `struct' ../../../boost/circular_buffer/base.hpp:140: error: using typedef-name `boost::circular_buffer<T, Alloc>::const_iterator' after `struct' Verified, and the code really does try to use a typedef-name while declaring friendship, which is invalid. ../../../boost/circular_buffer/adaptor.hpp:369: error: dependent-name `boost::cb_details::cb_iterator_category_traits<InputIterator>::tag' is parsed as a non-type, but instantiation yields a type ../../../boost/circular_buffer/adaptor.hpp:369: note: say `typename boost::cb_details::cb_iterator_category_traits<InputIterator>::tag' if a type is meant Just as it says. The same happens at line 412. Then in base.hpp, lines 570, 827, 953, 1105. After fixing the above, I was able to compile & run adaptor_test and base_test with no errors detected. -- Giovanni Bajo
Hi Jan, This is not my final review, but just some comment and questions. It's based solely on my reading of the docs. 1. your rationale mentions many characteristics that I would expect of std::deque. Do you have any idea how big the performance difference is? 2. You mention "Guarantee of basic exception safety" as a design criteria. I would expect many operations to have a stronger guarantee. 3. you write "In fact the circular_buffer is defined in the file boost/circular_buffer/base.hpp, but it is necessary to ". I don't see why the user should be bothered with this implementation detail. 4. Type Requirements: don't T need to be Assignable too? 5. you could remove one version of push_back and push_front by using default arguments. Similar for insert()/rinsert() 6. What's the use of "return_value_type" ?return_value_type operator[] (size_type index) const Return the element at the index position. Should it not be const_reference? 7. when you state contracts like Precondition: *(this).size() > index don't you mean (*this).size() ? I would prefer that you omitted this entirely. 8. maybe you should add const_pointer data() const ? 9 I assume you provide the basic exception safety for set_capacity(). However, I think you could achieve the strong guarantee by (1) allocating the new buffer and (2) start to copy elements [might throw] (3) swap the two buffers upon completion. The same goes for resize(). Why are they both provided? (If you made resizes 2nd argument to be the bool, then how would they differ?] 10. Can't the exception guarantee for the copy-constructor be stronger too? (and assign(), and push_back(), push_front(), insert() ) 11. Some operations must be nothrow: swap(), size(), capaciity(), pop_back(), pop_front(). Besides that, I think you documentation is excellent. br Thorsten
Hi Thorsten! --- Thorsten Ottosen <nesotto@cs.auc.dk> wrote:
Hi Jan,
This is not my final review, but just some comment and questions. It's based solely on my reading of the docs.
1. your rationale mentions many characteristics that I would expect of std::deque. Do you have any idea how big the performance difference is? The memory is allocated at once, that's the biggest difference.
2. You mention "Guarantee of basic exception safety" as a design criteria. I would expect many operations to have a stronger guarantee.
Of cource, some methods provide stronger guarantee, but in general the container povides just basic exception safety. For some methods (e.g. insert) it is impossible to provide stronger guarantees.
3. you write "In fact the circular_buffer is defined in the file boost/circular_buffer/base.hpp, but it is necessary to ". I don't see why the user should be bothered with this implementation detail.
You're right.
4. Type Requirements: don't T need to be Assignable too?
Just no!
5. you could remove one version of push_back and push_front by using default arguments. Similar for insert()/rinsert()
I don't know if this is good idea or not, but all STL implementations I've seen have containers with both methods (one with default param and one without).
6. What's the use of "return_value_type" ?return_value_type operator[] (size_type index) const Return the element at the index position. Should it not be const_reference?
return_value_type is just optimization. It is const_reference for objects and value_type for primitive types.
7. when you state contracts like Precondition: *(this).size() > index don't you mean (*this).size() ? I would prefer that you omitted this entirely.
This is just typo. Anyway I would retain the precondition.
8. maybe you should add const_pointer data() const ?
It is not possible. data() is mutating operation. See the source code.
9 I assume you provide the basic exception safety for set_capacity(). However, I think you could achieve the strong guarantee by (1) allocating the new buffer and (2) start to copy elements [might throw] (3) swap the two buffers upon completion. The same goes for resize(). Why are they both provided? (If you made resizes 2nd argument to be the bool, then how would they differ?]
Yes, it works exactly like this. But the statement about provided exception safety covers the whole container.
10. Can't the exception guarantee for the copy-constructor be stronger too? (and assign(), and push_back(), push_front(), insert() )
No for insert()/rinsert(), push_xxx(), data() and erase(). See the source code.
11. Some operations must be nothrow: swap(), size(), capaciity(), pop_back(), pop_front().
Yes, they are. It is not written explicitly in the documentation (there is just no "Exceptions" section for each method). Jan __________________________________ Do you Yahoo!? Yahoo! Search - Find what you�re looking for faster http://search.yahoo.com
"Jan Gaspar" <jano_gaspar@yahoo.com> wrote in message news:20040305092703.88723.qmail@web41506.mail.yahoo.com...
1. your rationale mentions many characteristics that I would expect of std::deque. Do you have any idea how big the performance difference is? The memory is allocated at once, that's the biggest difference.
What I'm looking for is some more evidence that the data structure is really faster. I think that is relevant since that is your reason d'etre (or something, I never took French in highschool :-) ) for the container.
2. You mention "Guarantee of basic exception safety" as a design criteria. I would expect many operations to have a stronger guarantee.
Of cource, some methods provide stronger guarantee, but in general the container povides just basic exception safety. For some methods (e.g. insert) it is impossible to provide stronger guarantees. ------------- I guess I would like to know the exact guarantee of each function. It will be important for eg. when I have to provide a pointer version of circular_buffer for my smart containers.
4. Type Requirements: don't T need to be Assignable too? Just no!
Then how is an element overwritten?
5. you could remove one version of push_back and push_front by using default arguments. Similar for insert()/rinsert() I don't know if this is good idea or not, but all STL implementations I've seen have containers with both methods (one with default param and one without).
ok. I must admit that I have never seen this before. For example, my dinkumware only has vector::push_back( T& );
7. when you state contracts like Precondition: *(this).size() > index don't you mean (*this).size() ? I would prefer that you omitted this entirely.
This is just typo. Anyway I would retain the precondition. ---------- yes, I'm not talking about removing the precondition. I just don't think 'this->' adds anything. size() > index would be fine to me.
8. maybe you should add const_pointer data() const ?
It is not possible. data() is mutating operation. See the source code. --------------- ok. then maybe one should get more hints about this mutation (I did not have a clue), maybe like c.prepare_array(); foo( &*c.begin() ); And what complexity does it involves (linear, I assume)?
9 I assume you provide the basic exception safety for set_capacity(). However, I think you could achieve the strong guarantee by (1) allocating the new buffer and (2) start to copy elements [might throw] (3) swap the two buffers upon completion. The same goes for resize(). Why are they both provided? (If you made resizes 2nd argument to be the bool, then how would they differ?] Yes, it works exactly like this. But the statement about provided exception safety covers the whole container.
I think that saying that your container gives the basic exception safety guarantee is too weak a statement. Afterall, it *must* provide that guarantee. The standard specifies which operations that differs and under which cercumstances for T.
10. Can't the exception guarantee for the copy-constructor be stronger too? (and assign(), and push_back(), push_front(), insert() )
No for insert()/rinsert(), push_xxx(), data() and erase(). See the source code. ------------- Ok, let's try push_back: void push_back(param_value_type item) { if (full()) { if (empty()) return; (*) replace_last(item); // can throw increment(m_last); // nothrow m_first = m_last; // nothrow } else { m_alloc.construct(m_last, item); // can throw increment(m_last); // nothrow ++m_size; // nothrow } } AFAICT, you have the strong property unless you cannot roll-back stuff in replace_last/construct. (*) it might be good to document that push_back() can choose *not* to insert something. For example, it would be good for me to know when I write a pointer wrapper.
11. Some operations must be nothrow: swap(), size(), capaciity(), pop_back(), pop_front().
Yes, they are. It is not written explicitly in the documentation (there is just no "Exceptions" section for each method). ----------- Ok, I can live with that :-). You could consider one line that said that. br Thorsten
"Thorsten Ottosen" <nesotto@cs.auc.dk> wrote
1. your rationale mentions many characteristics that I would expect of std::deque. Do you have any idea how big the performance difference is?
What I'm looking for is some more evidence that the data structure is really faster. I think that is relevant since that is your reason d'etre (or something, I never took French in highschool :-) ) for the container.
Higher speed is welcomed side-effect of implementation here (no allocations). Choosen data structure provides a lot of flexibility, e.g. to implement debug support. That would be hard/impossible with std::deque. /Pavel
Hello!
1. your rationale mentions many characteristics that I would expect of std::deque. Do you have any idea how big the performance difference is? The memory is allocated at once, that's the biggest difference.
What I'm looking for is some more evidence that the data structure is really faster. I think that is relevant since that is your reason d'etre (or something, I never took French in highschool :-) ) for the container.
I agree with Pavel. Moreover you would have no control over iterator invalidation in std::deque.
2. You mention "Guarantee of basic exception
safety"
as a design criteria. I would expect many operations to have a stronger guarantee. Of cource, some methods provide stronger guarantee, but in general the container povides just basic exception safety. For some methods (e.g. insert) it is impossible to provide stronger guarantees.
I guess I would like to know the exact guarantee of each function. It will be important for eg. when I have to provide a pointer version of circular_buffer for my smart containers.
Ok, agree. Every method will have statement about its exception safety guarantee in the documentation.
4. Type Requirements: don't T need to be Assignable too? Just no!
Then how is an element overwritten?
Look at the replace() method in the source code.
7. when you state contracts like Precondition: *(this).size() > index don't you mean (*this).size() ? I would prefer
you omitted this entirely. This is just typo. Anyway I would retain the
that precondition. ---------- yes, I'm not talking about removing the precondition. I just don't think 'this->' adds anything. size() > index would be fine to me. Agree.
8. maybe you should add const_pointer data() const
? It is not possible. data() is mutating operation. See the source code. --------------- ok. then maybe one should get more hints about this mutation (I did not have a clue), maybe like c.prepare_array(); foo( &*c.begin() );
There are some words regarding iterator invalidation in the method documentation.
And what complexity does it involves (linear, I assume)? Yes, linear.
Jan __________________________________ Do you Yahoo!? Yahoo! Search - Find what you�re looking for faster http://search.yahoo.com
One last thing:
8. maybe you should add const_pointer data() const ? It is not possible. data() is mutating operation. See the source code.
ok. then maybe one should get more hints about this mutation (I did not have a clue), maybe like c.prepare_array(); foo( &*c.begin() ); There are some words regarding iterator invalidation in the method documentation.
ok, I'm not super religious about it, but my line of thought goes like this: if a programmer sees this kind of code: circular_buffer<T> cb; ... foo( cb.data() ); he would have to look at documentation to know what's going on (he could be a maintenance programmer who have no earlier knowlegde of circular buffer). data() is a very innocent word and I doubt that people in general would think all iterator were invalidated. I also doubt that they would think it was a linear time operation. Now, that's why I think it might be possible to give programmer just a little more hint about what might be going on by using a *verb* in the functions name, eg. compute_data(); prepare_data(); prepare_array(); linearize_data(); It's probably good to get other's oppinion about this too. br Thorsten
Perhaps in addition to a data() function, it would be useful if the container provided constant-time access to the data as two arrays. Perhaps something like std::pair<T *, T *> first_range() and std::pair<T *, T *> second_range(). (Where these can also be made available in const-form, since no internal modification is necessary) Then as Thorsten suggested, an operation such as linearize or reorder could be added which orders the elements such that first_range() contains all of the elements. -- Jeremy Maitin-Shepard
"Jeremy Maitin-Shepard" <jbms@attbi.com> wrote
Perhaps in addition to a data() function, it would be useful if the container provided constant-time access to the data as two arrays. Perhaps something like std::pair<T *, T *> first_range() and std::pair<T *, T *> second_range(). (Where these can also be made available in const-form, since no internal modification is necessary) Then as Thorsten suggested, an operation such as linearize or reorder could be added which orders the elements such that first_range() contains all of the elements.
data() does 'linearization' when needed (it was called flatten() when I proposed it ago). Do you have an example where returning two arrays is much better than optional reordering by data()? What kind of algorithm would be better to be called twice? /Pavel
The advantage is that the two ranges can be returned without any reordering. For instance, if the circular buffer is being used as a write buffer, it might prove more efficient to call the underlying write twice, once on each portion of the array, than to reorder the array (and call the underlying write only once). -- Jeremy Maitin-Shepard
At 09:04 AM 3/5/2004, Thorsten Ottosen wrote:
One last thing:
8. maybe you should add const_pointer data() const ? It is not possible. data() is mutating operation. See the source code.
ok. then maybe one should get more hints about this mutation (I did not have a clue), maybe like c.prepare_array(); foo( &*c.begin() ); There are some words regarding iterator invalidation in the method documentation.
ok, I'm not super religious about it, but my line of thought goes like this:
if a programmer sees this kind of code:
circular_buffer<T> cb; ... foo( cb.data() );
he would have to look at documentation to know what's going on (he could be a maintenance programmer who have no earlier knowlegde of circular buffer). data() is a very innocent word and I doubt that people in general would think all iterator were invalidated. I also doubt that they would think it was a linear time operation. Now, that's why I think it might be possible to give programmer just a little more hint about what might be going on by using a *verb* in the functions name, eg.
compute_data(); prepare_data(); prepare_array(); linearize_data();
It's probably good to get other's oppinion about this too.
FWIW, I agree. Particularly since data() in std::string is const. Verbs do a better job of indicating meaning. --Beman
Jan Gaspar wrote:
4. Type Requirements: don't T need to be Assignabletoo? Just no!
Then how is an element overwritten? Look at the replace() method in the source code.
This strikes me. All standard containers require T to be Assignable, so I don't understand the rationale for dropping such requirement. Does it give more freedom? Perhaps yes, but not so much IMHO. Users of containers are probably going to provide assignment anyway. Suppose that T *is* assignable, is destroy+copy construction better than assignment? Probably no, for several reasons, including: 1) assigment is probably more efficient. In particular it might avoid destruction/reconstruction of sub-objects non related with the class invariant (for example: buffers, mutexes, etc.). 2) with the dtor/ctor idiom, if the ctor throws an exception, the old element is lost and you can't do anything about it, so the container cannot provide more than the basic guarantee for any method that might overwrite elements. However, the user might implement assigment with the strong guarantee, the container might leverage on that and provide the strong guarantee too at least for methods that might overwrite a single element such as push_back/push_front. (Of course, the user might implement assignment so badly that it doesn't provide even the basic guarantee and the container could not recover from that, but a library such not try to outsmart the user... too much ;). Just my opinion, Alberto
Alberto Barbati <abarbati@iaanus.com> writes:
Suppose that T *is* assignable, is destroy+copy construction better than assignment? Probably no, for several reasons, including:
1) assigment is probably more efficient. In particular it might avoid destruction/reconstruction of sub-objects non related with the class invariant (for example: buffers, mutexes, etc.).
2) with the dtor/ctor idiom, if the ctor throws an exception, the old element is lost and you can't do anything about it, so the container cannot provide more than the basic guarantee for any method that might overwrite elements. However, the user might implement assigment with the strong guarantee, the container might leverage on that and provide the strong guarantee too at least for methods that might overwrite a single element such as push_back/push_front. (Of course, the user might implement assignment so badly that it doesn't provide even the basic guarantee and the container could not recover from that, but a library such not try to outsmart the user... too much ;).
Just my opinion,
Well said. -- Dave Abrahams Boost Consulting www.boost-consulting.com
--- David Abrahams <dave@boost-consulting.com> wrote:
Alberto Barbati <abarbati@iaanus.com> writes:
Suppose that T *is* assignable, is destroy+copy construction better than assignment? Probably no, for several reasons, including:
1) assigment is probably more efficient. In particular it might avoid destruction/reconstruction of sub-objects non related with the class invariant (for example: buffers, mutexes, etc.). I agree the assignment is more efficient. If you dig in the code little bit you will find that there is assignment operation provided for the primitive types.
2) with the dtor/ctor idiom, if the ctor throws an
element is lost and you can't do anything about it, so the container cannot provide more than the basic guarantee for any method that might overwrite elements. However,
implement assigment with the strong guarantee,
exception, the old the user might the container might
leverage on that and provide the strong guarantee too at least for methods that might overwrite a single element such as push_back/push_front. (Of course, the user might implement assignment so badly that it doesn't provide even the basic guarantee and the container could not recover from that, but a library such not try to outsmart the user... too much ;).
Just my opinion,
The idea behind the dtor/ctor idiom is like this: suppose you have full circular_buffer and you want to push_back a new element (instance of some class). That means the fron-most element is about to be overwritten. Now if there will be the assignment idiom applied the front-most will be assigned to the new one - it will be not destroyed (no destructor will be called). IMHO this is not correct. The old element will not disappear - just its value/state will be different. I think that the overwrite operation means destruction of the old object, NOT assignment. What do you think? Jan
Well said.
-- Dave Abrahams Boost Consulting www.boost-consulting.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
__________________________________ Do you Yahoo!? Yahoo! Search - Find what you�re looking for faster http://search.yahoo.com
Hi Jan, On Sunday, March 7, 2004, at 04:31 PM, Jan Gaspar wrote:
overwritten. Now if there will be the assignment idiom applied the front-most will be assigned to the new one - it will be not destroyed (no destructor will be called). IMHO this is not correct. The old element will not disappear - just its value/state will be different. I think that the overwrite operation means destruction of the old object, NOT assignment. What do you think?
I don't see how it makes any difference from the semantic point of view. Other than tracing calls to destructors, are there any other ways to tell the difference? Another note about the documentation... whichever way this issues end up, more needs to be said about it in the docs. Currently, the docs say "overwrite" which to me sounds like assignment, and the docs never mention destroying the objects. I think you either need to give a technical definition for what you mean by "overwrite", or better yet, use different words. Cheers, Jeremy
--- Jeremy Siek <jsiek@osl.iu.edu> wrote:
Another note about the documentation... whichever way this issues end up, more needs to be said about it in the docs. Currently, the docs say "overwrite" which to me sounds like assignment, and the docs never mention destroying the objects. I think you either need to give a technical definition for what you mean by "overwrite", or better yet, use different words.
I agree with you. I have to specify the exact meaning of the "overwrite" operation. Jan __________________________________ Do you Yahoo!? Yahoo! Search - Find what you�re looking for faster http://search.yahoo.com
Jan Gaspar wrote:
I agree the assignment is more efficient. If you dig in the code little bit you will find that there is assignment operation provided for the primitive types.
That is good. However, I think that such optimization is unnecessary. For primitive types, the destructor is trivial and the copy constructor is the assignment, so I bet a reasonably good compiler can optimize the dtor/ctor idiom to a simple assigment even without any "help" in the form of template machinery. Besides, bad compilers may introduce pessimizations... ;)
The idea behind the dtor/ctor idiom is like this: suppose you have full circular_buffer and you want to push_back a new element (instance of some class). That means the fron-most element is about to be overwritten. Now if there will be the assignment idiom applied the front-most will be assigned to the new one - it will be not destroyed (no destructor will be called). IMHO this is not correct. The old element will not disappear - just its value/state will be different. I think that the overwrite operation means destruction of the old object, NOT assignment. What do you think?
That's interesting, indeed. I agree it is more "correct". However, I don't see this improved correctness bringing a real benefit to the user. Do you have at least one use case where the ctor/dtor idiom can be leveraged by the user in order to provide a feature not obtainable with plain assignment? BTW, this discussion triggers some other ideas. Have you considered adding to the circular_buffer the capability to optionally notify the user about an impeding overwrite? I have at least one use case where it might be useful. It might be as easy as invoking a boost::function0 callback, at the cost of few bytes in footprint and an extra test before any overwrite. Alternatively, we could put hooks (in form of a template policy, for example) in the main container that are then implemented by a container adaptor, so the user won't pay if it doesn't want such a feature. Alberto
Alberto Barbati <abarbati@iaanus.com> writes:
[snip]
BTW, this discussion triggers some other ideas. Have you considered adding to the circular_buffer the capability to optionally notify the user about an impeding overwrite? I have at least one use case where it might be useful. It might be as easy as invoking a boost::function0 callback, at the cost of few bytes in footprint and an extra test before any overwrite. Alternatively, we could put hooks (in form of a template policy, for example) in the main container that are then implemented by a container adaptor, so the user won't pay if it doesn't want such a feature.
I would think that sort of feature would be better implemented as a wrapper around the circular_buffer container. -- Jeremy Maitin-Shepard
Jeremy Maitin-Shepard wrote:
Alberto Barbati <abarbati@iaanus.com> writes:
BTW, this discussion triggers some other ideas. Have you considered adding to the circular_buffer the capability to optionally notify the user about an impeding overwrite? I have at least one use case where it might be useful. It might be as easy as invoking a boost::function0 callback, at the cost of few bytes in footprint and an extra test before any overwrite. Alternatively, we could put hooks (in form of a template policy, for example) in the main container that are then implemented by a container adaptor, so the user won't pay if it doesn't want such a feature.
I would think that sort of feature would be better implemented as a wrapper around the circular_buffer container.
I tend to agree, in fact I mentioned container adaptor (= wrapper) in the list of alternatives. I guess such an adaptor could perform the task more efficiently if the underlying container provided the right hooks, but until we agree on the semantic and have a reasonable test implementation it's difficult to tell. Alberto
"Alberto Barbati" <abarbati@iaanus.com> wrote in message news:c2gk5o$6v4$1@sea.gmane.org...
Jan Gaspar wrote:
I agree the assignment is more efficient. If you dig in the code little bit you will find that there is assignment operation provided for the primitive types.
That is good. However, I think that such optimization is unnecessary. For primitive types, the destructor is trivial and the copy constructor is the assignment, so I bet a reasonably good compiler can optimize the dtor/ctor idiom to a simple assigment even without any "help" in the form of template machinery. Besides, bad compilers may introduce pessimizations... ;)
The cases where a call to a destructor is actually important beacuse it does some non-trivial work, one really need to ensure not even temporary objects of the type exists. That's one of the capabilities my smart containers will allow, ie, "overwriting" really means destructing and replacing. br Thorsten
Thorsten Ottosen wrote:
"Alberto Barbati" <abarbati@iaanus.com> wrote in message news:c2gk5o$6v4$1@sea.gmane.org...
That is good. However, I think that such optimization is unnecessary. For primitive types, the destructor is trivial and the copy constructor is the assignment, so I bet a reasonably good compiler can optimize the dtor/ctor idiom to a simple assigment even without any "help" in the form of template machinery. Besides, bad compilers may introduce pessimizations... ;)
The cases where a call to a destructor is actually important beacuse it does some non-trivial work, one really need to ensure not even temporary objects of the type exists. That's one of the capabilities my smart containers will allow, ie, "overwriting" really means destructing and replacing.
I'm sorry, I don't understand what you are trying to say here. I started my sentence with "For primitive types"... Alberto
Thorsten Ottosen wrote: [snip]
The cases where a call to a destructor is actually important beacuse it does some non-trivial work, one really need to ensure not even temporary objects of the type exists. That's one of
"Alberto Barbati" <abarbati@iaanus.com> wrote in message news:c2hhhi$lgs$1@sea.gmane.org... the
capabilities my smart containers will allow, ie, "overwriting" really means destructing and replacing.
I'm sorry, I don't understand what you are trying to say here. I started my sentence with "For primitive types"...
yeah, I could have said it better :-) What I meant was that copy-behavior is ususally incompatible with non-trivial destructors. What I mean by non-trivial destructors is that eg. a file is closed or a connection is closed. In those cases making temporaries and copies is not good: you want more explicit control over when the destructor is called. (hence you need a container of heap-allocated objects and not something like vector<Socket> ) For most value-like objects we have the opposite situation and we don't mind if an object is overwritten by assignment of if destructors are called. br Thorsten
Thorsten Ottosen wrote:
"Alberto Barbati" <abarbati@iaanus.com> wrote in message news:c2hhhi$lgs$1@sea.gmane.org...
Thorsten Ottosen wrote:
[snip]
The cases where a call to a destructor is actually important beacuse it
does
some non-trivial work, one really need to ensure not even temporary objects of the type exists. That's one of
the
capabilities my smart containers will allow, ie, "overwriting" really
means
destructing and replacing.
I'm sorry, I don't understand what you are trying to say here. I started my sentence with "For primitive types"...
yeah, I could have said it better :-) What I meant was that copy-behavior is ususally incompatible with non-trivial destructors. What I mean by non-trivial destructors is that eg. a file is closed or a connection is closed. In those cases making temporaries and copies is not good: you want more explicit control over when the destructor is called. (hence you need a container of heap-allocated objects and not something like vector<Socket> ) For most value-like objects we have the opposite situation and we don't mind if an object is overwritten by assignment of if destructors are called.
I learned that good programming practice is that if a class requires a non-trivial destructor it should either implement both the copy constructor and the assignment operator or declare them private and leave them unimplemented. Moreover, if either the copy constructor or the assignment operator is defined, both of them should. I never found a case where it was worth violating this practice, maybe you have such an example? Fact is that I still fail to understand why a class that has a meaningful copy constructor cannot implement a meaningful assignment operator with the same semantic as dtor+copy ctor, but more efficiently. Alberto
"Alberto Barbati" <abarbati@iaanus.com> wrote in message news:c2jldp$j19$1@sea.gmane.org...
Thorsten Ottosen wrote: [snip]
yeah, I could have said it better :-) What I meant was that copy-behavior is ususally incompatible with non-trivial destructors. What I mean by non-trivial destructors is that eg. a file is closed or a connection is closed. In those cases making temporaries and copies is not good: [snip] I learned that good programming practice is that if a class requires a non-trivial destructor it should either implement both the copy constructor and the assignment operator or declare them private and leave them unimplemented.
true. Don't be confusd by my slight misuse of "non-trivial destructor".
Moreover, if either the copy constructor or the assignment operator is defined, both of them should.
also true.
I never found a case where it was worth violating this practice, maybe you have such an example?
no.
Fact is that I still fail to understand why a class that has a meaningful copy constructor cannot implement a meaningful assignment operator with the same semantic as dtor+copy ctor, but more efficiently.
I can't either. [remark: we agree that circular_buffer should use assignment] [note:I was trying to mention a specific type of RAII objects which cannot be put in copying containers].Copy behavior is not always desireable. If assigment of a Socket class would require the connection to close(), then I don't want assigment. And I don't want temporary objects. Hence the object must be heap-allocated. br Thorsten
--- Alberto Barbati <abarbati@iaanus.com> wrote:
BTW, this discussion triggers some other ideas. Have you considered adding to the circular_buffer the capability to optionally notify the user about an impeding overwrite?
I didn't think of it. Anyway it is interesting. Jan __________________________________ Do you Yahoo!? Yahoo! Search - Find what you�re looking for faster http://search.yahoo.com
Jan Gaspar <jano_gaspar@yahoo.com> writes:
Now if there will be the assignment idiom applied the front-most will be assigned to the new one - it will be not destroyed (no destructor will be called). IMHO this is not correct. The old element will not disappear - just its value/state will be different. I think that the overwrite operation means destruction of the old object, NOT assignment. What do you think?
I think it introduces inefficiencies that most people won't want to pay for, and I don't see any benefits other than lifting the requirement on assignability. Types that are copiable but not assignable are rare, though, at least in my experience. -- Dave Abrahams Boost Consulting www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote
Now if there will be the assignment idiom applied the front-most will be assigned to the new one - it will be not destroyed (no destructor will be called). IMHO this is not correct. The old element will not disappear - just its value/state will be different. I think that the overwrite operation means destruction of the old object, NOT assignment. What do you think?
I think it introduces inefficiencies that most people won't want to pay for, and I don't see any benefits other than lifting the requirement on assignability. Types that are copiable but not assignable are rare, though, at least in my experience.
I think you are missing the point: object pushed out of circular_buffer because container got full must be destroyed. Therefore assignement is not used, therefore no CopyConstructible requirement on T. (I'll look whether there aren't other places requiring assignement.) /Pavel
"Pavel Vozenilek" <pavel_vozenilek@hotmail.com> writes:
"David Abrahams" <dave@boost-consulting.com> wrote
Now if there will be the assignment idiom applied the front-most will be assigned to the new one - it will be not destroyed (no destructor will be called). IMHO this is not correct. The old element will not disappear - just its value/state will be different. I think that the overwrite operation means destruction of the old object, NOT assignment. What do you think?
I think it introduces inefficiencies that most people won't want to pay for, and I don't see any benefits other than lifting the requirement on assignability. Types that are copiable but not assignable are rare, though, at least in my experience.
I think you are missing the point:
Actually, no. I realized you're making the argument below.
object pushed out of circular_buffer because container got full must be destroyed.
Why? I mean, the only reason I can see for that requirement is an aesthetic one. I don't see any logical foundation for the assertion. -- Dave Abrahams Boost Consulting www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote
object pushed out of circular_buffer because container got full must be destroyed.
Why? I mean, the only reason I can see for that requirement is an aesthetic one. I don't see any logical foundation for the assertion.
I am not getting something. You are saying objects can go away without being destructed? /Pavel
"Pavel Vozenilek" <pavel_vozenilek@hotmail.com> writes:
"David Abrahams" <dave@boost-consulting.com> wrote
object pushed out of circular_buffer because container got full must be destroyed.
Why? I mean, the only reason I can see for that requirement is an aesthetic one. I don't see any logical foundation for the assertion.
I am not getting something. You are saying objects can go away without being destructed?
No, I'm saying that their values can go away without destruction: you could replace their values in the buffer using assignment instead of destroy + construct. There's no a priori reason they have to be destroyed. When I erase objects from a std::vector, the objects being erased don't neccessarily get destroyed. They may be assigned. For example, here's STLPort's vector<T>::erase(iterator) implementation: iterator erase(iterator __position) { if (__position + 1 != end()) __copy_ptrs(__position + 1, this->_M_finish, __position, _TrivialAss()); --this->_M_finish; _Destroy(this->_M_finish); return __position; } Notice that only the last element of the vector is destroyed. -- Dave Abrahams Boost Consulting www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote
No, I'm saying that their values can go away without destruction: you could replace their values in the buffer using assignment instead of destroy + construct. There's no a priori reason they have to be destroyed.
When I erase objects from a std::vector, the objects being erased don't neccessarily get destroyed. They may be assigned. For example, here's STLPort's vector<T>::erase(iterator) implementation:
[snip code]
Notice that only the last element of the vector is destroyed.
Quoting from similar discussion on c.l.c++.m: http://tinyurl.com/2c3na --- quote about vector::erase --- The standard says this: "The destructor of T is called the number of times equal to the number of the elements erased, but the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements." ------------------------------------ With circular buffer the destructor wouldn't be called at all, in similar circumstance. Eample: Circular buffer of size 3. You create 100 of objects and push them in. You would get: - 100 constructors called, - 97 copy constructors called, - 3 destructors called. /Pavel
"Pavel Vozenilek" <pavel_vozenilek@hotmail.com> writes:
"David Abrahams" <dave@boost-consulting.com> wrote
No, I'm saying that their values can go away without destruction: you could replace their values in the buffer using assignment instead of destroy + construct. There's no a priori reason they have to be destroyed.
When I erase objects from a std::vector, the objects being erased don't neccessarily get destroyed. They may be assigned. For example, here's STLPort's vector<T>::erase(iterator) implementation:
[snip code]
Notice that only the last element of the vector is destroyed.
Quoting from similar discussion on c.l.c++.m: http://tinyurl.com/2c3na
--- quote about vector::erase --- The standard says this: "The destructor of T is called the number of times equal to the number of the elements erased, but the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements." ------------------------------------
With circular buffer the destructor wouldn't be called at all, in similar circumstance.
Eample: Circular buffer of size 3. You create 100 of objects and push them in. You would get: - 100 constructors called, - 97 copy constructors called, - 3 destructors called.
Yeah, but my point is: so what? I still see no a priori reason that circular_buffer must do element destruction before it is itself destroyed. std::vector *has* to do some destruction in order to get the right semantics. Arguably, circular_buffer does not. If it doesn't matter *which* vector elements get destroyed upon erase, then I presume it doesn't matter which circular_buffer elements get destroyed. In that case, why should it matter that any elements are destroyed? -- Dave Abrahams Boost Consulting www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote
I still see no a priori reason that circular_buffer must do element destruction before it is itself destroyed. std::vector *has* to do some destruction in order to get the right semantics. Arguably, circular_buffer does not. If it doesn't matter *which* vector elements get destroyed upon erase, then I presume it doesn't matter which circular_buffer elements get destroyed. In that case, why should it matter that any elements are destroyed?
If you have class and the class has static member keeping number of object instances alive (incremented in constructor, decremented in destructor): - putting these objects into vector keeps counter valid, - circular_buffer with assignement won't. That was problem I did have with earlier version of circular_buffer and that' why I did ask for construct/destruct feature. It is maybe border case but IMHO valid one against assignement. /Pavel
"Pavel Vozenilek" <pavel_vozenilek@hotmail.com> writes:
"David Abrahams" <dave@boost-consulting.com> wrote
I still see no a priori reason that circular_buffer must do element destruction before it is itself destroyed. std::vector *has* to do some destruction in order to get the right semantics. Arguably, circular_buffer does not. If it doesn't matter *which* vector elements get destroyed upon erase, then I presume it doesn't matter which circular_buffer elements get destroyed. In that case, why should it matter that any elements are destroyed?
If you have class and the class has static member keeping number of object instances alive (incremented in constructor, decremented in destructor):
- putting these objects into vector keeps counter valid, - circular_buffer with assignement won't.
I can't understand this claim. If the counter works properly, then it will stay valid. Assignment doesn't magically make instances appear or disappear. In one case you assign and the counter doesn't change. In the other you destroy one element and construct another in its place and the counter is incremented, then decremented.
That was problem I did have with earlier version of circular_buffer and that' why I did ask for construct/destruct feature.
It is maybe border case but IMHO valid one against assignement.
I don't get it. -- Dave Abrahams Boost Consulting www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote
I can't understand this claim. If the counter works properly, then it will stay valid.
This example was too simplified (and thus not to the point). More complex one: ----------------------- struct my_class { void* database_handle; my_class() { database_handle = allocate_handle(); } ~my_class() { destroy_db_handle(database_handle); } my_class& operator=(const my_class& other) { // no copy of database handle, not needed, // not useful here } my_class(const my_class& other) { database_handle = allocate_handle(); // needs unique db connection } }; circular_buffer<my_class> buffer(1); { my_class a; buffer.push_back(a); // 2 handles after function returns ... } { my_class b; buffer.push_back(b); // desctructor not called, handle lost ... } ----------------- To deal with lost resources you would need to modify operator=() to take ownership of all rhs resources. But in this case following will fail: my_class a; my_class b; a = b; // b is stripped of its handle now, cannot be used /Pavel
Pavel Vozenilek wrote:
"David Abrahams" <dave@boost-consulting.com> wrote
I can't understand this claim. If the counter works properly, then it will stay valid.
This example was too simplified (and thus not to the point).
More complex one:
----------------------- struct my_class { void* database_handle;
my_class() { database_handle = allocate_handle(); } ~my_class() { destroy_db_handle(database_handle); } my_class& operator=(const my_class& other) { // no copy of database handle, not needed, // not useful here } my_class(const my_class& other) { database_handle = allocate_handle(); // needs unique db connection } };
circular_buffer<my_class> buffer(1);
{ my_class a; buffer.push_back(a); // 2 handles after function returns ... }
{ my_class b; buffer.push_back(b); // desctructor not called, handle lost ... }
I don't see why a handle is lost. { // Only one handle in existence at this point, the one // previously added to buffer by "buffer.push_back(a);". my_class b; // Now two handles exist, one in b, and one in buffer. buffer.push_back(b); // Two handles still exist -- push_back uses assignment, which // doesn't affect handles at all. No new handles have been // created by push_back(b). } // Now only one handle exists, in buffer, since b has // gone out of scope and has been destroyed. What am I missing? Bob
"Alberto Barbati" <abarbati@iaanus.com> wrote [snip assignement prefereble over destruct/construct]
2) with the dtor/ctor idiom, if the ctor throws an exception, the old element is lost and you can't do anything about it, so the container cannot provide more than the basic guarantee for any method that might overwrite elements. However, the user might implement assigment with the strong guarantee, the container might leverage on that and provide the strong guarantee too at least for methods that might overwrite a single element such as push_back/push_front. (Of course, the user might implement assignment so badly that it doesn't provide even the basic guarantee and the container could not recover from that, but a library such not try to outsmart the user... too much ;).
This argument isn't valid. push_back() will construct elements when there's space available in circular buffer. Therefore using assignement won't give the method strong guarantee (in all cases). /Pavel
Pavel Vozenilek wrote:
"Alberto Barbati" <abarbati@iaanus.com> wrote
[snip assignement prefereble over destruct/construct]
2) with the dtor/ctor idiom, if the ctor throws an exception, the old element is lost and you can't do anything about it, so the container cannot provide more than the basic guarantee for any method that might overwrite elements. However, the user might implement assigment with the strong guarantee, the container might leverage on that and provide the strong guarantee too at least for methods that might overwrite a single element such as push_back/push_front. (Of course, the user might implement assignment so badly that it doesn't provide even the basic guarantee and the container could not recover from that, but a library such not try to outsmart the user... too much ;).
This argument isn't valid.
push_back() will construct elements when there's space available in circular buffer.
Therefore using assignement won't give the method strong guarantee (in all cases).
If there is space, the buffer tries to copy construct an element in an empty (uninitialized) space, then the internal state of the buffer is updated (this operation does not throw). If the copy ctor throws an exception, no object is constructed and the buffer state is not modified => the buffer is in the exact state it was before the call => strong guarantee. If there is not enough space, the buffer tries to replace one value by invoking operator=, then the internal state is updated (this operation doesn't throw). *If operator= provides the strong guarantee* and throws, the element already in the buffer is not modified and the buffer state is not modified either => the buffer is in the exact state it was before the call => strong guarantee. It seems to me that this cover all cases and you always get strong guarantee. Am I missing something? Alberto
"Alberto Barbati" <abarbati@iaanus.com> wrote
If there is space, the buffer tries to copy construct an element in an empty (uninitialized) space, then the internal state of the buffer is updated (this operation does not throw). If the copy ctor throws an exception, no object is constructed and the buffer state is not modified => the buffer is in the exact state it was before the call => strong guarantee.
If there is not enough space, the buffer tries to replace one value by invoking operator=, then the internal state is updated (this operation doesn't throw). *If operator= provides the strong guarantee* and throws, the element already in the buffer is not modified and the buffer state is not modified either => the buffer is in the exact state it was before the call => strong guarantee.
It seems to me that this cover all cases and you always get strong guarantee. Am I missing something?
No, you are right here. /Pavel
I have read the documentation for the library, and browsed through the test code. Based on that I recommend acceptance of the circular buffer library. Nice work Jan! Here are some suggestions. This sentences seems unnecessary: In fact the circular_buffer is defined in the file boost/circular_buffer/base.hpp, but it is necessary to include the boost/circular_buffer.hpp in order to use this container Have you checked whether CopyConstructible is in fact the only requirements needed on the type parameter T? For example, I bet T must also be Assignable. But who knows what other requirements you may have missed (it is easy to miss them). I recommend using concept archetypes to check this. There are no requirements on the Alloc type parameter. Surely there should be some. I'm not a big fan of how the semantics section is separated from the function prototypes. I'd rather see all the information about a function in one place. Also I'm not fond of how the "source code documentation" is separate from the main documentation. I had to click around a lot to find information. Best wishes, Jeremy
--- Jeremy Siek <jsiek@osl.iu.edu> wrote:
I have read the documentation for the library, and browsed through the test code. Based on that I recommend acceptance of the circular buffer library. Nice work Jan!
Here are some suggestions.
This sentences seems unnecessary: In fact the circular_buffer is defined in the file boost/circular_buffer/base.hpp, but it is necessary to include the boost/circular_buffer.hpp in order to use this container
No it isn't, I'll change it.
Have you checked whether CopyConstructible is in fact the only requirements needed on the type parameter T? For example, I bet T must also be Assignable. But who knows what other requirements you may have missed (it is easy to miss them). I recommend using concept archetypes to check this.
Yes, it is the only requirement.
There are no requirements on the Alloc type parameter. Surely there should be some.
I think the Alloc has to be just an allocator (with the neccessary methods). No special requirements needed. Jan __________________________________ Do you Yahoo!? Yahoo! Search - Find what you�re looking for faster http://search.yahoo.com
Hi Jan, On Mar 8, 2004, at 1:03 PM, Jan Gaspar wrote:
I think the Alloc has to be just an allocator (with the neccessary methods). No special requirements needed.
That's what I mean, the documentation should say that Alloc is required to meet the standard allocator requirements. Cheers, Jeremy _______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington C++ Booster (http://www.boost.org) Office phone: (812) 856-1820 _______________________________________________
Hi, I'd like to cast my vote on the circular_buffer review. I have read through all documentation, briefly skimmed through the implementation and test code. a.. What is your evaluation of the design? ------------------------------------------ The library follows the standard STL container conventions very closely. Provided interface is sufficient and well defined. Debugging facility seems very useful. One objection I have is following: Interaface models Sequence concept, but one of the concept's requirements is missing. There is no constructor taking just two iterators as a parameter. Initialization from a pair of iterators is provided, but the signature does not match the requirements of Sequence concept. It is not possible to use this container in generic algorithms, that require such a constructor (this is quite common case IMHO). I would like to see more adaptors in addtion to one provided. Concretely, one that have been already mentioned, which provides means for notification when a buffer is empty/full. This might be extremly useful. Another adaptor I would like to see, is one, that disallows rewriting of the old elements. Such an buffer can be used as a faster alternative to std::deque, when a bounded buffer is sufficient. Checking for overflow can be provided by an exception or an error code from insering operations. b.. What is your evaluation of the implementation? -------------------------------------------------- Implementaion seem quite solid. I have no objections. As for the assign-construct/destruct discussion, I think, that one of options would be to use a policy class to define the behaviour. Both approaches have their own pros and cons. Assignment might bring some speedup and I would prefer it as default. Construct/Destruct might be benefitial in some applications (f.e. an object is notified, by a destructor, that it has been removed from buffer). c.. What is your evaluation of the documentation? ------------------------------------------------- Documentation seem sound and well prepared. I was able easily understand how to use the library. Examples are illustrative enough for the common usage. I have few suggestion, though. First of all, I don't like doxygen generated documenation too much. This might be my personal preference, however it does not integrage with other parts of documentation well. Source documentaion has different layout and format than the rest and IMO it is little bit confusing to use two styles in one doc. There is an obvious suggestion to solve this problem: convert docs to boost-book. d.. What is your evaluation of the potential usefulness of the library? ----------------------------------------------------------------------- I find the library useful for many application. Either as a bounded aging buffer or as a faster alternative for deque when memory limit is benefitial or required. e.. Did you try to use the library? With what compiler? Did you have any problems? -------------------------------------------------------------------------- I have compiled test cases without any problem on vc7.1 and gcc3.3.1 under cygwin f.. How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? ----------------------------------------------------------------------- I have spend about 2 to 3 hours studying the code, the documentation and reading the discussions here on the list. g.. Are you knowledgeable about the problem domain? --------------------------------------------------- I have good knowledge about STL containers and concepts related to them. h.. Do you think the library should be accepted as a Boost library? -------------------------------------------------------------------- I vote that the library should be ACCEPTED to boost. It provides handy utility. Design and implementation is solid, documentation is acceptable. Regards, Pavol
Pavel Vozenilek wrote:
Discovered problems in code or in documentation, missing features, portability issues and finally opinion whether the library belongs to Boost is welcomed.
I believe this library is very useful and generally well-written. I found a few minor problems that I deem workable. My opinion is that the library should be accepted. The only things I would like to be discussed thouroughly are the "ctor/dtor vs. assignment" dispute (see specific thread) and the possibility to provide extension points that allows a (possibly future) implementation of a "notifying" container (ibid.). About portability issues, these lines of code (file details.hpp, lines 274-277) invoke undefined behaviour, according to 5.7/5: if (less(rhs, lhs) && lhs.m_it <= rhs.m_it) return lhs.m_it + m_buff->capacity() - rhs.m_it; if (less(lhs, rhs) && lhs.m_it >= rhs.m_it) return lhs.m_it - m_buff->capacity() - rhs.m_it; that's because the expressions (lhs.m_it + m_buff->capacity()) and (lhs.m_it - m_buff->capacity()) might produce a pointer outside the allocated range. I suggest to replace those lines with: if (less(rhs, lhs) && lhs.m_it <= rhs.m_it) return lhs.m_it - rhs.m_it + m_buff->capacity(); if (less(lhs, rhs) && lhs.m_it >= rhs.m_it) return lhs.m_it - rhs.m_it - m_buff->capacity(); or, even better, to avoid complaints from nasty compilers about mixed signed/unsigned usage: if (less(rhs, lhs) && lhs.m_it <= rhs.m_it) return (lhs.m_it - rhs.m_it) + static_cast<difference_type>(m_buff->capacity()); if (less(lhs, rhs) && lhs.m_it >= rhs.m_it) return (lhs.m_it - rhs.m_it) - static_cast<difference_type>(m_buff->capacity()); To be extra paranoid, we should ensure that the static_cast doesn't overflow. This could be done by changing the defintion of max_size() in base.hpp from: size_type max_size() const { return m_alloc.max_size(); } to size_type max_size() const { return std::min<size_type>(m_alloc.max_size(), (std::numeric_limits<difference_type>::max)()); } I've seen this issue overlooked even in commercial standard library implementations. As c.end() - c.begin() == c.size() and c.end() - c.begin() must be representable as a positive quantity of type difference_type, this imply that c.size() <= c.max_size() <= numeric_limits<difference_type>::max(). On a side note, I think it should be good if the implementation of the iterator classes used the new Boost Iterators Library. I have uploaded in the Boost file area an implementation using boost::iterator_facade (filename is circular_buffer_new_iterators.zip). The implementation already include the fix above and also has a slightly more optimized version of the less() method, with fewer tests and without switches. Problem is that there is something wrong with the implementation of operator[] in iterator_facade and the regression test does not compile anymore :-( However, if I hack iterator_facade::operator[] to avoid the use of the operator_brackets_proxy class, all regression tests pass. Maybe it would be good to discuss this problem of the iterator_facade in a different thread. Alberto Barbati
Alberto Barbati <abarbati@iaanus.com> writes:
Problem is that there is something wrong with the implementation of operator[] in iterator_facade and the regression test does not compile anymore :-(
What makes you say that there's something wrong with iterator_facade's operator[]? Is it possible that the regression test makes invalid assumptions about the way an iterator's operator[] is supposed to work?
However, if I hack iterator_facade::operator[] to avoid the use of the operator_brackets_proxy class
That's unneccessary. Any iterator_facade behavior you want to replace can simply be added to your derived iterator class.
all regression tests pass. Maybe it would be good to discuss this problem of the iterator_facade in a different thread.
Here we are! -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Alberto Barbati <abarbati@iaanus.com> writes:
Problem is that there is something wrong with the implementation of operator[] in iterator_facade and the regression test does not compile anymore :-(
What makes you say that there's something wrong with iterator_facade's operator[]? Is it possible that the regression test makes invalid assumptions about the way an iterator's operator[] is supposed to work?
The problem is triggered by the expression BOOST_CHECK(it[0] == 2); found in file base_test.cpp line 157. VC .NET 2003 gives the following error message: error C2678: binary '==' : no operator found which takes a left-hand operand of type 'boost::detail::operator_brackets_result<Iterator,Value,Reference>::type' (or there is no acceptable conversion) with [ Iterator=boost::cb_details::cb_iterator<boost::circular_buffer<Integer>,Integer>, Value=Integer, Reference=Integer & ] "it" is defined as circular_buffer<Integer>::iterator. As the right hand side is not an "Integer" I also tried writing: BOOST_CHECK(it[0] == Integer(2)); but the error message stays the same.
However, if I hack iterator_facade::operator[] to avoid the use of the operator_brackets_proxy class
That's unneccessary. Any iterator_facade behavior you want to replace can simply be added to your derived iterator class.
Yes. Sure you are right. I feel kind of stupid, I should have thought about it in the first place. I am uploading a revised version of circular_buffer_new_iterators_v2.zip that overrides operator[]. All regression tests passes with VC7.1. I also made the implementation members private and fixed the comments. Anyway you'll agree that the issue is quite general and it might be interesting to investigate if we could find a solution at the iterator_facade level.
all regression tests pass. Maybe it would be good to discuss this problem of the iterator_facade in a different thread.
Here we are!
:-) Alberto
Alberto Barbati <abarbati@iaanus.com> writes:
David Abrahams wrote:
What makes you say that there's something wrong with iterator_facade's operator[]? Is it possible that the regression test makes invalid assumptions about the way an iterator's operator[] is supposed to work?
The problem is triggered by the expression
BOOST_CHECK(it[0] == 2);
found in file base_test.cpp line 157. VC .NET 2003 gives the following error message:
error C2678: binary '==' : no operator found which takes a left-hand operand of type boost::detail::operator_brackets_result<Iterator,Value,Reference>::type' (or there is no acceptable conversion) with [ Iterator=boost::cb_details::cb_iterator<boost::circular_buffer<Integer>,Integer>, Value=Integer, Reference=Integer & ]
"it" is defined as circular_buffer<Integer>::iterator. As the right hand side is not an "Integer" I also tried writing:
BOOST_CHECK(it[0] == Integer(2));
but the error message stays the same.
The right check would be: BOOST_CHECK(Integer(it[0]) == 2); The return type of a random access iterator's operator[] is only required to be *convertible* to its value_type.
I am uploading a revised version of circular_buffer_new_iterators_v2.zip that overrides operator[]. All regression tests passes with VC7.1. I also made the implementation members private and fixed the comments.
Anyway you'll agree that the issue is quite general and it might be interesting to investigate if we could find a solution at the iterator_facade level.
We've given it a lot of thought already. In general there's no way to detect that a given iterator implementation will return a reference to a persistent object from its dereference implementation. See http://www.boost.org/libs/iterator/doc/iterator_facade.html#operator. If you can come up with a way to decide reliably that the proxy is unneded, that'd be great -- but I doubt it can be done. Anyone who really cares about returning a reference from operator[] can do what you did. In general, though, there's no reason for any algorithm to use an iterator's operator[] anyway, so fulfilling the random-access requirement for operator[] is really a formality and it doesn't need to be optimal. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Alberto Barbati <abarbati@iaanus.com> writes:
David Abrahams wrote:
Anyway you'll agree that the issue is quite general and it might be interesting to investigate if we could find a solution at the iterator_facade level.
We've given it a lot of thought already. In general there's no way to detect that a given iterator implementation will return a reference to a persistent object from its dereference implementation. See http://www.boost.org/libs/iterator/doc/iterator_facade.html#operator.
I should have the docs more thouroughly before posting. Now I understand the situation better and I agree with the design. The docs are quite clear about it, but I bet that this issue will soon be the top FAQ about Boost.Iterator ;-)
If you can come up with a way to decide reliably that the proxy is unneded, that'd be great -- but I doubt it can be done. Anyone who really cares about returning a reference from operator[] can do what you did. In general, though, there's no reason for any algorithm to use an iterator's operator[] anyway, so fulfilling the random-access requirement for operator[] is really a formality and it doesn't need to be optimal.
Instead of trying a way to avoid the proxy, we could just help the compiler resolving certain kind of expressions like it[0] == 2. For example if the proxy implemented operator== like this: template <class Rhs> friend bool operator == (const operator_brackets_proxy& lhs, const Rhs& rhs) { return *(lhs.m_iter) == rhs; } we would not impose any additional requirement on the iterator unless the operator== is really needed. The problems I see with this suggestions are: 1) this will address only operators, it still may not help in some other contexts; 2) we should overload all operators twice and be careful about it[0] == it[1]. A *lot* of code. 3) to do things *really* right we definitely need some typeof-like facility to determine the return type of the operators. I guess that point 3 rules my suggestion out for the next several years, but I hope it still might be thought provoking :-) Alberto
I have very briefly (re-)reviewed Jan Gaspar's circular buffer. What is your evaluation of the design? It provides a useful 'should-be-standard' feature not provided elsewhere. What is your evaluation of the implementation? It works in my tests, and some usage. What is your evaluation of the documentation? Seems OK. Examples good and well commented. [Aside- although I am not a fan of Doxygen generated docs - somehow they never seem to tell what you want to know. Does the automatic-ness delude the author that he has done his job when he hasn't really barely started?] What is your evaluation of the potential usefulness of the library? When useful and appropriate, invaluable. STL compatibility should greatly increase its applicability. Did you try to use the library? Earlier versions. With what compiler? MSVC 7.1 Did you have any problems? No. Compiles cleanly even in strict mode. How much effort did you put into your evaluation? Shallow-depth study? Are you knowledgeable about the problem domain? Only as a user. Other comments: It is quite mature having been through a number of iterations under Boost (fairly friendly) fire for some time. Test suite looks OK. Do you think the library should be accepted as a Boost library? I vote for acceptance. Paul Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539 561830 +44 7714 330204 mailto: pbristow@hetp.u-net.com | -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Pavel Vozenilek | Sent: 05 March 2004 02:17 | To: boost@lists.boost.org | Subject: [boost] Formal Review: Circular Buffer
Hi, I did a short review of this library. - regarding the data() issue I think it should be mentioned that this function has linear complexity. A name reflecting this behavior would be even better. - the difference between resize() and set_capacity() should be mentioned more explicitly. It might be especially confusing since std::vector's reserve is quite similar to set_capacity but has a different name. - I am missing the counterpart to erase which shifts the elements before the erased elements and not the ones after. Probably this is not important but std::deque allows erasing at the front without invalidating all iterators (according to sgi-stl docs). - The insert() function has its rinsert() counterpart. The same issue for resize and set_capacity is solved with the boolean parameter remove_front. If this has an important reason it should be mentioned. If not I would like to see a more consistent solution. - In section Caveats: "... According to the semantics of rinsert, insertion overwrites front-most items as necessary ..." should probably read "back-most items" if this is a valid english word. - I compiled the library with g++ 3.2.2 and everything worked fine. But when I tried to compile the example from the documentation with a command line call to g++ I got the following error: [jan@affe test]$ g++ -Wall -Wno-long-long -ansi -pedantic -I .. -I $BOOST_ROOT cb_example.cpp ../boost/circular_buffer/base.hpp: In member function `void boost::circular_buffer<T, Alloc>::replace(Alloc::pointer, boost::call_traits<Alloc::value_type>::param_type) [with T = int, Alloc = std::allocator<int>]': ../boost/circular_buffer/base.hpp:1137: instantiated from `void boost::circular_buffer<T, Alloc>::replace_last(boost::call_traits<Alloc::value_type>::param_type) [with T = int, Alloc = std::allocator<int>]' ../boost/circular_buffer/base.hpp:605: instantiated from `void boost::circular_buffer<T, Alloc>::push_back(boost::call_traits<Alloc::value_type>::param_type) [with T = int, Alloc = std::allocator<int>]' cb_example.cpp:10: instantiated from here ../boost/circular_buffer/base.hpp:1105: invalid use of member ` boost::cb_details::cb_replace_category_traits<int>::tag' Without -ansi -pedantic it works fine. I don't know if it should work with -ansi -pedantic but I thought it worth mentioning - In general the documentation is quite good and well written. - I didn't look at the code in detail, but in order to understand some things I had a look at certain member functions and found them clearly implemented and easy to understand. - I cannot sufficiently evaluate the usefullness of this library since I haven't had the need for it in my previous work in C++. Actually I cannot imagine it being usefull in normal programming tasks where memory is plenty. And I haven't done embedded programming in C++ yet. - I spent approximatly 3 to 4 hours on studying the docs, clarifying certain things with the help of the code and compiling and looking at the examples and writing this email. - I'm no expert in the problem domain. Just a regular user of std:: and other containers. If some points mentioned above will be clarified and if other people (or me in the future) can find applications for it, I think its a very usefull library. Since I am quite sure that this will be the case I vote for acceptance. regards jan -- jan langer ... jan@langernetz.de "pi ist genau drei"
Bellow are few notes to circular_buffer library. Over weekend I'll reread the code and post remaining notes. /Pavel ____________________________________ 1. docs: there should be warning for data() documentation that the returned pointer gets very easily invalidated. ____________________________________ 2. docs: Synopsis in circular_buffer.html could be splitted by <p> into two paragraphs. It would look less "heavy". ____________________________________ 3. the macros as BOOST_CB_TRY should be at some time replaced by common Boost macros. These macros are proposed but not yet added there AFAIK. #if !(defined BOOST_NO_EXCEPTIONS) # define BOOST_TRY { try # define BOOST_CATCH(x) catch(x) # define BOOST_RETHROW throw # define BOOST_CATCH_END } #else # if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) # define BOOST_TRY { if ("") # define BOOST_CATCH(x) else if (!"") # else # define BOOST_TRY { if (true) # define BOOST_CATCH else if (false) # endif # define BOOST_RETHROW # define BOOST_CATCH_END } #endif _________________________________________ 4. circular_buffer.hpp: #include <boost/type_traits.hpp> should be replaced by finer granularity includes. This line big huge impact on compilation time. __________________________________________ 5. base.hpp: #if BOOST_CB_ENABLE_DEBUG #include <string.h> #endif maybe this can change to <cstring>. __________________________________________ 6. base.hpp, Intel C++ 7.0, warning on line: void replace(pointer pos, param_value_type item) { replace(pos, item, cb_details::template cb_replace_category_traits<value_type>::tag()); <<< here C:\Temp\temp\circular_buffer3.6\circular_buffer\boost/circular_buffer/base.h pp(1105): warning #1017: name following "template" must be a member template Dtto assign(), insert(), rinsert(). insert()/rinsert() in adaptor.hpp. __________________________________________ 7. base.hpp: few places contain text "circular_buffer<T, Alloc>". Helper type, e.g. self_t can be created and used there. Its slightly easier to read. __________________________________________ EOF
participants (13)
-
Alberto Barbati -
Beman Dawes -
David Abrahams -
Giovanni Bajo -
Jan Gaspar -
Jan Langer -
Jeremy Maitin-Shepard -
Jeremy Siek -
Paul A Bristow -
Pavel Vozenilek -
Pavol Droba -
Robert Bell -
Thorsten Ottosen