Есть ли какое-то преимущество в манипулировании битами в стиле c по сравнению с std :: bitset?

16

Я работаю почти исключительно в C ++ 11/14, и обычно сжимаюсь, когда вижу такой код:

std::int64_t mArray;
mArray |= someMask << 1;

Это всего лишь пример; Я говорю о побитовой манипуляции в целом. В C ++ есть ли смысл? Вышесказанное искажает сознание и подвержено ошибкам, а использование std::bitsetпозволяет:

  1. проще изменить размер по std::bitsetмере необходимости, настроив параметр шаблона и позволив реализации позаботиться обо всем остальном, и
  2. тратьте меньше времени на выяснение того, что происходит (и, возможно, на ошибки), и пишите std::bitsetтак же, как std::arrayи другие контейнеры данных.

Мой вопрос есть ли причина не использовать std::bitsetповерх примитивных типов, кроме как для обратной совместимости?

шест для отталкивания
источник
Размер a std::bitsetфиксируется во время компиляции. Это единственный серьезный недостаток, о котором я могу думать.
Руон
1
@ rwong Я говорю о std::bitsetбитовой манипуляции в стиле c (например int), которая также исправлена ​​во время компиляции.
кв
Одной из причин может быть унаследованный код: код был написан, когда он std::bitsetбыл недоступен (или известен автору), и не было причин переписывать код для использования std::bitset.
Барт ван Инген Шенау
Лично я считаю, что вопрос о том, как сделать «операции над множеством / картой / массивом бинарных переменных», понятные каждому, в значительной степени остается нерешенным, поскольку на практике используется много операций, которые нельзя свести к простым операциям. Существует также слишком много способов представления таких наборов, из которых bitsetодин, но небольшой вектор или набор ints (битового индекса) также могут быть допустимыми. Философия C / C ++ не скрывает эти сложности выбора от программиста.
Rwong

Ответы:

12

С логической (нетехнической) точки зрения преимущества нет.

Любой простой код C / C ++ может быть заключен в подходящую «библиотечную конструкцию». После такой упаковки вопрос «является ли это более выгодным, чем это» становится спорным вопросом.

С точки зрения скорости, C / C ++ должен позволять конструкции библиотеки генерировать код, который столь же эффективен, как и простой код, который он переносит. Это, однако, подлежит:

  • Функция встраивания
  • Проверка во время компиляции и устранение ненужной проверки во время выполнения
  • Устранение мертвого кода
  • Многие другие оптимизации кода ...

Используя этот вид нетехнического аргумента, любые «отсутствующие функции» могут быть добавлены кем угодно, и поэтому не считаются недостатком.

Однако встроенные требования и ограничения не могут быть преодолены с помощью дополнительного кода. Ниже я утверждаю, что размер std::bitsetявляется константой времени компиляции, и, следовательно, хотя это и не считается недостатком, он все же влияет на выбор пользователя.


С эстетической точки зрения (удобочитаемость, простота обслуживания и т. Д.) Есть разница.

Тем не менее, не очевидно, что std::bitsetкод сразу побеждает простой C-код. Нужно взглянуть на большие куски кода (а не на какой-то игрушечный образец), чтобы сказать, std::bitsetулучшило ли использование исходный код человеческое качество.


Скорость работы с битами зависит от стиля кодирования. Стиль кодирования влияет как на манипулирование битами C / C ++, так и в равной степени применим std::bitset, как объясняется ниже.


Если кто-то пишет код, который использует operator []для чтения и записи по одному биту за раз, ему придется делать это несколько раз, если нужно манипулировать более чем одним битом. То же самое можно сказать о коде в стиле C.

Однако bitsetтакже есть другие операторы, такие как operator &=, operator <<=и т. Д., Которые работают на всю ширину набора битов. Поскольку базовый механизм часто может работать с 32-разрядными, 64-разрядными, а иногда и 128-разрядными (с SIMD) за один раз (при том же количестве циклов ЦП), код, предназначенный для использования преимуществ таких многобитовых операций может быть быстрее, чем "зацикленный" код битовой манипуляции.

Общая идея называется SWAR (SIMD в регистре) и является подтемой при битовых манипуляциях.


Некоторые поставщики C ++ могут использовать bitsetот 64 до 128 бит с SIMD. Некоторые поставщики не могут (но могут в конечном итоге сделать). Если необходимо знать, что делает библиотека вендора C ++, единственный способ - посмотреть на разборку.


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

  1. Размер std::bitsetдолжен быть известен во время компиляции. Чтобы создать массив битов с динамически выбранным размером, нужно будет использовать std::vector<bool>.
  2. Текущая спецификация C ++ для std::bitsetне предоставляет способ извлечения последовательного фрагмента из N битов из большего bitsetиз M битов.

