如何提高C++ STL bitset的效率？

我有一个程序，大量使用STL的bitset。 Gperftools表明，性能瓶颈之一是std::_Base_bitset::_S_maskbit（内联）。如何提高C++ STL bitset的效率？

从这里https://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a00775_source.html#l00078它似乎是一个访问或修改bitset掩码总是重新计算。这让我想知道查找表是否有用。

我试图实现我自己的版本bitset，其中使用掩码查找表。但是由于我的版本没有使用gcc内置指令，如__builtin_memcpy，它实际上比STL bitset慢得多。

所以我想知道是否有办法替代std::_Base_bitset::_S_maskbit，或者我应该通过复制STL bitset的代码并添加一个查找表来编写我自己的bitset版本。

谢谢！

2014-10-02 YJC

首先，你计划一个优化的构建？ – PaulMcKenzie 2014-10-02 04:21:44

现代处理器在计算值时比从内存中获取值要快得多。查找表几乎不是一个改进。 – 2014-10-02 04:39:39

@PaulMcKenzie用O2编译的程序。 – YJC 2014-10-02 04:53:35

如果你的位集足够小，使用std::vector<char>可以是一个改进。当然，你使用了8倍的内存，但你不需要再计算掩码，分析表明它与你有关。

由于x86对寻址模式和预取器的良好支持，在x86上访问数组的速度相当快，但是位集更像是ARM的领域，许多操作都可以包含免费的bitshift。

2014-10-02 07:30:26 MSalters

我的位包含400位。 – YJC 2014-10-02 10:40:43

我曾经在使用位图图像时发现，将每个8位扩展为8个字节的速度更快，执行我的操作并重新打包，而不是直接使用位图。 – 2014-10-02 21:24:23

考虑到400字节仍然适合L1缓存，如果这是一个类似的情况，我不会感到惊讶。 – MSalters 2014-10-02 21:55:31

从链接看来，掩码位（_S_maskbit）的重新计算只是一个左移，然后是模块化操作，如果_GLIBCXX_BITSET_BITS_PER_WORD是2的幂，和。所以重新计算该位的复杂度非常低，可能比访问查找表要低。

鉴于函数内联并且相对较短，gperf在分析它时可能不准确。或者__pos％_GLIBCXX_BITSET_BITS_PER_WORD无法优化为__pos &（_GLIBCXX_BITSET_BITS_PER_WORD - 1），在这种情况下，运算符％可能是此处最昂贵的操作。

2016-12-31 15:30:52 Edy

回答