13

我最近遇到了 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::bitsetsetflip

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上面插入的代码在哪里。

4

2 回答 2

31

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

由于std::bitset不使用动态分配，并且 yourbitset是一个局部变量，编译器可以很容易地确定所有的set'sflip和counts 都没有外部可见的影响。结果，它把它们全部优化了，你的代码基本上最终变成了一堆计时和打印调用。

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

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

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

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

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

于 2014-08-21T00:52:32.067 回答
1

好吧，看起来TC有解释。

您在 bitset 上的所有设置和翻转（和计数）都已完全优化。

汇编代码提供了一个链接来显示这一点：汇编代码

通过从三个不同的方法返回值并将它们添加到一个附加变量中就可以了，现在这似乎是一场公平的斗争（正如 TC 所建议的那样）。

于 2014-08-20T18:09:48.323 回答