Первый является основополагающим, то есть для людей, которым нужны динамические размеры битов, они должны выбрать другие варианты.

Второй можно преодолеть, потому что можно написать какие-то адаптеры для выполнения задачи, даже если стандарт bitsetне расширяемый.


Существуют определенные типы расширенных операций SWAR, которые не предоставляются из коробки std::bitset. Можно прочитать об этих операциях на этом сайте о битовых перестановках . Как обычно, их можно реализовать самостоятельно, работая поверх std::bitset.


По поводу обсуждения по производительности.

Одно замечание: многие люди спрашивают, почему (что-то) из стандартной библиотеки намного медленнее, чем какой-то простой код в стиле C. Я бы не стал повторять здесь предварительные знания о микробенчмаркинге, но у меня есть только один совет: убедитесь, что проводите тестирование в «режиме выпуска» (с включенной оптимизацией), и убедитесь, что код не удаляется (устранение мертвого кода) или выведен из цикла (петлево-инвариантный код движения) .

Так как в целом мы не можем сказать, правильно ли кто-то (в Интернете) делал микробенчмарки, единственный способ получить достоверное заключение - это сделать собственные микробенчмарки, документировать детали и представить для публичного просмотра и критики. Не мешает заново делать микробенчмарки, которые раньше делали другие.

rwong
источник
Проблема № 2 также означает, что набор битов не может использоваться ни в одной параллельной установке, где каждый поток должен работать с подмножеством набора битов.
user239558
@ user239558 Я сомневаюсь, что кто-то захочет распараллелить то же самое std::bitset. Нет гарантии целостности памяти (in std::bitset), что означает, что она не должна быть распределена между ядрами. Люди, которым нужно делиться ими между ядрами, будут стремиться к созданию собственной реализации. Когда данные распределяются между разными ядрами, принято выравнивать их по границе строки кэша. Невыполнение этого требования снижает производительность и создает больше ошибок, не связанных с атомарностью. У меня недостаточно знаний, чтобы дать обзор того, как построить параллелизуемую реализацию std::bitset.
Rwong
параллельное программирование данных обычно не требует согласованности памяти. Вы только синхронизируете между фазами. Я абсолютно хотел бы обрабатывать битсет параллельно, я думаю, что любой с большой bitsetволей.
user239558
@ user239558, который звучит как подразумевающий копирование (соответствующий диапазон битов, который должен обрабатываться каждым ядром, должен быть скопирован до начала обработки). Я согласен с этим, хотя я думаю, что любой, кто думает о распараллеливании, уже подумает о развертывании собственной реализации. В общем, многие стандартные библиотеки C ++ предоставляются в качестве базовых реализаций; любой, у кого есть более серьезные потребности, собирается реализовать свои собственные.
Rwong
нет нет копирования. это просто доступ к различным частям статической структуры данных. синхронизация не требуется.
user239558
2

Это, конечно, применимо не во всех случаях, но иногда алгоритм может зависеть от эффективности сдвоенного твила в стиле C для обеспечения значительного прироста производительности. Первый пример, который мне приходит в голову, - это использование битбордов , умных целочисленных кодировок позиций настольных игр, чтобы ускорить шахматные движки и тому подобное. Здесь фиксированный размер целочисленных типов не проблема, так как шахматные доски всегда равны 8 * 8.

Для простого примера рассмотрим следующую функцию (взятую из этого ответа Бена Джексона ), которая проверяет позицию Connect Four на победу:

// return whether newboard includes a win
bool haswon2(uint64_t newboard)
{
    uint64_t y = newboard & (newboard >> 6);
    uint64_t z = newboard & (newboard >> 7);
    uint64_t w = newboard & (newboard >> 8);
    uint64_t x = newboard & (newboard >> 1);
    return (y & (y >> 2 * 6)) | // check \ diagonal
           (z & (z >> 2 * 7)) | // check horizontal -
           (w & (w >> 2 * 8)) | // check / diagonal
           (x & (x >> 2));      // check vertical |
}
Дэвид Чжан
источник
2
Как вы думаете, std::bitsetбудет медленнее?
кв
Итак, с первого взгляда на источник, набор битов libc ++ основан на одном size_t или их массиве, поэтому, вероятно, будет скомпилирован во что-то по существу эквивалентное / идентичное, особенно в системе, где sizeof (size_t) == 8 - так что нет, наверное, не будет медленнее.
Райан Павлик