Re: [Boost-users] set() of dynamic_bitset is too slow.

From: Bo Peng (ben.bob_at_[hidden])
Date: 2006-06-08 23:09:42

> However, keep in mind that a) it doesn't resize the bitset: it's your
> responsibility to ensure that you won't copy "too many blocks" into it

Now, I am writing num_blocks()-1 blocks, and treat the last block
separately. I think I can just use bit sizes that are multiples of
block size, although the last few bits will not be used. In this way,
the algorithm will be cleaner and faster, and boost/dynamic_bitset
will not complain.

> >2. retrieve succ from each column of this matrix. Curently, I am doing
> >something like
> >
> >  vector<int> succ(4);
> > ....
> >  for(size_t i=0; i<4; ++i)
> >    succ[i] = succ_matrix[i][cur];
> >  // process succ
> >  cur ++
> >  // get another row
> >
>
> I'm confused by this. Does succ_matrix[i][cur] yields a bool or an
> int? And in the latter case, what value does it actually return?

I was using dynamic_bitset to get results (succ) but the performance
was bad. vector<int> is much faster. I can afford to use int since
succ is usually small.

> The reason why dynamic_bitset does not expose block-level iterators is
> that I see blocks as an implementation detail. I'm not even convinced
> there should be a template parameter for them.

I have checked my random number generator. It will produce full range
of  integer values (0 - 2^32-1). As a result, I use unsigned long as
the template parameter of dynamic_bitset. At least for my usage, this
template parameter is useful.

>  *Nonetheless* incrementing/decrementing iterators
> still requires some computation. Maybe you are thinking that such
> iterators could be implemented by storing a pointer or reference to a
> bitset and an index, but would not be conforming.

You mean *(++ptr) will be as slow as succ[++idx]? I would be really
disappointed.

Bo