Martin Ba Martin Ba - 9 months ago 48
C++ Question

How can std::bitset be faster than std::vector<bool>?

According to this answer the poster expects a

of size 100k bits to be faster than a
when querying individual bits. How can this be possible?

How could they even differ significantly in their implementation, if
apparently allows for arbitrary sizes just like

Answer Source

Measurements on Visual Studio 2010 show that std::bitset is not generally faster than std::vector<bool>. What the exact reason for this is I cannot say -- only that bitset is implemented significantly different from the std::vector full specialization.

std::bitset stores it's full content in the object via a

template<size_t _Bits>
    class bitset .....

    _Ty _Array[_Words + 1]; // the set of bits

array and that makes large bitset unsuitable to be put on the stack -- which isn't a performance argument per se.

vector<bool> doesn't suffer from the stack problem, and testing with a size of 1e6 and 1e7 it seems that on my box here querying values in a loop is actually 2x faster with a vector.

Well. I guess the usual timing caveats apply and YMMV, but here's the test code I used should anyone care to try himself:

The output on my box is:

vector<bool> loop with a size of 10000000 and 10 iterations*n: 11187 ms
bitset<10000000> loop with 10 iterations*n: 22719 ms
Press any key to continue . . .


#include "stdafx.h"
#include "BitMap.h"

using namespace std;

// Global var to prevent optimizer from messing things up
volatile size_t ext;

volatile clock_t t1;
volatile clock_t t2;
double delta1;
double delta2;

int main(int argc, _TCHAR* argv[])
  ext = 1;
  printf("%d\n", ext);

  vb_t *const vec = new vb_t(bssz);
  bs_t *const bits = new bs_t(); // must put large bitset on heap

  const int iter = 10;
  for(int o=0; o<5; ++o) {
    t1 = clock();
    for(int i=0; i!=5; ++i)
      bs_loop(iter, *vec);
    t2 = clock();
    delta1 += t2-t1;
    t1 = clock();
    for(int i=0; i!=5; ++i)
      bs_loop(iter, *bits);
    t2 = clock();
    delta2 += t2-t1;

  delta1 /= CLOCKS_PER_SEC;
  delta2 /= CLOCKS_PER_SEC;
  delta1 *= 1000;
  delta2 *= 1000;

  cout << "vector<bool> loop with a size of " << bssz << " and " << iter << " iterations*n: " << delta1 << " ms\n";
  cout << "bitset<" << bssz << "> loop with " << iter << " iterations*n: " << delta2 << " ms\n";

  printf("%d\n", ext);
  delete vec;
  delete bits;
  return 0;


#pragma once
#include <vector>
#include <bitset>

extern volatile size_t ext;
const size_t bssz = size_t(1e7); // 1e7 ca 10m

using namespace std; // Test code, using here is OK.
typedef vector<bool> vb_t;
typedef bitset<bssz> bs_t;

template<class COLL>
void bs_loop(const int iterations, COLL const& v);


#include "stdafx.h"
#include "BitMap.h"

template<class COLL>
void bs_loop(const int iterations, COLL const& v)
  ext = sizeof(COLL);
  for(size_t i=0; i!=iterations; ++i) {
    for(size_t j=0, e=v.size(); j!=e; ++j) {
      if(v[j]) {
      else {

void bs_loop(const int iterations, vb_t const& v);

void bs_loop(const int iterations, bs_t const& v);

Compiler command line:

/Zi /nologo /W3 /WX- /O2 /Oi /Oy- /D "WIN32" /D "NDEBUG"
/D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /Gm- /EHsc /GS /Gy 
/fp:precise /Zc:wchar_t /Zc:forScope /Yu"StdAfx.h" /Fp"Release\BitMap.pch" 
/Fa"Release\" /Fo"Release\" /Fd"Release\vc100.pdb" /Gd /analyze- 

note the /O2 and the missing /GL (no whole prg opt).