c++ - `std::bitset` 有和没有边界检查

Question

关于 STL std::bitset - 它的文档说函数 set/reset/test 做边界检查，operator[] 没有。我的计时实验表明，set/test 函数的执行速度通常比 operator[] 快 2-3%。我正在使用的代码是:

typedef unsigned long long U64;
const U64 MAX = 800000000ULL;

struct Bitmap1
{
  void insert(U64 N) {this->s[N % MAX] = 1;}
  bool find(U64 N) const {return this->s[N % MAX];}
private:
  std::bitset<MAX> s;  // <---- takes MAX/8 memory (in bytes)
};

struct Bitmap2
{
  void insert(U64 N) {this->s.set(N % MAX);}
  bool find(U64 N) const {return this->s.test(N % MAX);}
private:
  std::bitset<MAX> s;  // <---- takes MAX/8 memory (in bytes)
};

int main()
{
  Bitmap2* s = new Bitmap2();
  // --------------------------- storing
  const size_t t0 = time(0);
  for (unsigned k = 0; k < LOOPS; ++k)
  {
    for (U64 i = 0; i < MAX; ++i) s->insert(i);
  }
  cout << "storing: " << time(0) - t0 << endl;
  // -------------------------------------- search
  const size_t t1 = time(0);
  U64 count = 0;
  for (unsigned k = 0; k < LOOPS; ++k)
  {
    for (U64 i = 0; i < MAX; ++i) if (s->find(i)) ++count;
  }
  cout << "search:  " << time(0) - t1 << endl;
  cout << count << endl;
}

这个怎么解释？没有边界检查应该可以为我们节省一些周期，对吗？

Compiler: g++ 4.8.1 (options -g -O4)
VMware VM: Ubuntu 3.11.0-15
Host: MacBook Pro

Answer 1

当我从时序中删除 rand、除法、输出和内存缓存时:

bool bracket_test() {
    std::bitset<MAX> s;
    for(int j=0; j<num_iterations; ++j) {
        for(int i=0; i<MAX; ++i)
            s[i] = !s[MAX-1-i];
    }
    return s[0];
}
bool set_test() {
    std::bitset<MAX> s;
    for(int j=0; j<num_iterations; ++j) {
        for(int i=0; i<MAX; ++i)
            s.set(i, !s.test(MAX-1-i));
    }
    return s.test(0);
}
bool no_test() {
    bool s = false;
    for(int j=0; j<num_iterations; ++j) {
        for(int i=0; i<MAX; ++i)
            s = !s;
    }
    return s;
}

我用 Clang 在 http://coliru.stacked-crooked.com/a/cdc832bfcc7e32be 得到了这些结果. (我做了 10000 次迭代，20 次，并测量了最短时间，这减少了计时错误。)

clang++ -std=c++11  -O0 -Wall -Wextra -pedantic -pthread main.cpp  && ./a.out
bracket_test took 178663845 ticks to find result 1
set_test     took 117336632 ticks to find result 1
no_test      took 9214297 ticks to find result 0
clang++ -std=c++11  -O1 -Wall -Wextra -pedantic -pthread main.cpp  && ./a.out
bracket_test took 798184780 ticks to find result 1
set_test     took 565999680 ticks to find result 1
no_test      took 41693575 ticks to find result 0
clang++ -std=c++11  -O2 -Wall -Wextra -pedantic -pthread main.cpp  && ./a.out
bracket_test took 81240369 ticks to find result 1
set_test     took 72172912 ticks to find result 1
no_test      took 41907685 ticks to find result 0
clang++ -std=c++11  -O3 -Wall -Wextra -pedantic -pthread main.cpp  && ./a.out
bracket_test took 77688054 ticks to find result 1
set_test     took 72433185 ticks to find result 1
no_test      took 41433010 ticks to find result 0

此测试的先前版本发现括号稍微快一些，但现在我提高了计时的准确性，看来我的计时误差幅度约为 3%。在 O1 时 Set 快 35-54%，在 O2 时快 13-49%，在 O3 时快 2-34%。除了查看程序集输出之外，这对我来说似乎是非常确定的。

所以这是通过 http://assembly.ynh.io/ 进行的汇编(在 GCC -O) :

std::bitset<MAX> s
s[1000000] = true;
return s;

0000 4889F8         movq    %rdi, %rax
0003 4889FA         movq    %rdi, %rdx
0006 488D8F00       leaq    100000000(%rdi), %rcx
     E1F505
000d 48C70200       movq    $0, (%rdx)
     000000
0014 4883C208       addq    $8, %rdx
0018 4839CA         cmpq    %rcx, %rdx
001b 75F0           jne .L2
001d 48838848       orq $1, 125000(%rax)
     E8010001 
0025 C3             ret

和

std::bitset<MAX> s;
s.set(1000000);
return s;

0026 4889F8         movq    %rdi, %rax
0029 4889FA         movq    %rdi, %rdx
002c 488D8F00       leaq    100000000(%rdi), %rcx
     E1F505
0033 48C70200       movq    $0, (%rdx)
     000000
003a 4883C208       addq    $8, %rdx
003e 4839CA         cmpq    %rcx, %rdx
0041 75F0           jne .L6
0043 48838848       orq $1, 125000(%rax)
     E8010001 
004b C3             ret

我实在看不懂汇编，但是这些完全一致，所以分析这个案例很容易。如果编译器知道它们都在范围内，它会优化范围检查。当我用可变索引替换固定索引时，Set 添加了 5 个操作来检查边界情况。

至于 Set 有时更快的原因，operator[] 必须为 Set 的引用代理做大量工作> 不必做。 Set 有时较慢的原因是代理被简单地内联，在这种情况下，唯一的区别是 Set 必须进行边界检查。另一方面，如果编译器无法证明索引始终在范围内，Set 只需进行边界检查。所以这在很大程度上取决于周围的代码。您的结果可能会有所不同。

http://en.cppreference.com/w/cpp/utility/bitset/set说:

Sets the bit at position pos to the value value.
Throws std::out_of_range if pos does not correspond to a valid position within the bitset.

http://en.cppreference.com/w/cpp/utility/bitset/operator_at说:

Accesses the bit at position pos. Returns an object of type std::bitset::reference that allows modification of the value.
Unlike test(), does not throw exceptions: the behavior is undefined if pos is out of bounds.

和http://en.cppreference.com/w/cpp/utility/bitset/reference说:

The std::bitset class includes std::bitset::reference as a publicly-accessible nested class. This class is used as a proxy object to allow users to interact with individual bits of a bitset, since standard C++ types (like references and pointers) are not built with enough precision to specify individual bits. The primary use of std::bitset::reference is to provide an l-value that can be returned from operator[]. Any reads or writes to a bitset that happen via a std::bitset::reference potentially read or write to the entire underlying bitset.

应该清楚的是，operator[] 实际上比直观的要多得多。