c++ - boost::dynamic_bitset 比 std::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 的调用不应更改任何位。在 reset 之前和之后转储 none 的输出确实可以确认这一点。

毕竟，我有两个问题:

1) 为什么调用 set 和 flip 时 boost::dynamic_bitset 比 std::bitset 慢很多?

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) Why is the boost::dynamic_bitset so much slower than the std::bitset when calling set and flip?

由于 std::bitset 不使用动态分配，而且你的 bitset 是一个局部变量，编译器可以很容易地确定所有 set's 和 flips 和 counts 没有外部可见的效果。结果，它optimizes them all away ，并且您的代码基本上最终会成为一堆计时和打印调用。

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

boost::dynamic_bitset 使用 new 动态分配其缓冲区，最终调用 ::operator new()，这可以是在不同的翻译单元中定义的任意重载版本。所以编译器很难证明返回的缓冲区的变化在外部是不可见的。

std::bitset 和 boost::dynamic_bitset 的 count 循环都被优化掉了，因为编译器可以很容易地看到 count() 不会更改位集中的任何内容，并且您不使用返回值。

2) Why does calling reset have a huge negative effect on the speed of std::bitset?

我在 GCC 中检查了 reset 的源代码，它调用了编译器内部的 __builtin_memset，并传递了一个指向缓冲区的指针。当您将指向堆栈变量的指针传递给外部函数时，编译器在可以删除的内容方面受到更多限制，因为变量中的更改现在可能是外部可观察到的(例如，被调用的函数可能已经存储了某处的指针，稍后可以窥视它)。