Какова производительность std::bitset?
Недавно я задал вопрос программистам о причинах использования ручного управления битами примитивных типов над std::bitset,
Из этого обсуждения я пришел к выводу, что главная причина - его сравнительно худшие показатели, хотя я не знаю каких-либо взвешенных оснований для этого мнения. Итак, следующий вопрос:
Какое снижение производительности может произойти при использовании std::bitset над бит-манипуляциями примитива?
Вопрос намеренно широк, потому что после просмотра в Интернете я ничего не смог найти, поэтому возьму то, что смогу получить. В основном я за ресурсом, который обеспечивает некоторое профилирование std::bitset vs альтернативы "pre-bitset" для тех же проблем на некоторых типичных архитектурах компьютеров, использующих GCC, Clang и / или VC++. Существует очень полная статья, которая пытается ответить на этот вопрос для битовых векторов:
http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf
К сожалению, это или предшествует или считается вне области std::bitset, поэтому он сосредоточен на реализации векторов / динамических массивов.
Я действительно просто хочу знать, std::bitset лучше, чем альтернативы для вариантов использования, которые он намеревается решить. Я уже знаю, что это проще и понятнее, чем возиться с целым числом, но так ли это быстро?
5 ответов
Обновить
Прошло много лет с тех пор, как я опубликовал это, но:
Я уже знаю, что это проще и понятнее, чем возиться с целым числом, но так ли это быстро?
Если вы используете bitset таким образом, что это на самом деле делает его более ясным и чистым, чем битовая игра, например, проверяя один бит за раз вместо использования битовой маски, тогда неизбежно вы теряете все те преимущества, которые предоставляют побитовые операции, такие как возможность проверять, чтобы увидеть если 64 бита установлены за один раз против маски или с помощью инструкций FFS, чтобы быстро определить, какой бит установлен среди 64-битных.
Я не уверен что bitset влечет за собой штраф за использование всеми возможными способами (например: использование его побитового operator&), но если вы используете его как логический массив фиксированного размера, который, как я всегда вижу, используют люди, то вы, как правило, теряете все преимущества, описанные выше. К сожалению, мы не можем достичь такого уровня выразительности, просто получая доступ по одному operator[] и пусть оптимизатор выяснит все побитовые манипуляции, FFS и FFZ и так далее, что происходит для нас, по крайней мере, с тех пор, как я проверял последний раз (в противном случае bitset будет одним из моих любимых структур).
Теперь, если вы собираетесь использовать bitset<N> bits взаимозаменяемо, как, скажем, uint64_t bits[N/64] как при доступе к обоим одинаковым способом с использованием побитовых операций, это может быть на одном уровне (не проверялось с этого древнего поста). Но тогда вы теряете многие из преимуществ использования bitset на первом месте.
for_each метод
Я думаю, что в прошлом у меня возникали некоторые недоразумения, когда я предлагал for_each метод перебирать такие вещи, как vector<bool>, deque, а также bitset, Смысл такого метода состоит в том, чтобы использовать внутренние знания контейнера для более эффективной итерации по элементам при вызове функтора, так же как некоторые ассоциативные контейнеры предлагают find собственный метод вместо использования std::find сделать лучше, чем поиск по линейному времени.
Например, вы можете перебирать все установленные биты vector<bool> или же bitset если вы обладаете внутренними знаниями об этих контейнерах, проверяя одновременно 64 элемента, используя 64-битную маску, когда заняты 64 смежных индекса, и аналогичным образом используйте инструкции FFS, когда это не так.
Но дизайн итератора должен делать этот тип скалярной логики в operator++ неизбежно придется делать что-то значительно более дорогое, просто по характеру, в котором итераторы разработаны в этих особых случаях. bitset не хватает итераторов, и это часто заставляет людей хотеть использовать его, чтобы избежать использования побитовой логики operator[] проверить каждый бит отдельно в последовательном цикле, который просто хочет узнать, какие биты установлены. Это тоже не так эффективно, как for_each Реализация метода может сделать.
Двойные / Вложенные Итераторы
Еще одна альтернатива for_each Предложенный выше контейнерно-специфический метод будет заключаться в использовании двойных / вложенных итераторов, то есть внешнего итератора, который указывает на поддиапазон итератора другого типа. Пример кода клиента:
for (auto outer_it = bitset.nbegin(); outer_it != bitset.nend(); ++outer_it)
{
for (auto inner_it = outer_it->first; inner_it != outer_it->last; ++inner_it)
// do something with *inner_it (bit index)
}
Несмотря на то, что он не соответствует плоскому типу конструкции итератора, доступному сейчас в стандартных контейнерах, это может позволить некоторые очень интересные оптимизации. В качестве примера представьте случай, подобный этому:
bitset<64> bits = 0x1fbf; // 0b1111110111111;
В этом случае внешний итератор может с помощью всего лишь нескольких побитовых итераций ((FFZ/ или / дополнение) сделать вывод, что первый диапазон битов для обработки будет битами [0, 6), и в этот момент мы можем выполнить итерацию этого очень дешевый поддиапазон через внутренний / вложенный итератор (он будет просто увеличивать целое число, делая ++inner_it эквивалентно просто ++int). Затем, когда мы увеличиваем внешний итератор, он может очень быстро, и снова с помощью нескольких побитовых инструкций, определить, что следующий диапазон будет [7, 13). После того, как мы пройдемся по этому поддиапазону, мы закончили. Возьмите это как другой пример:
bitset<16> bits = 0xffff;
В таком случае первый и последний поддиапазон будут [0, 16) и набор битов может определить это с помощью одной побитовой инструкции, в которой мы можем выполнить итерацию по всем установленным битам, и тогда все готово.
Этот тип вложенного дизайна итератора будет особенно хорошо отображаться на vector<bool>, deque, а также bitset а также другие структуры данных, которые люди могут создавать как развернутые списки.
Я говорю это таким образом, что это выходит за рамки простого предположения, поскольку у меня есть набор структур данных, которые напоминают deque которые на самом деле на одном уровне с последовательной итерацией vector (все еще заметно медленнее для произвольного доступа, особенно если мы просто храним кучу примитивов и выполняем тривиальную обработку). Однако для достижения сопоставимого времени vector для последовательной итерации мне пришлось использовать эти методы (for_each метод и двойные / вложенные итераторы), чтобы уменьшить объем обработки и ветвления, происходящих в каждой итерации. Я не мог бы соперничать со временем, используя только плоский дизайн итератора и / или operator[], И я, конечно, не умнее, чем разработчики стандартной библиотеки, но придумали deque -подобный контейнер, который может быть последовательно итерирован гораздо быстрее, и это убедительно подсказывает мне, что это проблема со стандартным дизайном интерфейса итераторов в этом случае, которые идут с некоторыми накладными расходами в этих специфических случаях, которые оптимизатор не может оптимизировать.
Старый ответ
Я один из тех, кто даст вам аналогичный ответ по производительности, но я постараюсь дать вам что-то более глубокое, чем "just because", Это то, с чем я столкнулся через фактическое профилирование и выбор времени, а не просто недоверие и паранойя.
Одна из самых больших проблем с bitset а также vector<bool> является то, что их дизайн интерфейса "слишком удобно", если вы хотите использовать их как массив логических значений. Оптимизаторы отлично справляются со всей той структурой, которую вы создаете, чтобы обеспечить безопасность, снизить затраты на обслуживание, сделать изменения менее навязчивыми и т. Д. Они особенно хорошо справляются с выбором инструкций и выделением минимального количества регистров, чтобы такой код выполнялся так же быстро, как не слишком безопасные, не очень простые в обслуживании / изменить альтернативы.
Частью, которая делает интерфейс набора битов "слишком удобным" за счет эффективности, является произвольный доступ operator[] а также дизайн итератора для vector<bool>, Когда вы получаете доступ к одному из них по индексу n код должен сначала выяснить, какому байту принадлежит n-й бит, а затем субиндекс для этого бита. Эта первая фаза обычно включает в себя деление / смещение по l-значению вместе с модулем / битом, что обходится дороже, чем фактическая битовая операция, которую вы пытаетесь выполнить.
Дизайн итератора для vector<bool> сталкивается с подобной неловкой дилеммой, когда он должен либо переходить в другой код каждые 8+ раз, когда вы итерируете его, либо платить такую стоимость индексации, как описано выше. Если первое будет выполнено, логика будет асимметричной на разных итерациях, и в тех редких случаях конструкции итераторов имеют тенденцию к снижению производительности. В качестве примера, если vector был for_each своего собственного метода, вы можете перебирать, скажем, диапазон из 64 элементов одновременно, просто маскируя биты по отношению к 64-битной маске для vector<bool> если все биты установлены без проверки каждого бита в отдельности. Он может даже использовать FFS, чтобы определить диапазон сразу. Конструкция итератора неизбежно должна была бы делать это скалярным образом или хранить больше состояний, которые должны быть избыточно проверены на каждой итерации.
Что касается произвольного доступа, оптимизаторы не могут оптимизировать эти издержки индексации, чтобы выяснить, к какому байту и относительному биту обращаться (возможно, слишком зависит от времени выполнения), когда он не нужен, и вы, как правило, видите значительное увеличение производительности с этим более ручная обработка битов кода последовательно с углубленным знанием того, над каким байтом / словом / словом / словом он работает. Это отчасти несправедливое сравнение, но сложность с std::bitset в том, что нет никакого способа сделать справедливое сравнение в тех случаях, когда код знает заранее, к какому байту он хочет получить доступ, и чаще всего вы склонны иметь эту информацию заранее. В случае с произвольным доступом это сравнение яблок и апельсинов, но вам часто нужны только апельсины.
Возможно, это было бы не так, если бы дизайн интерфейса bitset где operator[] вернул прокси, требующий двухиндексный шаблон доступа для использования. Например, в таком случае вы бы получили доступ к биту 8, написав bitset[0][6] = true; bitset[0][7] = true; с параметром шаблона, чтобы указать размер прокси (например, 64-бит). Хороший оптимизатор может быть в состоянии взять такой дизайн и заставить его соперничать с руководством, старой школой как способ манипуляции битами вручную, переводя его в: bitset |= 0x60;
Другой дизайн, который может помочь, если bitsets при условии for_each_bit метод передачи небольшого прокси функтору, который вы предоставляете. Это может на самом деле быть в состоянии конкурировать с ручным методом.
std::deque имеет похожую проблему интерфейса. Его производительность не должна быть намного медленнее, чем std::vector для последовательного доступа. Тем не менее, к сожалению, мы получаем к нему доступ последовательно operator[] который предназначен для произвольного доступа или через итератор, а внутренний представитель запросов просто не очень эффективно сопоставляется с дизайном на основе итератора. Если deque предоставил for_each своего рода метод, то там он может потенциально стать намного ближе к std::vector's производительность последовательного доступа. Это некоторые из редких случаев, когда дизайн интерфейса Sequence сопряжен с некоторыми издержками эффективности, которые оптимизаторы часто не могут уничтожить. Зачастую хорошие оптимизаторы могут обеспечить удобство работы без затрат времени выполнения в производственной сборке, но, к сожалению, не во всех случаях.
Сожалею!
Также извините, оглядываясь назад, я немного побрел с этим постом, говоря о vector<bool> а также deque в дополнение к bitset, Это потому, что у нас была кодовая база, где использование этих трех, и особенно их повторение или использование их с произвольным доступом, часто были горячими точками.
Яблоки в апельсины
Как подчеркивалось в старом ответе, сравнивая прямое использование bitset Для примитивных типов с низкоуровневой побитовой логикой идет сравнение яблок с апельсинами. Это не как bitset реализован очень неэффективно для того, что он делает. Если вам действительно необходим доступ к группе битов с шаблоном произвольного доступа, который по тем или иным причинам должен проверять и устанавливать только один бит за раз, то он может быть идеально реализован для такой цели. Но я хочу сказать, что почти во всех случаях использования, с которыми я сталкивался, этого не требовалось, а когда это не требуется, старый метод, включающий побитовые операции, имеет тенденцию быть значительно более эффективным.
Сделал короткий тест профилирования массивов std::bitset и bool для последовательного и произвольного доступа - вы тоже можете:
#include <iostream>
#include <bitset>
#include <cstdlib> // rand
#include <ctime> // timer
inline unsigned long get_time_in_ms()
{
return (unsigned long)((double(clock()) / CLOCKS_PER_SEC) * 1000);
}
void one_sec_delay()
{
unsigned long end_time = get_time_in_ms() + 1000;
while(get_time_in_ms() < end_time)
{
}
}
int main(int argc, char **argv)
{
srand(get_time_in_ms());
using namespace std;
bitset<5000000> bits;
bool *bools = new bool[5000000];
unsigned long current_time, difference1, difference2;
double total;
one_sec_delay();
total = 0;
current_time = get_time_in_ms();
for (unsigned int num = 0; num != 200000000; ++num)
{
bools[rand() % 5000000] = rand() % 2;
}
difference1 = get_time_in_ms() - current_time;
current_time = get_time_in_ms();
for (unsigned int num2 = 0; num2 != 100; ++num2)
{
for (unsigned int num = 0; num != 5000000; ++num)
{
total += bools[num];
}
}
difference2 = get_time_in_ms() - current_time;
cout << "Bool:" << endl << "sum total = " << total << ", random access time = " << difference1 << ", sequential access time = " << difference2 << endl << endl;
one_sec_delay();
total = 0;
current_time = get_time_in_ms();
for (unsigned int num = 0; num != 200000000; ++num)
{
bits[rand() % 5000000] = rand() % 2;
}
difference1 = get_time_in_ms() - current_time;
current_time = get_time_in_ms();
for (unsigned int num2 = 0; num2 != 100; ++num2)
{
for (unsigned int num = 0; num != 5000000; ++num)
{
total += bits[num];
}
}
difference2 = get_time_in_ms() - current_time;
cout << "Bitset:" << endl << "sum total = " << total << ", random access time = " << difference1 << ", sequential access time = " << difference2 << endl << endl;
delete [] bools;
cin.get();
return 0;
}
Обратите внимание: вывод итоговой суммы необходим, чтобы компилятор не оптимизировал цикл for - что делают некоторые, если результат цикла не используется.
Под GCC x64 со следующими флагами: -O2;-Wall;-march=native;-fomit-frame-pointer;-std= C++11; Я получаю следующие результаты:
Bool массив: время произвольного доступа = 4695, время последовательного доступа = 390
Битовый набор: время произвольного доступа = 5382, время последовательного доступа = 749
Не очень хороший ответ, а скорее похожий анекдот:
Несколько лет назад я работал над программным обеспечением в реальном времени, и мы столкнулись с проблемами планирования. Был модуль, который занимал гораздо больше времени, и это было очень удивительно, потому что модуль отвечал только за некоторое отображение и упаковку / распаковку битов в / из 32-битных слов.
Оказалось, что модуль использует std::bitset. Мы заменили это на ручные операции, и время выполнения сократилось с 3 миллисекунд до 25 микросекунд. Это было серьезной проблемой производительности и значительным улучшением.
Дело в том, что проблемы с производительностью, вызванные этим классом, могут быть очень реальными.
В дополнение к тому, что в других ответах говорится о производительности доступа, также могут быть значительные издержки пространства: типичный bitset<> Реализации просто используют самый длинный целочисленный тип для поддержки своих битов. Таким образом, следующий код
#include <bitset>
#include <stdio.h>
struct Bitfield {
unsigned char a:1, b:1, c:1, d:1, e:1, f:1, g:1, h:1;
};
struct Bitset {
std::bitset<8> bits;
};
int main() {
printf("sizeof(Bitfield) = %zd\n", sizeof(Bitfield));
printf("sizeof(Bitset) = %zd\n", sizeof(Bitset));
printf("sizeof(std::bitset<1>) = %zd\n", sizeof(std::bitset<1>));
}
производит следующий вывод на моей машине:
sizeof(Bitfield) = 1
sizeof(Bitset) = 8
sizeof(std::bitset<1>) = 8
Как видите, мой компилятор выделяет колоссальные 64 бита для хранения одного, при использовании подхода с битовыми полями мне нужно только округлить до восьми бит.
Этот фактор восемь в использовании пространства может стать важным, если у вас много маленьких битрейтов.
Риторический вопрос: почему std::bitset написано таким образом неэффективности? Ответ: это не так.
Еще один риторический вопрос: в чем разница между:
std::bitset<128> a = src;
a[i] = true;
a = a << 64;
а также
std::bitset<129> a = src;
a[i] = true;
a = a << 63;
Ответ: разница в производительности в 50 раз http://quick-bench.com/iRokweQ6JqF2Il-T-9JSmR0bdyw
Вы должны быть очень осторожны, что вы просите, bitset Поддержка много вещей, но каждый имеет свою цену. При правильной обработке у вас будет точно такое же поведение, что и у необработанного кода:
void f(std::bitset<64>& b, int i)
{
b |= 1L << i;
b = b << 15;
}
void f(unsigned long& b, int i)
{
b |= 1L << i;
b = b << 15;
}
Оба генерируют одну и ту же сборку: https://godbolt.org/g/PUUUyd (64-битный GCC)
Другое дело, что bitset является более портативным, но это тоже стоит:
void h(std::bitset<64>& b, unsigned i)
{
b = b << i;
}
void h(unsigned long& b, unsigned i)
{
b = b << i;
}
Если i > 64 тогда бит будет установлен равным нулю, а в случае без знака у нас будет UB.
void h(std::bitset<64>& b, unsigned i)
{
if (i < 64) b = b << i;
}
void h(unsigned long& b, unsigned i)
{
if (i < 64) b = b << i;
}
С проверкой, предотвращающей UB, оба генерируют один и тот же код.
Другое место set а также []Во-первых, это безопасно и означает, что вы никогда не получите UB, но это будет стоить вам филиала. [] есть UB, если вы используете неправильное значение, но быстро, как при использовании var |= 1L<< i;, Конечно, если std::bitset не нужно иметь больше битов, чем самый большой int, доступный в системе, потому что в противном случае вам нужно разделить значение, чтобы получить правильный элемент во внутренней таблице. Это значит для std::bitset<N> размер N очень важно для производительности. Если он больше или меньше оптимального, вы заплатите за него.
В целом, я считаю, что лучше всего использовать что-то вроде этого:
constexpr size_t minBitSet = sizeof(std::bitset<1>)*8;
template<size_t N>
using fasterBitSet = std::bitset<minBitSet * ((N + minBitSet - 1) / minBitSet)>;
Это снимет стоимость обрезки превышающих битов: http://quick-bench.com/Di1tE0vyhFNQERvucAHLaOgucAY