Какую реализацию битового набора следует использовать для максимальной производительности?

В настоящее время я пытаюсь реализовать различные алгоритмы в компиляторе Just In Time (JIT). Многие из алгоритмов работают с растровыми изображениями, более широко известными как биты.

В С++ существуют различные способы реализации битового набора. Как настоящий разработчик на С++, я бы предпочел использовать что-то из STL. Самый важный аспект - производительность. Мне не обязательно нужен динамически изменяемый битрейт.

Как я вижу, существует три возможных варианта.

я. Один из вариантов - использовать std::vector<bool>, который был оптимизирован для пространства. Это также указывает на то, что данные не должны быть смежными в памяти. Думаю, это может снизить производительность. С другой стороны, наличие одного бита для каждого значения bool может повысить скорость, поскольку он очень удобен для кеширования.

II. Другой вариант - вместо этого использовать std::vector<char>. Это гарантирует, что данные смежны в памяти, и легче получить доступ к отдельным элементам. Тем не менее, кажется странным использовать эту опцию, поскольку она не предназначена для битов.

III. Третьим вариантом будет использование фактического std::bitset. Тот факт, что он не динамически изменен, не имеет значения.

Какой из них следует выбрать для максимальной производительности?

Ответы

Ответ 1

Лучший способ - просто сравнить его, потому что каждая ситуация другая.

Я бы не использовал std::vector<bool>. Я попробовал это однажды, и производительность была ужасной. Я мог бы улучшить производительность моего приложения, просто используя std::vector<char>.

Я действительно не сравнивал std::bitset с std::vector<char>, но если пространство не является проблемой в вашем случае, я бы пошел на std::vector<char>. Он использует в 8 раз больше места, чем бит, но поскольку ему не нужно выполнять бит-операции для получения или установки данных, это должно быть быстрее.

Конечно, если вам нужно хранить много данных в битете/векторе, тогда было бы полезно использовать битовый набор, потому что это будет входить в кеш процессора.

Самый простой способ - использовать typedef и скрыть реализацию. Оба битового набора и вектора поддерживают оператор [], поэтому легко переключить одну реализацию на другую.

Ответ 2

Недавно я ответил на аналогичный вопрос на этом форуме. Я рекомендую библиотеку BITSCAN. Я только что выпустил версию 1.0. BITSCAN специально разработан для быстрого сканирования бит.

Класс BitBoard обертывает ряд различных реализаций для типичных операций, таких как bsf, bsr или popcount для 64-битных слов (также называемых битами). Классы BitBoardN, BBIntrin и BBSentinel расширяют сканирование бит до битовых строк. Битовая строка в BITSCAN представляет собой массив битов. Класс базовой оболочки для битовой строки - BitBoardN. BBIntrin расширяет BitBoardN, используя встроенные компиляторы Windows поверх 64-х бит. BBIntrin переносится в POSIX с помощью соответствующих эквивалентных функций asm.

Я использовал BITSCAN для реализации ряда эффективных решателей для комбинаторных задач NP в области графа. Как правило, матрица смежности графа, а также множества вершин кодируются как битовые строки, а типичные вычисления выполняются с использованием бит-масок. Код для простых объектов с битокодированным графом доступен в GRAPH. Также доступны примеры использования BITSCAN и GRAPH.

Сравнение BITSCAN и типичных реализаций в STL (битрейт) и BOOST (dynamic_bitset) можно найти здесь: http://blog.biicode.com/bitscan-efficiency-at-glance/