除非std :: bitset被重置,否则boost :: dynamic_bitset比std :: bitset慢

Question

我最近遇到了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上面插入的代码在哪里.

Answer 1

1)为什么boost::dynamic_bitset比std::bitset调用set和flip时要慢得多 ？

由于std::bitset不使用动态分配的,而你bitset是一个局部变量,编译器可以很容易地确定,所有set的和flipS和count■找没有外部可见的效果.结果,它将它们全部优化掉,而你的代码基本上最终成为一堆定时和打印调用.

请注意,在上面的程序集中,它甚至不为bitset分配堆栈空间.整个事情基本上消失得无影无踪.

boost::dynamic_bitset动态分配其缓冲区new,最终调用::operator new(),可以是在不同的翻译单元中定义的任意重载版本.因此,编译器很难证明返回的缓冲区的更改在外部是不可见的.

你count的两个回路std::bitset,并boost::dynamic_bitset因为编译器可以很容易地看到,会被优化掉count()不更改任何位集,你不使用返回值.

2)为什么调用reset会对std :: bitset的速度产生巨大的负面影响？

我检查了resetGCC中的源代码,它调用了编译器内部函数__builtin_memset,并将指针传递给缓冲区.当您将指向堆栈变量的指针传递给外部函数时,编译器在它可以删除的内容中受到的限制更多,因为变量中的更改现在可以在外部进行观察(例如,调用的函数可能存储了一个副本指针在某处,有些东西可以在以后偷看它.