代码之家 › 专栏 › 技术社区 › Martin Ba

STD::BITSET比STD::向量< BOOL >

c++

Martin Ba · 技术社区 · 15 年前

根据 this answer 海报希望 std::bitset 大小为100K位,比 std::vector<bool> 查询单个位时。这怎么可能?

如果 STD::比特集 显然,允许任意尺寸,就像 std::vector ?

6 回复 | 直到 15 年前

Martin Ba 15 年前

Visual Studio 2010的测量结果表明 std::bitset 是不通常比 std::vector<bool> . 确切的原因是,我不能说,只有比特集与STD::向量完全专门化实现了显著的不同。

STD::比特集通过一个对象将它的全部内容存储在对象中

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

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

数组,这使得大的位集不适合放在堆栈上——这本身不是一个性能参数。

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

位图.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;
}

位图.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);

循环.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选项)。

Steve M 15 年前

既然我是你提出这个问题的依据, here's where I got that idea from :

_它将bools打包,并将其作为单个位(例如chars)存储在其内部表示中。这样做的一个后果是,它不能只从其运算符[]或其未引用的迭代器[2]返回正常的bool&值;相反,它必须使用类似bool但绝对不是bool的助手“proxy”类进行游戏。不幸的是,这也意味着 vector<bool> 更慢,因为我们必须处理代理而不是直接指针和引用。

艾斯

底线:如果你更关心速度而不是尺寸,你不应该使用 std::vector<bool> . 相反,您应该使用 std::vector<char> 或者类似的,这是不幸的,但仍然是你能做的最好的。”

或者,正如我建议的那样,如果你知道你的套装能达到的最大尺寸,使用 std::bitset 。

Raffaello 11 年前

老实说,我认为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

(但所有这些测试都有点棘手,可能只给我们提供了直接比较的大致概念。分析项目,这是最后唯一要做的事情。)

VS2012在版本中编译(提供了默认版本)。
用-o2编译的G++
G+ + -O2- STD=C++11

注:

尺寸10^7:

VS2012运行时崩溃。(所以我可以假设内存管理与G++不同)
G++没问题。
g++11在test2()报告time=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

MIW/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.82输出-O2-STD= C++ 11:

矢量速度=1.561391(15641392748)
位集速度=1.681818(32460511564233)
矢量速度=1.487877011(47339753246098)
V[1],V[2]0,1
位集速度=1.685297012(64193284734031)
B[1],B[2]0,1

结论:

对于这些用例,作为一个粗略的概念向量似乎更快。

我不运行多个距离并平均结果,但或多或少的值总是相同的。

关于vs的注释 :我认为它使用了与gcc不同的内存管理机制,对于这些用例,在生成的代码中似乎较慢。

Armen Tsirunyan 15 年前

矢量使用迭代器访问其元素,迭代器不能是bool*的简单typedef,这使得它比不提供迭代器的位集慢。另一个使其快速的原因是它的大小是已知的编译时间,因此它不使用new进行分配,这比堆栈分配慢。只是随便的想法

estan 12 年前

这是我访问/插入30亿元素的不科学基准 bitset<> 和 vector<bool> 大小分别为100K、1M和5M。编译器是64位Linux机器(核心i7)上的GCC4.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

因此,在这些条件下,当代码被优化时,位集比向量快,而向量实际上在不优化时以(非常小的)边缘排在最前面。

也就是说,如果您的代码是时间关键的,那么您可能应该自己执行基准测试,因为我怀疑这些数字是高度特定于编译器/环境的。

基准代码:

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

-2

Marcin 15 年前

另外,请注意 vector<bool> 是向量模板的专门化,其实现方式与您可能认为的完全不同。