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

From: Gennaro Prota (gennaro_prota_at_[hidden])
Date: 2006-06-03 10:03:57

On Fri, 2 Jun 2006 17:03:11 -0500, "Bo Peng" <ben.bob_at_[hidden]>
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 suspect to me. 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);
    }

Please, let us know if this helped.

Cheers,
Gennaro.

--
Genny.