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

From: Gennaro Prota (gennaro_prota_at_[hidden])
Date: 2006-06-03 08:59:59

Bo Peng wrote:
> Dear list,
> 
> I am using dynamic_bitset to store a sequence of random 0/1. The
> program generates repeatedly 32bit random numbers and assign the
> result to a dynamic_bitset.
> 
> 				for(UINT i=0; i < m_N; ++i)
> 				{
> 					if(bit == block)			  // generate a block
> 					{
> 						ri = rng().randInt(m_max);
> 						bit = 0;
> 					}
> 					if((ri >> bit) & 0x1)
> 						succ.set(i);
> 					bit++;
> 			    }
> When I profile this program, I surprisingly find out that succ.set(i)
> uses >50% of the execution time. Is there anyway I can assign block by
> block to dynamic_bitset, or assign sequentially so the position of i
> does not have to be calculated each time?

Hi,

you code looks very suspect. Are you aware it actually yields m_N bits 
rather than m_N blocks? Also, I'll assume the dynamic_bitset is sized in 
advance. Sticking to the problem, there are many alternative codings; in 
particular you could use the iterator-based version of append, after 
creating a little iterator class for the random integers (please, ignore 
from_block_range() :-)). If that's not suitable for you might try this:

     typedef UINT block_type;
     boost::dynamic_bitset<block_type> succ; /* no resizing needed */

     // (assuming m_N is a multiple of the UINT width, i.e. 32)
     for(UINT i=1; i <= m_N / (block + 1); ++i)
     {
         block_type b = /*random...*/;
         succ.append(b);
     }

Let us know if it worked for you.

Cheers,
Gennaro.