The efficience of the bitset?

[remlostime]

Now, i define the following variables:
bitset<32> a, b;
int c, d;

and I have give some value to a, b, c, d, and if i compare (a == b),
is it like the integer compare like (c == d), or
it just do a loop 0 to 31 to compare if (a == b) and what is the
efficience compared with (c == d), if slow? is it
O(n) or just a little slower than O(1)?

 

[Reetesh Mukul]

Now, i define the following variables:
bitset<32> a, b;
int c, d;

and I have give some value to a, b, c, d, and if i compare (a == b),
is it like the integer compare like (c == d), or
it just do a loop 0 to 31 to compare if (a == b) and what is the
efficience compared with (c == d), if slow? is it
O(n) or just a little slower than O(1)?

Just a little slower than O(1), as bitset uses word ( int or size_t )
arrays. However I am not sure, whether standards says anything
regarding complexity order of bitset routines or not. Moreover my
answer is based on gcc compiler.

With Regards,
Reetesh Mukul

 

[Juha Nieminen]

Now, i define the following variables:
bitset<32> a, b;
int c, d;

and I have give some value to a, b, c, d, and if i compare (a == b),
is it like the integer compare like (c == d), or
it just do a loop 0 to 31 to compare if (a == b) and what is the
efficience compared with (c == d), if slow? is it
O(n) or just a little slower than O(1)?

Not surprisingly the C++ standard doesn't specify how bitset is
internally implemented. However, most implementations (or, more
precisely, at least the gcc implementation) are very efficient and will
perform things like comparisons and bit counting as fast as they can.

(The bit counting of the gcc bitset is actually incredibly fast. Even
with really large bitsets it takes, in my computer, an average of 1
clock cycle per bit to count all the set bits. That's fast.)

 

[Gennaro Prota]

(The bit counting of the gcc bitset is actually incredibly fast. Even
with really large bitsets it takes, in my computer, an average of 1
clock cycle per bit to count all the set bits. That's fast.)

In 2003, libstdc++ switched from the table-based SGI implementation to
using builtins. I'd be curious to know how does dynamic_bitset<
unsigned long >::count() compares, on your machine; I'd expect it to
be close to the old libstdc++ (at least if you have CHAR_BIT == 8 and
no padding bits in unsigned longs ).

 

[Juha Nieminen]

In 2003, libstdc++ switched from the table-based SGI implementation to
using builtins. I'd be curious to know how does dynamic_bitset< unsigned
long >::count() compares, on your machine; I'd expect it to be close to
the old libstdc++ (at least if you have CHAR_BIT == 8 and no padding
bits in unsigned longs ).

My computer is a 3.4GHz Pentium4, and I'm using gcc 4.1.2 on a linux
system. I created a bitset with 2100000000 elements, with approximately
10% of the bits set (more precisely, discarding all the even numbers,
all the primes between 2 and 4200000000 are set as a set bit; the total
amount of set bits is 198996103).
I compiled the program with "-O3 -march=pentium4".

std::bitset::count() took approximately 590 ms.
boost::dynamic_bitset::count() took approximately 250 ms.

The latter seems to be significantly faster.

If my calculations are correct, this means that the former uses in
average approximately 0.95 clock cycles per bit, while the latter uses
in average only 0.4 clock cycles per bit.

That's *fast* bit counting...

 

[Gennaro Prota]

My computer is a 3.4GHz Pentium4, and I'm using gcc 4.1.2 on a linux
system. I created a bitset with 2100000000 elements, with approximately
10% of the bits set (more precisely, discarding all the even numbers,
all the primes between 2 and 4200000000 are set as a set bit; the total
amount of set bits is 198996103).
I compiled the program with "-O3 -march=pentium4".

std::bitset::count() took approximately 590 ms.
boost::dynamic_bitset::count() took approximately 250 ms.

The latter seems to be significantly faster.

If my calculations are correct, this means that the former uses in
average approximately 0.95 clock cycles per bit, while the latter uses
in average only 0.4 clock cycles per bit.

That's *fast* bit counting...

And that's nice to hear for me Re-implementing count() was the
first thing I did on dynamic_bitset. If that doesn't bother you, you
might try another benchmark with find_first/find_next; in this case
libstdc++ and dynamic_bitset use completely different techniques. And
I have to say that, regardless of performance, I was quite happy of
how I implemented them without having built-ins at disposal (and
without a lookup table, either).