[boost] Re: Re: Formal Review Request: circular_buffer [long]

From: Pavel Vozenilek (pavel_vozenilek_at_[hidden])
Date: 2003-07-21 12:34:19

Hello Jan,

Few more comments + answers.

1. Documentation: can circular_buffer<> be used as
   container for stack/queue/priority_queue?

2. When BOOST_NO_EXCEPTION is defined, library
   shouldn't throw but call function
   throw_exception() from throw_exception.hpp
   (or abort).

3. This fragment fails:

    struct Test {}

    circular_buffer<Test> a(2);
    a.push_back(Test());
    a.push_back(a[0]);

Instance of Test is overwritten (by construct())
and not destroyed in second push_back().

This may be problem for insert()s as well.

I am not sure whether solving this kind of problems
is worth of the increased complexity. I do not know
what Standard mandates for such a circumstances.

4. It may be useful to have circular_buffer<>
   constructor taking external buffer (e.g. static
   or on stack) and using it internally.

   (Feature has some similarity to std::streambuf.)

   External buffer could lead to lower heap
   fragmentation in apps.

5. Currently functions like insert/erase cannot use
   reverse iterators (similarly to standard
   containers).

   Some structures like LRU could find use for it.

----------------------------------------------

"Jan Gaspar" <jga_at_[hidden]> wrote ...

> > 3. cb_iterator: is the m_end value needed?
> >
> >    It can be computed using 'm_it == m_buff->m_last' in
> >    those few (~2) places it is needed and if eliminated,
> >    iterator will get smaller (by 30%) and simpler.
>
> Yes, the m_end member is needed. Suppose the circular_buffer is full. Then
> m_buff->m_first == m_buff->m_last. If there is no m_end variable how would
you
> recognize that the iterator points to the beginning or end?
>
a) on compilers I use sizeof(bool) == 4 so removing it would have impact

b) what about setting m_it == m_buff every time iterator gets to the end?:

  bool is_end() {
    return m_buff == m_it;
  }

Operator ++, --, >, +=, -=, == can do the check and if needed they may
fetch the m_buff->m_last.

Since m_buff is already in some registry the check should impact
performance too much.

> > 5. In cb_iterator::operator-(): result of the expression
> >    ' it < *this' can be saved and not computed second time.
>
> But it is not used second time.
>
My mistake.

> > 7. cb_iterator::operator!=(): it may be more efficient to code
> >    it as 'm_it != it.m_it ...' instead of !operator==().
> >    I do not know if compilers are allowed to change logical
> >    expression and if, how good they are in it.
>
> Maybe. But everyone uses it like this.
>
Everyone uses
  for (iter i = buff.begin(); i != buff.end(); ++i)

While only small help, it may have impact in innermost loops.

> > 8. cb_iterator::operator<(): the ASSERTS here are useless.
> >    Function compare() doesn't return anything else
> >    than -1/0/1 - I see it.
>
> Yes, they are useless. But
> 1) omitting them doesn't speed up the execution (in general)

Well, excerpt from MSVC 7 help:

void main(int p)
{
   switch(p){
      case 1:
         func1(1);
         break;
      case 2:
         func1(-1);
         break;
      default:
         __assume(0);
            // This tells the optimizer that the default
            // cannot be reached. As so it does not have to generate
            // the extra code to check that 'p' has a value
            // not represented by a case arm. This makes the switch
            // run faster.
   }
}

> 2) suppose if someone changes the compare() method implementation ... !!!!
>
Then the check should be within compare()

> 3) this code is clean, you should always provide the default option
>
IMHO not in this case. I struck my eyes.

However this is all unimportant detail.

> > 9. OTOH there are places where ASSERT can be inserted:
> >    - ensuring two iterators come from the same buffer
> >    - checking iterators are within valid range
> >    - checking type of iterators is the same (reverse / normal)
>
> circular_buffer is a STL compliant container - no STL container is doing
this.
>
STLport, newer Dinkumware and maybe even Metrowerks STL provides
DEBUG mode.

I may help you with this. It is however orthogonal to anything
else with the lib and can be added later into finished code.

> > 14. circular_buffer<>: set_capacity() is not exception safe:
> >     if uninitialized_copy() throws it will leak.
> >     This problem happens IMHO in many functions (e.g.
> >     in constructors).
> >
> >     Scope guard can be used to get basic exception safety.
>
> OK, I will try to fix it.
>
I think basic exception safety can be done without performance hit.
Higher level would require a lot of work, for example to protect
insert_n() interrupted in the middle.

> > 18. both circular_buffer<>::assign():
> >
> >             m_buff = m_alloc.allocate(capacity(), 0);
> > should be
> >             m_buff = allocate(n);
> >
>
> No, it is OK. capacity() will be always at least 1.
>
what about
  buff.assign(0, Test())
or
  buff.assign(x.begin(), x.begin()) ?

> > 23. It may be wortwile to check whether A. Alexandrescu's
> >     Mojo technique cannot be used within circular_buffer<>.
> >     (I have no idea about concrete applicaility here.)
>
> I have no idea what the Mojo technique is. Try to explore it.
>
Mojo is described in article
http://www.moderncppdesign.com/publications/cuj-02-2003.html.

Performance effect on STLport containers is described in
http://www.stlport.com/dcforum/DCForumID5/682.html.

> > 26. circular_buffer<>:: first insert(): some code from here
> >     can be shared throughout the library.
>
> I don't know exactly what you mean.
>
Uhh, nothing to share.

> > 33. circular_buffer<>::insert(Iter, Iter) may contain
> >     STATIC_ASSERT check that Iter iterator value is
> >     convertible to buffer main data type.
> >     Some other functions as well.
> >
> >     Iterator traits may be checked as well.
>
> I think, if the value won't be convertible the compilation fails anyway.
>
My point is that instead of ugly error from guts of STL you get more
readable error.

> > 37. Documentation: it would be nice to have documented
> >     precondition, postconditions, exceptions
> >     thrown etc. Maybe this info can be embedded into
> >     Doxygened text.
>
> What do you mean by precondition and postconditions. Give an example.
>
http://www.boost.org/libs/optional/doc/optional.html

S pozdravom,
/Pavel