Недавно я наткнулся на шаблоны битсетов и очень хотел бы использовать их в своем текущем проекте. Читая дальше, я вижу, что размер шаблона std::bitset
должен быть определен во время компиляции. Многие предлагают использовать boost::dynamic_bitset
, чтобы облегчить это требование.
Чтобы сравнить их, я решил провести сравнение скорости методов set
, flip
и count
.
Результаты довольно странные ... и мне интересно, может ли кто-нибудь пролить на это свет для меня.
Код в конце поста, но я объясню, что я делаю здесь. У меня есть один объект std::bitset
(назовем его bs
) и один объект boost::dynamic_bitset
(назовем его dynbs
). Каждый имеет n=1000000
бит. Для указанного выше метода вызовите метод для каждого из n
битов последовательно и повторите это R=10000
раз.
Используя библиотеку std::chrono
, вот тайминги для каждого в наносекундах:
set
bitset: 267 nsecs
dyn bitset: 18603174546 nsecs
flip
bitset: 73 nsecs
dyn bitset: 18842352867 nsecs
count
bitset: 77 nsecs
dyn bitset: 51 nsecs
boost::dynamic_bitset
кажется намного медленнее для set
и flip
.
Чтобы сделать это более интересным, если метод reset
вызывается для двух объектов перед запуском этих тестов, то тайминги сравнимы. Они здесь:
set
bitset: 19397779399 nsecs
dyn bitset: 18472863864 nsecs
flip
bitset: 18599248629 nsecs
dyn bitset: 18376267939 nsecs
count
bitset: 68 nsecs
dyn bitset: 61 nsecs
Теперь оба контейнера утверждают, что инициализируют все биты значением 0
, поэтому вызов reset
не должен изменять ни один из битов. Сброс вывода none
до и после reset
подтверждает это.
Итак, после всего этого у меня два вопроса:
1) Почему boost::dynamic_bitset
намного медленнее, чем std::bitset
при вызове set
и flip
?
2) Почему вызов reset
оказывает огромное негативное влияние на скорость std::bitset
?
Вот мой код:
#include <iostream>
#include <iomanip>
#include <bitset>
#include <boost/dynamic_bitset.hpp>
#include <vector>
#include <chrono>
#include <ctime>
using namespace std;
using namespace chrono;
using namespace boost;
int main(){
const unsigned int n=1000000;
bitset< n > bs;
dynamic_bitset< > dynbs(n);
// bs.reset();
// dynbs.reset();
unsigned int i,r,R=10000;
high_resolution_clock::time_point tick,tock;
////////////////////////////////////////////////////////////
// Method: set
std::cout << "set" << std::endl;
tick=high_resolution_clock::now();
for(r=0; r<R; r++)
for(i=0; i<n; i++)
bs.set(i);
tock=high_resolution_clock::now();
cout << setw(16) << "bitset: "
<< setw(16) << duration_cast<nanoseconds>(tock-tick).count() << " nsecs"
<< std::endl;
tick=high_resolution_clock::now();
for(r=0; r<R; r++)
for(i=0; i<n; i++)
dynbs.set(i);
tock=high_resolution_clock::now();
cout << setw(16) << "dyn bitset: "
<< setw(16) << duration_cast<nanoseconds>(tock-tick).count() << " nsecs"
<< std::endl << std::endl;
////////////////////////////////////////////////////////////
// Method: flip
std::cout << "flip" << std::endl;
tick=high_resolution_clock::now();
for(r=0; r<R; r++)
for(i=0; i<n; i++)
bs.flip(i);
tock=high_resolution_clock::now();
cout << setw(16) << "bitset: "
<< setw(16) << duration_cast<nanoseconds>(tock-tick).count() << " nsecs"
<< std::endl;
tick=high_resolution_clock::now();
for(r=0; r<R; r++)
for(i=0; i<n; i++)
dynbs.flip(i);
tock=high_resolution_clock::now();
cout << setw(16) << "dyn bitset: "
<< setw(16) << duration_cast<nanoseconds>(tock-tick).count() << " nsecs"
<< std::endl << std::endl;
////////////////////////////////////////////////////////////
// Method: count
std::cout << "count" << std::endl;
tick=high_resolution_clock::now();
for(r=0; r<R; r++)
for(i=0; i<n; i++)
bs.count();
tock=high_resolution_clock::now();
cout << setw(16) << "bitset: "
<< setw(16) << duration_cast<nanoseconds>(tock-tick).count() << " nsecs"
<< std::endl;
tick=high_resolution_clock::now();
for(r=0; r<R; r++)
for(i=0; i<n; i++)
dynbs.count();
tock=high_resolution_clock::now();
cout << setw(16) << "dyn bitset: "
<< setw(16) << duration_cast<nanoseconds>(tock-tick).count() << " nsecs"
<< std::endl;
return 0;
}
Я скомпилировал его с
g++ -O3 -std=c++11 bitset.cpp -o bitset
где bitset.cpp
— код, вставленный выше.
bs
, после каждого цикла, тоset
иflip
, вероятно, не будут оптимизированы. Чтобы гарантировать, что вызовыcount
не будут оптимизированы, добавьте возвращаемое значение в переменную, которую затем распечатаете.dynamic_bitset
использует выделение в куче, и компилятору гораздо сложнее доказать, что изменения, сделанныеset
иflip
, будут невидимыми. - person T.C.   schedule 20.08.2014