boost :: dynamic_bitset медленнее, чем std :: bitset, если std :: bitset не сбрасывается

Недавно я столкнулся с шаблонами битов и хотел бы использовать их в своем текущем проекте. Я std::bitset шаблон 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 - это код, вставленный выше.

Ответы

Ответ 1

1) Почему boost::dynamic_bitset намного медленнее, чем std::bitset при вызове set и flip?

Поскольку std::bitset не использует динамическое распределение, а ваш bitset набор - это локальная переменная, компилятор может легко определить, что весь set flip и count имеют внешнего эффекта. В результате он оптимизирует их всех, и ваш код в основном заканчивается тем, что он связан с синхронизацией и печатью вызовов.

Обратите внимание, что в приведенной выше сборке он даже не выделяет пространство стека для битового набора. Все это практически исчезло без следа.

boost::dynamic_bitset динамически распределяет свой буфер с помощью new, который заканчивается вызовом ::operator new(), который может быть произвольной перегруженной версией, определенной в другой единицы перевода. Поэтому компилятору очень сложно доказать, что изменения в возвращаемом буфере не отображаются внешне.

Ваши циклы count для обоих std::bitset и boost::dynamic_bitset оптимизированы, потому что компилятор может легко увидеть, что count() ничего не меняет в битах, и вы не используете возвращаемое значение.

2) Почему reset вызова оказывает огромное негативное влияние на скорость std :: bitset?

Я проверил исходный код reset в GCC, и он вызывает встроенный компилятор __builtin_memset, передавая ему указатель на буфер. Когда вы передаете указатель на переменную стека во внешнюю функцию, тогда компилятор гораздо более ограничен в том, что он может удалить, так как изменения в переменной теперь могут быть внешне наблюдаемыми (например, вызванная функция могла бы хранить копию указатель где-нибудь, и что-то может заглянуть в него позже).

Ответ 2

Ну, похоже, у TC есть объяснение.

Все ваши настройки и флип (и подсчеты) на битете полностью оптимизированы.

Ссылка была предоставлена с кодом сборки, чтобы показать это: код сборки

Возвращая значения из трех разных методов и добавляя их к дополнительной переменной, сделал трюк, и теперь это будет честная борьба (как было предложено TC).