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

From: Gennaro Prota (gennaro_prota_at_[hidden])
Date: 2006-06-08 13:52:00

On Wed, 7 Jun 2006 14:36:15 -0500, "Bo Peng" <ben.bob_at_[hidden]>
wrote:

>> No, that is intentionally not possible. But you can construct the
>> dynamic_bitset object directly from a suitable iterator range (no need
>> to use an intermediate vector). Just to illustrate the point, this is
>> an example iterator based on boost::iterator_facade.
>
>I think I get the idea of this piece of code (after reading the
>iterator document), but it does not really fit my needs. If you are
>interested, I can explain to you the whole scenario:

Sure, I'm here to help, in as far as I can.

>
>In a large simulation program, I need to simulate successes at
>different rates, for many times. For example, I may need to simulate a
>sequence of 0/1 with probability [0.00001, 0.5, 0.003, 0.001] for
>10000 times. This 10000-times process may be repeated as well. Doing
>randUniform(0,1) < p 40000 times is very slow.
>
>I then build a class that wraps around a
>vector<dynamic_bitset<unsigned long> >, which, for example, has 4
>dynamic_bitset of length 10000.
>Since 0.5 and very small p are comon, I use special algorithms to
>handle them and store the results in this bit matrix. The results will
>be retrieved as size 4 vectors. The bit matrix has fixed size, and
>will be refreshed when needed.
>
>Efficiency needs to be improved in two parts:
>
>1. set random bits when p=0.5. This has been largely solved but I need
>to use a temporary vector to stored generated random number, and
>transfer them into the dynamic_bitset. Your iterator allows me to
>create a bitvector, but I basically need to write to an existing
>vector. A built-in block iterator would be helpful in this case.

You if can leave with the chance that from_block_range could be
removed in later version of the library then you can use that one.
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
b) it assumes the bitset size is a multiple of the block_width; for
instance, if on your platform block_width = 32, the bitset will
actually have (1 + [10000/32]) * 32 = 313 * 32 = 10016 bits. To be
safe (and avoid library asserts) you should first size the bitset to
10016, then resize it to 10000 *after* calling from_block_range.

A potentially slower alternative, with the same caveats about the
actual bitset size, but with no need for an intermediate vector in the
client code, would be:

 std::swap(succ_matrix[i], (your_bitset_type(it, it + 313)));
 // shrink succ_matrix[i] to 10000 elements

Differently from the from_block_range solution, this won't save you
from unnecessary dynamic allocations. Furthermore, due to an oversight
on our part, it's unlikely that the correct constructor will be picked
up for my_bitset_type(it, it + 313), though everything might work, for
instance, with VC 7.1. This will be fixed as soon as possible.

>
>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?

>The [cur] operation is slow since its location in dynamic_bitset needs
>to be calculated each time. It would be better if I can do something
>like:
>
>  vector<int> succ(4);
>  for(size_t i=0; i<4; ++i)
>    succ[i] = *(++succ_iterator[i]);
>
>where the location is stored in iterators and need not to be re-calculated.
>
>So, as you can see, I basically need two levels (bit and block) of
>iterators to access existing bitsets.

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. The reason why it
doesn't expose bit-level iterators is that they wouldn't integrate
with the standard library anyway (see the section about why
dynamic_bitset is not a container, in the docs). But given that
Jeremy's new iterator categories have been approved for TR1 I'm going
to implement them. *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.

If you reply to my questions above I can try giving further help.

Cheers,
--Gennaro.