|
|
Boost : |
From: Jan Gaspar (jga_at_[hidden])
Date: 2003-07-22 13:27:04
Pavel Vozenilek wrote:
> Hello Jan,
>
> Few more comments + answers.
>
> 1. Documentation: can circular_buffer<> be used as
> container for stack/queue/priority_queue?
Yes, it can be. But I think, it is not necessary to mention it in the
documentation explicitly. Rather it is more important to mention that everyone is
encouraged to create an adaptor of this container (whatever he/she likes not only
stack or queue).
>
>
> 2. When BOOST_NO_EXCEPTION is defined, library
> shouldn't throw but call function
> throw_exception() from throw_exception.hpp
> (or abort).
>
OK, I will try to follow it.
>
> 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().
>
I don't understand this. IMHO there will be 2 copies of Test(). Nothing should be
destroyed in the second push_back(). I think, everything is OK.
>
> 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.
>
Maybe. But it will complicate things, because couldn't delete this buffer and I
will have to treat this case specially. So, maybe later.
>
> 5. Currently functions like insert/erase cannot use
> reverse iterators (similarly to standard
> containers).
>
> Some structures like LRU could find use for it.
>
I don't want to bother with this.
>
> ----------------------------------------------
>
> "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.
Should or shouldn't impact performance? What about setting m_it to 0 ?
>
>
> > > 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.
>
OK
>
> > > 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.
>
OK
>
> > > 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.
>
I will appreciate this.
>
> > > 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()) ?
>
Look at the code again:
if (n > capacity()) {
destroy();
m_capacity = n;
m_buff = m_alloc.allocate(capacity(), 0);
m_end = m_buff + capacity();
.....
The expresion in the condition will be false (even if capacity() == 0).
>
> > > 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.
>
I will look at it.
>
> > > 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.
OK, I will try.
>
>
> > > 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
>
OK
>
> S pozdravom,
> /Pavel
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Jano
-- Jan Gaspar | jga_at_[hidden] Whitestein Technologies | www.whitestein.com Panenska 28 | SK-81103 Bratislava | Slovak Republic Tel +421(2)5930-0735 | Fax +421(2)5443-5512
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk