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

Question

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

如果std::bitset允许任意大小，就像std::vector一样，它们如何在实现上有显著差异呢？

- Martin Ba

---

当然，你和前一个发帖者都应该进行一些分析。 :-) - C. K. Young

bitset是基于大小的模板，但该大小必须在编译时固定，而vector<bool>可以在运行时调整大小。 - Roger Pate

@Roger - 我知道这一点。问题是在大小被固定后，它们在访问时会有什么不同？（当使用[]访问元素时，存储大小并不重要，因为大小不会在那里被检查。） - Martin Ba

正如我在下面评论中所说，它们在访问方面并没有显著的区别。我是在回应“允许任意大小，就像std::vector一样”的说法，因为与大小相关的方面并不完全像vector那样。 :) - Roger Pate

Answer 1

据Visual Studio 2010的测量结果显示，std::bitset通常不比std::vector<bool>更快。我无法确定确切的原因——只知道bitset与vector完全特化的实现方式有明显差异。

std::bitset通过位存储其全部内容。

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

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

由于数组的大小，较大的位集不适合放在堆栈中，这并不是性能上的问题。

vector<bool>不受堆栈问题的影响，在测试大小为1e6和1e7时，在我的计算机上通过循环查询值实际上比使用位集快2倍。

当然，通常的时间注意事项可能会有所不同，但如果有人想尝试，这里是我使用的测试代码：

在我的计算机上输出结果为：

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 . . .

位图.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（无整个程序优化）。

- Martin Ba

---

需要记住的一件事是，代理对象必须用于l-values但不用于r-values。由于r-values是只读的，因此[]运算符可以返回一个bool。因此，您可能希望向测试中添加一些位设置，以使其具有良好的覆盖范围。 - Evan Teran

另外，我真的不理解你在那个测试中的 sizeof(COLL) 和其他 ext 操作，它们对我来说通常没有意义。 - Evan Teran

@Evan：volatile 操作只是为了让优化器不会完全搞砸事情。它们不必有意义，只需要存在即可。（在我看来，它们不会影响任何时间。） - Martin Ba

@Evan：我恐怕不理解你所称的“代理对象”和“添加一些位设置”的含义？ - Martin Ba

当你执行类似 bs[i] = true; 的操作时，operator[] 不能返回一个 bool&，因为事实上它们并不是以 bool 数组的形式存储的。所以它必须返回一个小对象，其中包括定义了 operator= 的适当位在容器中翻转的内容。而对于像 bool x = bs[i]; 这样的情况，情况就不同了，它可以简单地返回一个 bool。因此，在实现中，bitset 或 vector<bool> 的读取与写入代码非常不同。因此，您需要测试两者才能完整。 - Evan Teran

@Evan：最初引起这个问题的问题只涉及读取性能，这就是为什么在示例中我没有计时写入的原因。此外，无论是bitset还是vector-bool都需要实现这样的代理，因此我无法看出这会影响性能。（我同意公平比较应该测量写入性能--尽管我希望它最多相等。请随意这样做并发布您的结果 :-) - Martin Ba

Answer 2

好的，由于我是你基于这个问题的助手，这里是我得到这个想法的来源：

“……它将布尔值打包并将它们作为单独的位（在内部表示中，比如说char）存储。这种做法的一个后果是，它不能仅仅从它的operator[]或者解引用迭代器[2]中返回一个普通的bool&；相反，它必须使用一个帮助器“代理”类来进行操作，该类与bool类似，但绝对不是bool。不幸的是，这也意味着访问vector<bool>会更慢，因为我们必须处理代理而不是直接指针和引用。

……”

总之：如果你更关心速度而不是大小，那么你不应该使用std::vector<bool>。相反，你应该通过使用std::vector<char>或类似的东西来规避这个优化，虽然这很不幸，但这仍然是你能做的最好的事情。”

或者，正如我建议的那样，如果你知道你的集合将达到的最大大小，使用std::bitset。

- Steve M

---

另一个选择是Boost的dynamic_bitset，如果有价值的话。 - Stuart Golodetz

避免使用vector<bool>是一个好的建议，适用于一般情况，甚至是具有100k或1M项的一般情况，但是，与任何大小/速度权衡一样，这种方式并不总是更快。 （Sutter甚至通过提到权衡来暗示这一点。）然而，它并没有将vector<bool>与bitset进行比较，在那里任何性能差异都应该是可以忽略不计的或者是实现上的问题。 - Roger Pate

Steve - 谢谢你的回答，但是它并没有回答这里的问题，即比较 std::bitset 和 std::vector-bool！我知道 std::vector-bool 的特殊实现（特化），但是根据 std::bitset 的文档，它们似乎“几乎完全相同”——例如，它们都定义了一个内部帮助程序“reference”，以解决您无法将单个位作为指针或引用访问的问题。因此，我不明白它们在速度方面如何不同。 - Martin Ba

我知道这是一篇旧答案，但由于它排名第二，并且我可能不是唯一从谷歌进入此处的人，我想澄清一个可能令人困惑的问题：我所知的所有std::bitset<N>当前实现大约使用N/CHAR_BIT字节来存储N个位。因此，它们存储数据的方式与典型的std::vector<bool>实现方式基本相同（虽然标准对这两者都没有要求）。 - MikeMB

Answer 3

说实话，我认为bitset更适合在栈上使用而不是堆上。此外，这两个方法并不冲突，因为一个优雅的解决方案可能是这样的：

vector< bitset<64> > v(100000) //or whatever...

这里有一个有趣的测试，可以将这两个进行比较：

vector<unsigned char> v1(1000000) //8 bits to manage them manually
vector< bitset<8> >   v2(1000000) //8 bits managed by bitset

此外，为了补充这里的答案并提醒编译器在性能方面有很大关系，这里进行了一个简单的测试：

• VS2012
• mingw/g++ 4.7.0
• Ubuntu上的g++ 4.8.2

(但所有这些测试都有点棘手，可能只能给我们提供粗略的总体比较。最终要做的是对项目进行分析.)

• 使用默认的Release进行的VS2012编译。
• 使用-O2进行的g++编译。
• 使用-O2 -std=c++11进行的g++编译。

注意:

用大小为10^7的数据集：

• VS2012在运行时崩溃。(所以我可以假设它们的内存管理与g++不同)
• g++则没有问题。
• g++11在test2()中会出现时间=0的问题，我打印了一些值来触发代码执行。 (我认为这是编译器的优化)

我还包括了对象构造函数和析构函数的开销时间。

下面是简单的测试代码：

#include <iostream>
#include <vector>
#include <bitset>
#include <time.h>

using namespace std;

#define SIZE1 1000000000 //10e9
//#define SIZE2 10000000   //10e7 VS2012 crash at runtime, g++ OK
#define SIZE2 1000000 //10e6

void test1()
{
    register bool j;
    clock_t t1,t2;
    cout.precision(10);

    t1=clock();
    vector<bool> *v = new vector<bool>(SIZE1);
    for(register long int i=0; i<SIZE1;i++)
        (*v)[i] = i%2 == 0? true :false;

    for(register long int i=0; i<SIZE1;i++)
        j=(*v)[i];

    delete v;
    t2=clock();
    cout << "vector speed = " << (t2-t1) / (float) CLOCKS_PER_SEC << " (" << t2 << "," << t1 << ")" << endl;

    t1=clock();
    bitset<SIZE1> *b = new bitset<SIZE1>();
    for(register long int i=0; i<SIZE1;i++)
        (*b)[i] = i%2 == 0? true :false;
    for(register long int i=0; i<SIZE1;i++)
        j=(*b)[i];

    delete b;
    t2=clock();
    cout << "bitset speed = " << (t2-t1) / (float) CLOCKS_PER_SEC << " (" << t2 << "," << t1 << ")" << endl;
}

void test2()
{
    register bool j;
    clock_t t1,t2;
    cout.precision(10);

    t1=clock();
    vector<bool> v(SIZE2);
    for(register int k=0; k<SIZE1/SIZE2; k++)
        for(register long int i=0; i<SIZE2;i++)
            (v)[i] = i%2 == 0? true :false;

    for(register int k=0; k<SIZE1/SIZE2; k++)
        for(register long int i=0; i<SIZE2;i++)
            j=(v)[i];

    t2=clock();
    cout << "vector speed = " << (t2-t1) / (float) CLOCKS_PER_SEC << " (" << t2 << "," << t1 << ")" << endl;
    cout << "v[1], v[2] " <<  (int) v[1] << ", "<< (int)v[2] << endl;

    t1=clock();
    bitset<SIZE2> b;
    for(register int k=0; k<SIZE1/SIZE2; k++)
        for(register long int i=0; i<SIZE2;i++)
            (b)[i] = i%2 == 0? true :false;

    for(register int k=0; k<SIZE1/SIZE2; k++)
        for(register long int i=0; i<SIZE2;i++)
            j=(b)[i];

    t2=clock();
    cout << "bitset speed = " << (t2-t1) / (float) CLOCKS_PER_SEC << " (" << t2 << "," << t1 << ")" << endl;
    cout << "b[1], b[2] " <<  (int) b[1] << ", "<< (int)b[2] << endl;
}


int main(int argc, char* argv[])
{
    test1();
    test2();


    return 0;
}

VS2012输出：

vector speed = 3.105000019 (3105,0)
bitset speed = 10.44400024 (13551,3107)
vector speed = 3.987999916 (17542,13554)
v[1], v[2] 0, 1
bitset speed = 9.772999763 (27318,17545)
b[1], b[2] 0, 1

mingw/g++输出-O2：

vector speed = 1.519 (1520,1)
bitset speed = 1.647 (3168,1521)
vector speed = 1.383999944 (4554,3170)
v[1], v[2] 0, 1
bitset speed = 1.610000014 (6166,4556)
b[1], b[2] 0, 1

mingw/g++ 输出 -O2 -std=c++11:

vector speed = 1.528 (1529,1)
bitset speed = 1.685 (3215,1530)
vector speed = 1.409999967 (4626,3216)
v[1], v[2] 0, 1
bitset speed = 1.763000011 (6392,4629)
b[1], b[2] 0, 1

g++ 4.8.2 输出 -O2:

vector speed = 1.561391 (1564139,2748)
bitset speed = 1.681818 (3246051,1564233)
vector speed = 1.487877011 (4733975,3246098)
v[1], v[2] 0, 1
bitset speed = 1.685297012 (6419328,4734031)
b[1], b[2] 0, 1

g++ 4.8.2 输出 -O2 -std=c++11:

vector speed = 1.561391 (1564139,2748)
bitset speed = 1.681818 (3246051,1564233)
vector speed = 1.487877011 (4733975,3246098)
v[1], v[2] 0, 1
bitset speed = 1.685297012 (6419328,4734031)
b[1], b[2] 0, 1

结论：

粗略来看，对于这些用例，矢量似乎更快。

我没有运行多个实例并平均结果，但大体上数值总是相同的。

关于VS的注释：我认为它使用了与gcc不同的内存管理机制，在这些用例中生成的代码似乎更慢。

- Raffaello

Answer 4

以下是我对从/插入大小为100K、1M和5M的bitset<>和vector<bool>中的3亿个元素进行访问/插入的非科学基准测试。编译器是64位Linux机器（Core i7）上的GCC 4.8.2：

优化后（编译器标志：-O2 -std=c++11）：

[estan@pyret bitset_vs_vector]$ ./bitset_vs_vector 
bitset<100000> (3 billion accesses/inserts): 132.424 ms 
vector<bool>(100000) (3 billion accesses/inserts): 270.577 ms

bitset<1000000> (3 billion accesses/inserts): 67.752 ms 
vector<bool>(1000000) (3 billion accesses/inserts): 268.193 ms

bitset<5000000> (3 billion accesses/inserts): 67.426 ms 
vector<bool>(5000000) (3 billion accesses/inserts): 267.566 ms

没有优化（编译器标志：-std=c++11）：

[estan@pyret bitset_vs_vector]$ make
g++ -std=c++11 -o bitset_vs_vector *.cpp
[estan@pyret bitset_vs_vector]$ ./bitset_vs_vector 
bitset<100000> (3 billion accesses/inserts): 1900.13 ms 
vector<bool>(100000) (3 billion accesses/inserts): 1784.76 ms

bitset<1000000> (3 billion accesses/inserts): 1825.09 ms 
vector<bool>(1000000) (3 billion accesses/inserts): 1768.03 ms

