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

From: Dave Gomboc (dave_at_[hidden])
Date: 2003-07-21 17:31:10

> > > > 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?
> >
> > 30% is a lot.  Would it make sense to always allocate one extra element,
> > so that this equality can never occur?
>
> 1) This is is not true. The members of the iterator are:
> const Buff* m_buff;
> pointer m_it;
> bool m_end;
>
> At Windows based systems sizeof(m_buff) == 4, sizeof(m_it) == 4 and
sizeof(m_end)
> == 1. It is not 30%.

30% was the number given by another poster.  I merely referenced their
number.

On most 32-bit platforms, including Windows on x86, sizeof(structure with
those 3 fields only) is 12, not 9.  30% is actually somewhat generous,
because it slightly underestimates the relative space allocated due to the
presence of the bool.

> 2) Suppose you are storing elements of size 1000 bytes. By allocating one
more
> extra element ...

To me, this seems significantly less likely than storing elements of size 1,
2, 4, or 8 (values of small concrete types, or pointers to larger types).
Even if you are storing value types of 1000 bytes directly, if you're
allowing space for 1000 of those then the extra kilobyte is still not a big
deal.  I would expect the combination of large-sized type and low permitted
count to be infrequent, and implement accordingly.

However, should that expectation be incorrect, there is likely a way to
represent an empty circular buffer differently by using the value 0 in a
judicious manner somewhere in your code, so that when the equailty is being
tested and holds it is always intpretable as that the buffer is full.  By
such a mechanism the bool would still be avoidable, for the cost of a slight
increase in code complexity.

Dave