Re: [boost] Dynamic Bitset Formal Review June 8-17

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-06-10 23:27:36

On Mon, 10 Jun 2002, Howard Hinnant wrote:
> >     // The following 2 classes make sure that the bitset
> >     // gets allocated in an exception safe manner
>
> While this is a very good design pattern, it is not clear to me how it
> is helping in this application.  But also it does no harm ... except:

Why, is there a simpler way in this case to ensure the exception safety?

> > class dyn_bitset : public detail::dyn_bitset_base<Block, Allocator>
>
> Why the public derivation?  This seems to unnecessarily expose
> dyn_bitset to casting to a private implementation base class.  In effect
> detail::dyn_bitset_base<Block, Allocator> has become part of the public
> interface.  Is that intended?

No, I think the public derivation was not intentional, just habitual :)

> > template <typename Block, typename Allocator>
>
> I'm not seeing the motivation for the Block template parameter.  Would
> not the implementation know the best type for Block?  Are there choices
> for Block the user might make which may not be appropriate?  Signed
> types come to mind pretty quickly.  Not sure if they would mess up the
> implementation, but I'm guessing they will.   Why not leave this
> decision to the implementor?

My thinking was that as a boost library, it will be used on many different
platforms. For some it may be better to have 64 bit blocks, others 32 bit
blocks. As a codewarrior library it would probably make more sense to not
have this parameter, since you know what platform it will be going on.

> No iterators!
>
> Part of the motivation for dyn_bitset (imho) is to give clients of
> vector<bool> a place to migrate to so that we can deprecate
> vector<bool>.  Therefore dyn_bitset must support the vector<bool>
> interface at least to a large extent, if not completely.  Having it also
> support the bitset interface is a good thing too.  I think both could
> use iterators, begin, end, rbegin, rend, etc.  dyn_bitset could also use
> the rest of the vector interface: insert, erase, front, back, etc.  I
> would drop append (neither bitset nor vector).  In short, I would start
> with the interface of std::vector<bool> and add to it as appropriate
> from std::bitset.

The problem with iterators over bits is that they are slow. It seems to me
like putting iterators in the bitset is just tempting users to actually
use them, when in most situations they shouldn't. If the user wants to
iterator over stuff, they probably should look to vector<char> or
something similar instead.

> References should remain stable after swap (still valid, just points to
> the other container).  That means that dyn_bitset::reference can't hold
> a pointer to the dyn_bitset it is referencing.

OK.

> Namespace scope swap seems to be missing.
>
> > reference(); // intentionally not implemented
>
> ?  I don't understand.  reference already has a constructor.  If you
> want to disable default construction of references (I agree a good
> thing), just don't declare it.

I suppose that was mainly for documentation purposes.

> Try out boost::compressed_pair to get rid of the storage for the
> allocator.  On those systems that implement empty base class
> optimization you reduce your overhead from 4 words to 3 (25%) for the
> common case of a stateless allocator.  This can be significant in
> vector<dyn_bitset<> >.
>
> append:  Although should be replace by insert, should also be redesigned

What's the rationale for replacing by insert? More flexibility?

> w.r.t. optimizing on iterator type.  Current design instantiates code
> for input iterators and forward iterators.  This decision can be made at
> compile time and instantiate one algorithm or the other instead of both.

The current design does make the decision at compile time... and should
result in the same code assuming the compiler does dead-code elimination,
which I think is fairly common, though I haven't checked this.

> Btw, I kind of like the name bitvector better than dyn_bitset (thinking
> bitvector/bitset).

With iterators I would agree that bitvector is better, but without
iterators I still prefer bitset, since the primary focus is on
representing a set.

> Just my .02, hope it helps.

Thanks!
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://www.osl.iu.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------