Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++11 vector<bool> performance issue (with code example)

Tags:

I notice that vector is much slower than bool array when running the following code.

int main()  {     int count = 0;     int n = 1500000;     // slower with c++ vector<bool>     /*vector<bool> isPrime;     isPrime.reserve(n);     isPrime.assign(n, true);     */     // faster with bool array      bool* isPrime = new bool[n];      for (int i = 0; i < n; ++i)         isPrime[i] = true;       for (int i = 2; i< n; ++i) {         if (isPrime[i])             count++;         for (int j =2; i*j < n; ++j )             isPrime[i*j] = false;     }      cout <<  count << endl;     return 0; } 

Is there some way that I can do to make vector<bool> faster ? Btw, both std::vector::push_back and std::vector::emplace_back are even slower than std::vector::assign.

like image 637
guoqing Avatar asked Apr 29 '16 07:04

guoqing


People also ask

Is vector bool slow?

Indexing individual bools in a vector<bool> is slow.

Is Bitset faster than vector bool?

As bitset stores the same information in compressed manner the operation on bitset are faster than that of array and vector.

What is a bool vector?

The vector<bool> class is a partial specialization of vector for elements of type bool . It has an allocator for the underlying type that's used by the specialization, which provides space optimization by storing one bool value per bit.


1 Answers

std::vector<bool> can have various performance issues (e.g. take a look at https://isocpp.org/blog/2012/11/on-vectorbool).

In general you can:

  • use std::vector<std::uint8_t> instead of std::vector<bool> (give a try to std::valarray<bool> also).

    This requires more memory and is less cache-friendly but there isn't a overhead (in the form of bit manipulation) to access a single value, so there are situations in which it works better (after all it's just like your array of bool but without the nuisance of memory management)

  • use std::bitset if you know at compile time how large your boolean array is going to be (or if you can at least establish a reasonable upper bound)
  • if Boost is an option try boost::dynamic_bitset (the size can be specified at runtime)

But for speed optimizations you have to test...

With your specific example I can confirm a performance difference only when optimizations are turned off (of course this isn't the way to go).

Some tests with g++ v4.8.3 and clang++ v3.4.5 on an Intel Xeon system (-O3 optimization level) give a different picture:

                    time (ms)                  G++      CLANG++ array of bool    3103     3010 vector<bool>     2835     2420    // not bad! vector<char>     3136     3031    // same as array of bool bitset           2742     2388    // marginally better 

(time elapsed for 100 runs of the code in the answer)

std::vector<bool> doesn't look so bad (source code here).

like image 186
manlio Avatar answered Oct 13 '22 04:10

manlio