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

Ответ 1

Обновление

Прошло столько времени с тех пор, как я разместил это, но:

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

Если вы используете 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 (все еще заметно медленнее для случайных -access, особенно если мы просто храним кучу примитивов и делаем тривиальную обработку). Однако для достижения сопоставимых времен до 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 реализовано очень неэффективно для того, что он делает. Если вам действительно нужно получить доступ к кучке битов со случайным шаблоном доступа, который по какой-то причине или по-другому должен проверять и устанавливать только один бит времени, тогда он может быть идеально реализован для такой цели. Но я считаю, что почти все случаи использования, с которыми я столкнулся, не требовали этого, и когда это не требуется, старый способ школы, включающий побитовые операции, имеет тенденцию быть значительно более эффективным.

Ответ 2

Произошло короткое тестовое профилирование std:: bitset vs 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 = С++ 11; Я получаю следующие результаты:

массив Bool: время произвольного доступа = 4695, время последовательного доступа = 390

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

Ответ 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 бита для хранения одного, с подходом битового поля, мне нужно всего лишь округлить до восьми бит.

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

Ответ 4

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

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

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

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

Ответ 5

Риторический вопрос: почему 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> size 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