производительность — Как повысить эффективность набора битов C ++ STL?
У меня есть программа, которая интенсивно использует STL bitset, И gperftools показывает, что одна из горловин бутылки производительности std::_Base_bitset::_S_maskbit (в соответствии).
Отсюда 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 и добавление справочной таблицы.
Спасибо!
Решение
Если ваши битовые наборы достаточно малы, используйте std::vector<char> может быть улучшением. Конечно, вы используете 8 раз больше памяти, но вам не нужно больше вычислять маски, и профилирование показало, что это важно для вас.
Доступ к массивам в x86 довольно быстрый благодаря хорошей поддержке режимов адресации и предварительной выборки, но наборы битов — это больше область ARM, где многие операции могут включать бесплатное смещение битов.
Другие решения
По ссылке видно, что пересчет бита маски (_S_maskbit) — это просто сдвиг влево, за которым следует модульная операция, которая (если _GLIBCXX_BITSET_BITS_PER_WORD имеет степень 2) могла бы быть оптимизирована компилятором как логическое И. Таким образом, сложность повторного вычисления бита действительно мала, вероятно, ниже, чем доступ к таблице поиска.
Учитывая, что функция встроенная и относительно короткая, gperf может быть не точным в ее профилировании. Или, возможно, __pos% _GLIBCXX_BITSET_BITS_PER_WORD не может быть оптимизирован как __pos & (_GLIBCXX_BITSET_BITS_PER_WORD — 1), в этом случае оператор%, вероятно, будет самой дорогой операцией здесь.