В соответствии с этим ответом плакат ожидает std::bitset размера 100k бит быстрее, чем std::vector<bool> при запросе отдельных битов. Как это возможно?
Как они могут существенно различаться в своей реализации, если std::bitset, по-видимому, допускает произвольные размеры, как std::vector?
Измерения в Visual Studio 2010 показывают, что std::bitset обычно не быстрее, чем std::vector<bool>. Какую именно причину этого я не могу сказать - только этот битсет реализован значительно отличается от полной специализации std::vector.
std:: bitset сохраняет полный контент в объекте через
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 . . .
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
обратите внимание на /O 2 и отсутствующий /GL (не весь prg opt).
Ну, так как я тот парень, на которого вы задаете этот вопрос, здесь, где я получил эту идею из:
"... он упаковывает bools и сохраняет их как отдельные биты (внутри, скажем, символы) во внутреннем представлении. Одним из следствий этого является то, что он не может просто вернуть нормальный bool & из своего оператора [] или его разыменованные итераторы [2], вместо этого он должен играть в игры со вспомогательным классом" proxy", который является bool-подобным, но определенно не является bool. К сожалению, это также означает, что доступ к vector<bool> медленнее, потому что мы имеем для работы с прокси-серверами вместо прямых указателей и ссылок.
...
Нижняя строка: если вам больше нужна скорость, чем размер, вы не должны использовать std::vector<bool>. Вместо этого вы должны взломать эту оптимизацию, используя вместо этого std::vector<char> или тому подобное, что является неудачным, но тем не менее лучшим, что вы можете сделать ".
Или, как я рекомендовал, если вы знаете самый большой размер, который получит ваш набор, используйте std::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
Кроме того, просто для добавления ответов на эти вопросы и напоминания о том, как компилятор зависит от LOT в производительности, вот простой тест, выполненный с помощью:
(но все эти тесты немного сложны и, возможно, дают нам только приблизительную общую идею для сравнения DIRECT. Профилирование проекта это единственное, что нужно сделать в конце.)
ПРИМЕЧАНИЕ.
с размером 10 ^ 7:
Я включил служебное время конструктора и деструктора объектов.
здесь простой тестовый код:
#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++ output -O2 -std = С++ 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 output -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 output -O2 -std = С++ 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
ВЫВОД:
Как грубый вектор идеи кажется более быстрым для этих случаев использования.
Я не запускаю несколько istances и усредняю результаты, но более или менее значения всегда одинаковы.
примечание на VS: я думаю, что он использует другой механизм управления памятью, относящийся к gcc, и для этих случаев использования в сгенерированном коде медленнее.
вектор обращается к своим элементам с помощью итераторов, что не может быть простым typedef для bool *, что делает его медленнее, чем битсет, который не предоставляет итераторов. Еще одна вещь, которая делает это быстро, заключается в том, что его размер известен как время компиляции, и поэтому он не выделяет новые, что медленнее, чем распределение стека. Просто случайные мысли
Здесь мой ненаучный критерий доступа/вставки 3 миллиардов элементов из/в bitset<> и vector<bool> размером 100K, 1M и 5M. Компилятор GCC 4.8.2 на 64-битной машине Linux (Core i7):
С оптимизацией (флаги компилятора: -O2 -std=c++11):
[[email protected] 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):
[[email protected] bitset_vs_vector]$ make
g++ -std=c++11 -o bitset_vs_vector *.cpp
[[email protected] 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;
}
Также обратите внимание, что a vector<bool> является специализацией векторного шаблона и реализуется совсем по-другому, чем вы думаете.