Как улучшить эффективность битов C++ STL?

Question

У меня есть программа, которая сильно использует STL's bitset. И gperftools показывает, что одна из горлышек с производительностью - std::_Base_bitset::_S_maskbit (inline).

Отсюда 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, или я должен написать свою собственную версию bitset, скопировав код STL bitset и добавив таблицу поиска.

Спасибо!

Answer 1

Если ваши биты достаточно малы, использование std::vector<char> может быть улучшением. Конечно, вы используете в 8 раз больше памяти, но вам больше не нужно будет вычислять маски, и профилирование показало, что это важно для вас.

Доступ к массивам довольно быстрый на x86 из-за хорошей поддержки режимов адресации и prefetchers, но биты - это больше область ARM, где многие операции могут включать в себя бесплатный бит-сдвиг.

Answer 2

Из ссылки, по-видимому, перекомпоновка бит маски (_S_maskbit) - это только сдвиг влево, за которым следует модульная операция, которая (если _GLIBCXX_BITSET_BITS_PER_WORD - это мощность 2) могла бы быть оптимизирована компилятором как логико- А ТАКЖЕ. Таким образом, сложность пересчета бит действительно низка, вероятно, ниже, чем доступ к таблице поиска.

Учитывая, что функция является встроенной и относительно короткой, gperf может быть неточным при профилировании. Или, возможно, __pos% _GLIBCXX_BITSET_BITS_PER_WORD не может быть оптимизирован как __pos & (_GLIBCXX_BITSET_BITS_PER_WORD - 1), и в этом случае оператор%, вероятно, будет самой дорогой операцией здесь.