bitset<5000000> (3 billion accesses/inserts): 1846.73 ms 
vector<bool>(5000000) (3 billion accesses/inserts): 1763.48 ms

在这些条件下，当代码被优化时，bitset比vector更快，而当没有优化时，vector实际上略微领先。

话虽如此，如果您的代码时间很关键，最好自己进行基准测试，因为我怀疑这些数字高度依赖于编译器/环境。

基准测试代码：

#include <iostream>
#include <functional>
#include <bitset>
#include <vector>
#include <ctime>

// Performs N access/insert on container.
template<class T>
void access_and_insert(T &container, int N)
{
    const std::size_t size = container.size();
    for (int i = 0; i < N; ++i) {
        bool v = container[i % size];
        container[i % size] = true;
    }
}

// Measure the time in milliseconds required to call f.
double measure(std::function<void (void)> f)
{
    clock_t start = std::clock();
    f();
    return 1000.0 * (std::clock() - start)/CLOCKS_PER_SEC;
}

int main (void)
{
    // Benchmark with 100K elements.
    std::bitset<100000> bitset100K;
    std::vector<bool> vector100K(100000);
    std::cout << "bitset<100000> (3 billion accesses/inserts): ";
    std::cout << measure([&]() { access_and_insert(bitset100K, 3E7); }) << " ms " << std::endl;
    std::cout << "vector<bool>(100000) (3 billion accesses/inserts): ";
    std::cout << measure([&]() { access_and_insert(vector100K, 3E7); }) << " ms" << std::endl;
    std::cout << std::endl;

    // Benchmark with 1M elements.
    std::bitset<1000000> bitset1M;
    std::vector<bool> vector1M(1000000);
    std::cout << "bitset<1000000> (3 billion accesses/inserts): ";
    std::cout << measure([&]() { access_and_insert(bitset1M, 3E7); }) << " ms " << std::endl;
    std::cout << "vector<bool>(1000000) (3 billion accesses/inserts): ";
    std::cout << measure([&]() { access_and_insert(vector1M, 3E7); }) << " ms" << std::endl;
    std::cout << std::endl;

    // Benchmark with 5M elements.
    std::bitset<5000000> bitset5M;
    std::vector<bool> vector5M(5000000);
    std::cout << "bitset<5000000> (3 billion accesses/inserts): ";
    std::cout << measure([&]() { access_and_insert(bitset5M, 3E7); }) << " ms " << std::endl;
    std::cout << "vector<bool>(5000000) (3 billion accesses/inserts): ";
    std::cout << measure([&]() { access_and_insert(vector5M, 3E7); }) << " ms" << std::endl;

    return 0;
}

- estan

---

咳咳，你确定你正在测量正确的事情吗？一个有十倍条目的位集/向量不应该比原来快两倍。 - stefan

缓存可能变热了吗？上面的代码就是我运行以获取那些数字的确切代码。无论如何，正如我所说：不科学 :) - estan

好的，你正在测试的代码在优化构建中几乎是一个无操作（特别是读取部分！）。那就是你正在测量的唯一事物。不冒犯，但我认为它确实远离科学。非常不科学，以至于我会说毫无用处。 - stefan

Answer 5

向量使用迭代器访问其元素，这些迭代器不能是bool*的简单typedef，这使得它比位集慢，因为位集不提供迭代器。另一个使它快速的因素是它的大小在编译时已知，因此它不会使用new进行分配，而这比堆栈分配更慢。只是一些随机的想法。

- Armen Tsirunyan

---

一个向量也可以使用索引，但是对于这两个类的基本操作（即使使用迭代器），都是相同的。 - Roger Pate

Answer 6

此外，请注意 vector<bool> 是 vector 模板的一种特化，其实现方式与您想象的可能大不相同。

- Marcin

---

我相信原帖作者已经了解这一点，而这种知识也正是他为什么会想知道为什么它比位集慢的原因。但我可能错了。 - Armen Tsirunyan

考虑到vector<bool>的非标准行为，您可能根本不应该使用它... http://en.wikipedia.org/wiki/Vector_%28C%2B%2B%29#vector.3Cbool.3E_specialization - Joe