CODEWITHSUNDEEP
c++vectorbitset
Michel
Michel

Reputation: 21

Putting output of the bitset member function count into a vector is slow

Here is a part of my C++ code where I have problems:

std::bitset<64>a;
std::bitset<64>b;
std::bitset<64>c;
int bit_count=0;
std::vector<int> vec(SIZE,0);
for (i=1;i<NUM;i++)
{
  // I do here some operations on a and b (a and b will have bits that are set)
  c=a^b;
  bit_count=(int) c.count(); // LINE 1
  vec[i]=bit_count; // LINE2 2
}

My problem is the following:

  1. if I comment LINE 1 and LINE 2 the code runs in approx. 109ms;
  2. if I only comment LINE2 the code runs approx. in 115 ms;
  3. if I comment LINE 1 and bit_count=0 the code runs approx 130 ms;
  4. if both lines (LINE 1 and 2) are not commented, the code runs in approx. 350 ms.

Why is the code slow when I use LINE1 and LINE2? I do not find any acceptable explanation.

Note that I also tried vec.push_back(bit_count), and it is also slow. I also tried different cast operations without success.

Upvotes: 2

Views: 108

Answers (1)

peterchen
peterchen

Reputation: 41126

In case 2, the compiler may not calculate bit_count completely, as it is never used (e.g. it might do the XOR but not the count)

In case 3, you have just the assignment

Only in case 4, the bit_count (whcih is rather expensive) needs to execute.

(edit to clarify: if you never use vec, it might still throw away the entire loop. It doesn't have to, though)

additional information:

The compiler is requried to preserve only observable behavior, defined as

  • Access to volatile objects
  • input and output (including files)
  • calling into "unknown" code (e.g. external libraries)

The standard verbiage is of course more complicated,this question has some additional discussion.

I always found it an interesting exercise to watch your compiler. Most allow to enable an disassembly output, with an inquring mind and an hour of "introduction to my processor's assembly" undere the belt, little exercises like that can be very insightful

Upvotes: 2

Related Questions