如何提高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

回答