如何std :: bitset比`std :: vector< bool>`更快? [英] How can std::bitset be faster than `std::vector<bool>`?
问题描述
根据此回答海报要求大小为100k位的 std :: bitset 在查询单个位时比 std :: vector< bool>
更快。这怎么可能?如果std :: bitset显然允许像std :: vector这样的任意大小,它们如何在它们的实现中有显着差异?
According to this answer the poster expects a std::bitset of size 100k bits to be faster than a std::vector<bool>
when querying individual bits. How can this be possible? How could they even differ significantly in their implementation, if std::bitset apparently allows for arbitrary sizes just like std::vector?
推荐答案
p>测量在Visual Studio 2010显示 std :: bitset
是不是一般快于 std :: vector< bool> ;
。这是什么确切的原因是我不能说 - 只有bitset被实现与std :: vector完全专业化显着不同。
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对象中的内容通过
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
};
数组,这使得大bitset不适合放在堆栈上 - 这不是一个性能参数本身。
array and that makes large bitset unsuitable to be put on the stack -- which isn't a performance argument per se.
向量< bool>
不会遇到堆栈问题, 1e6和1e7似乎在我的盒子里,在一个循环中查询值实际上是一个向量的两倍快。
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.
好吧。我想通常的时间限制适用和YMMV,但这里是我使用的测试代码,任何人都应该尝试自己:
Well. I guess the usual timing caveats apply and YMMV, but here's the test code I used should anyone care to try himself:
我的盒子上的输出是:
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
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
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选择)。
note the /O2 and the missing /GL (no whole prg opt).
这篇关于如何std :: bitset比`std :: vector< bool>`更快?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!