Какова производительность std :: bitset?

Question

Я недавно задал вопрос о Programmers относительно причин использования ручных бит-манипуляций с примитивными типами над std::bitset.

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

Вопрос умышленно широкий, потому что после поиска в Интернете я ничего не смог найти, поэтому я возьму то, что смогу получить. В основном я получаю ресурс, который предоставляет некоторое профилирование std::bitset vs 'pre-bitset' альтернативы тем же проблемам на некоторой общей машинной архитектуре с использованием GCC, Clang и/или VC++. Существует весьма всеобъемлющий документ, который attemtps ответить на этот вопрос для битовых векторов:

http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf

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

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

Answer 1

Update

Прошло очень много времени, так как я отправил это одно, но:

Я уже знаю, что это проще и яснее, чем бит пустячный на целое, но это, как быстро?

Если вы используете 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) и BitSet мог определить, что с одной инструкции побитового в какой момент мы можем перебрать все заданные биты и тогда мы закончили.

Этот тип вложенного дизайна итератора будет особенно хорошо отображаться на vector<bool>, deque и bitset, а также на другие структуры данных, которые люди могут создавать как развернутые списки.

Я говорю, что в некотором смысле, который выходит за рамки просто кресло спекуляции, так как у меня есть набор структур данных, которые напоминают подобных deque, которые на самом деле на одном уровне с последовательной итерации vector (по-прежнему заметно медленнее произвольным доступом, особенно если мы просто храним кучу примитивов и делаем тривиальную обработку). Однако для достижения сопоставимых времен до vector для последовательной итерации мне пришлось использовать эти типы методов (метод for_each и двойные/вложенные итераторы), чтобы уменьшить объем обработки и разветвления на каждой итерации. Я не мог соперничать с другими временами, используя только плоскую конструкцию итератора и/или operator[]. И я, конечно, не умнее, чем стандартные разработчики библиотек, но придумал контейнер размером deque, который может быть последовательно повторен гораздо быстрее, и это говорит мне о том, что в этом случае проблема со стандартным дизайном итераторов интерфейса, приходят с некоторыми накладными расходами в этих особых случаях, которые оптимизатор не может оптимизировать.

Старый Ответ

Я один из тех, кто хотел бы дать вам подобный ответ производительности, но я постараюсь дать вам что-то немного более глубокий, чем "just because". Это то, что я натолкнулся на фактическое профилирование и время, а не просто на недоверие и паранойю.

Одна из самых больших проблем с bitset и vector<bool> заключается в том, что их дизайн интерфейса «слишком удобен», если вы хотите использовать их как массив булевых. Оптимизаторы отлично справляются со всей структурой, которую вы создаете, чтобы обеспечить безопасность, снизить затраты на обслуживание, сделать изменения менее навязчивыми и т. Д. Они выполняют особенно прекрасную работу по выбору инструкций и распределению минимального количества регистров, чтобы такой код работал так быстро, как не столь безопасные, не очень простые в обслуживании/изменения альтернативы.

Часть, которая делает интерфейс битета «слишком удобным» за счет эффективности, - это случайный доступ operator[], а также дизайн итератора для vector<bool>. Когда вы обращаетесь к одному из них по индексу n, код должен сначала определить, к какому байту принадлежит n-й бит, а затем к подиндексу к этому биту. Эта первая фаза обычно включает в себя разделение/rshifts против lvalue вместе с модулем/побитовым и которое является более дорогостоящим, чем фактическая операция бит, которую вы пытаетесь выполнить.

Конструкция итератора для vector<bool> сталкивается с подобной неловкой дилеммой, где она либо должна входить в разный код каждые 8+ раз, когда вы перебираете ее или оплачиваете такую ​​стоимость индексации, описанную выше. Если первое сделано, это делает логику асимметричной по итерациям, и конструкции итератора имеют тенденцию к быстрому результату в тех редких случаях. Например, если vector имеет собственный метод for_each, вы можете перебирать, скажем, диапазон из 64 элементов сразу, просто маскируя биты против 64-разрядной маски для vector<bool>, если все биты установлены без проверки каждого бита индивидуально. Он может даже использовать FFS, чтобы разобраться в диапазоне все сразу. Конструкция итератора неизбежно должна была бы сделать это скалярным способом или сохранить больше состояния, которое должно быть избыточно проверено на каждой итерации.

Для случайного доступа оптимизаторы не могут оптимизировать эти служебные данные индексации, чтобы выяснить, какой байт и относительный бит для доступа (возможно, слишком зависимые от времени выполнения), когда это не требуется, и вы склонны видеть значительную производительность выигрывает с этим более ручным битом обработки кода последовательно с расширенным знанием того, в каком байте/слове/dword/qword он работает.Это несколько несправедливое сравнение, но сложность с 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[], который предназначен для случайного доступа или через итератор, а внутренняя репутация deqes просто не очень эффективно сопоставляется с дизайном на основе итератора. Если deque предоставил собственный метод for_each, тогда он мог бы начать намного приближаться к производительности последовательного доступа std::vector's. Это некоторые из редких случаев, когда дизайн интерфейса Sequence поставляется с некоторыми издержками эффективности, которые оптимизаторы часто не могут стереть. Часто хорошие оптимизаторы могут упростить доступ к стоимости исполнения в сборке, но, к сожалению, не во всех случаях.

Извините!

Также жаль, оглядываясь назад, я побродил немного с этим после говорить о vector<bool> и deque в дополнение к bitset. Это потому, что у нас была кодовая база, где использование этих трех, и особенно их повторение или использование их со случайным доступом, часто были горячими точками.

Яблоки Апельсины

Как подчеркивалось в старом ответ, сравнивая прямое использование bitset для примитивных типов с побитового логики низкого уровня сравнивает яблоки с апельсинами. Это не так, как bitset реализовано очень неэффективно для того, что он делает. Если вам действительно нужно получить доступ к кучке битов со случайным шаблоном доступа, который по какой-то причине или по-другому должен проверять и устанавливать только один бит времени, тогда он может быть идеально реализован для такой цели. Но я хочу сказать, что почти все случаи использования, которые я встречал, не требовали этого, и когда это не требуется, старая школьная дорога, включающая побитовые операции, имеет тенденцию быть значительно более эффективной.

Answer 2

ли короткий тест профилирования зОго :: 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

BITSET: случайное время доступа = 5382, последовательное время доступа = 749

Answer 3

В дополнение к тому, что другие ответы говорят об эффективности доступа, также могут быть значительные накладные расходы: типичные реализации 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 бит для хранения одного, с битовом подходом, я требуется округлить до восьми бит.

Этот фактор восемь в использовании пространства может стать важным, если у вас много маленьких битов.

Answer 4

Не большой ответ здесь, а родственный анекдот:

Несколько лет назад я работал в режиме реального времени, программное обеспечение, и мы столкнулись с проблемами планирования. Был модуль, который был по сравнению с временным бюджетом, и это было очень удивительно, потому что модуль отвечал только за сопоставление и упаковку/распаковку битов в/из 32-битных слов.

Оказалось, что модуль использует std :: bitset. Мы заменили его на ручные операции, и время выполнения уменьшилось с 3 миллисекунд до 25 микросекунд. Это была значительная проблема с производительностью и значительное улучшение.

Дело в том, что проблемы с производительностью, вызванные этим классом, могут быть очень реальными.