std :: bitset如何比std :: vector <bool>更快？

Question

根据这个答案,海报期望std::bitset大小100k位比std::vector<bool>查询单个位时更快.这怎么可能？

如果std::bitset显然允许任意大小,他们甚至可能在实施方面有显着差异std::vector？

Answer 1

在Visual Studio 2010中显示,测量std::bitset是不一般的速度比std::vector<bool>.究竟是什么原因我不能说 - 只有bitset实现与std :: vector完全特化有很大不同.

std :: bitset通过a将对象的完整内容存储在对象中

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

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

数组,这使得大的bitset不适合放在堆栈上 - 这本身不是性能参数.

vector<bool> 没有遭遇堆栈问题,并且测试大小为1e6和1e7似乎在我的盒子里,在这里查询循环中的值实际上是向量的2倍.

好.我想通常的时间警告适用和YMMV,但这里是我用过的测试代码,任何人都应该自己尝试:

我的盒子上的输出是:

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

BitMap.cpp

#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;
  delta1=0;
  delta2=0;
  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;
}

BitMap.h

#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);

bs_loop.cpp

#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) {
    ++ext;
    for(size_t j=0, e=v.size(); j!=e; ++j) {
      if(v[j]) {
        --ext;
      }
      else {
        ++ext;
      }
    }
  }
}

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

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

编译器命令行:

/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- 
/errorReport:queue 

注意/ O2和缺失/GL(没有整个prg选项).

Answer 2

好吧,因为我是你的问题,所以我从这里得到了这个想法:

"...它包含bool并将它们作为单独的位(内部,比如,字符)存储在其内部表示中.这样做的一个结果是它不能只返回正常的bool及其运算符[]或其解除引用的迭代器[2]相反,它必须玩一个类似bool的帮助器"代理"类游戏,但绝对不是bool.不幸的是,这也意味着访问a vector<bool>的速度较慢,因为我们必须处理代理而不是直接指针和参考.

...

底线:如果您更关心速度而不是尺寸,则不应使用std::vector<bool>.相反,你应该通过使用std::vector<char>等等来破解这种优化,这是不幸的,但仍然是你能做到的最好的."

或者,正如我所建议的那样,如果您知道您的设备将获得的最大尺寸,请使用std::bitset.