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

On Wed, 7 Jun 2006 14:36:15 -0500, "Bo Peng" 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, 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.