С++ 11 проблема с производительностью <bool> (с примером кода)

Я заметил, что вектор работает намного медленнее, чем массив bool при запуске следующего кода.

int main() 
{
    int count = 0;
    int n = 1500000;
    // slower with c++ vector<bool>
    /*vector<bool> isPrime;
    isPrime.reserve(n);
    isPrime.assign(n, true);
    */
    // faster with bool array 
    bool* isPrime = new bool[n];

    for (int i = 0; i < n; ++i)
        isPrime[i] = true;


    for (int i = 2; i< n; ++i) {
        if (isPrime[i])
            count++;
        for (int j =2; i*j < n; ++j )
            isPrime[i*j] = false;
    }

    cout <<  count << endl;
    return 0;
}

Есть ли способ, который я могу сделать, чтобы сделать vector<bool> быстрее? Btw, как std::vector::push_back, так и std::vector::emplace_back еще медленнее, чем std::vector::assign.

Ответ 1

vector<bool> может иметь специализацию шаблона и может быть реализован с использованием битового массива для экономии места. Извлечение и сохранение бит и преобразование его из/в bool может привести к падению производительности, которое вы наблюдаете. Если вы используете std::vector::push_back, вы изменяете размер вектора, который приведет к еще худшей производительности. Следующий убийца производительности может быть assign (Худшая сложность: Линейный первый аргумент), вместо этого используйте operator [] (Сложность: константа).

С другой стороны, bool [] гарантированно является массивом bool.

И вы должны изменить размер до n вместо n-1, чтобы избежать поведения undefined.

Ответ 2

std::vector<bool> может иметь различные проблемы с производительностью (например, посмотрите https://isocpp.org/blog/2012/11/on-vectorbool).

В общем вы можете:

используйте std::vector<std::uint8_t> вместо std::vector<bool> (попробуйте std::valarray<bool> также.)

Для этого требуется больше памяти и меньше кэш-памяти, но для доступа к одному значению нет накладных расходов (в виде манипуляций с битами), поэтому есть ситуации, в которых он работает лучше (в конце концов, это похоже на ваш массив bool, но без вреда управления памятью)
используйте std::bitset, если во время компиляции вы знаете, насколько велик ваш логический массив (или если вы можете хотя бы установить разумная верхняя граница)
Если Boost является опцией try boost::dynamic_bitset (размер может быть указан во время выполнения)

Но для оптимизации скорости вам нужно проверить...

В вашем конкретном примере я могу подтвердить разницу в производительности только тогда, когда оптимизация отключена (конечно, это не путь).

Некоторые тесты с g++ v4.8.3 и clang++ v3.4.5 в системе Intel Xeon (уровень оптимизации -O3) дают другое изображение:

                    time (ms)
                 G++      CLANG++
array of bool    3103     3010
vector<bool>     2835     2420    // not bad!
vector<char>     3136     3031    // same as array of bool
bitset           2742     2388    // marginally better

(время, прошедшее за 100 прогонов кода в ответе)

std::vector<bool> не выглядит так плохо (исходный код здесь).

Ответ 3

vector<bool> может быть высокой, но не обязательно. Для того чтобы vector<bool> был эффективным, он должен работать на многих баллах одновременно (например, isPrime.assign(n, true)), и разработчику пришлось вложить в него любящую заботу. Индексирование отдельных bools в vector<bool> происходит медленно.

Вот основной поиск, который я написал некоторое время назад, используя vector<bool> и clang + libС++ (важна часть libС++):

#include <algorithm>
#include <chrono>
#include <iostream>
#include <vector>

std::vector<bool>
init_primes()
{
    std::vector<bool> primes(0x80000000, true);
    primes[0] = false;
    primes[1] = false;
    const auto pb = primes.begin();
    const auto pe = primes.end();
    const auto sz = primes.size();
    size_t i = 2;
    while (true)
    {
        size_t j = i*i;
        if (j >= sz)
            break;
        do
        {
            primes[j] = false;
            j += i;
        } while (j < sz);
        i = std::find(pb + (i+1), pe, true) - pb;
    }
    return primes;
}

int
main()
{
    using namespace std::chrono;
    using dsec = duration<double>;
    auto t0 = steady_clock::now();
    auto p = init_primes();
    auto t1 = steady_clock::now();
    std::cout << dsec(t1-t0).count() << "\n";
}

Это выполняется для меня примерно за 28 секунд (-O3). Когда я меняю его, чтобы вернуть vector<char>, время выполнения увеличивается примерно до 44.

Если вы запустите это, используя некоторые другие std:: lib, вы, вероятно, не увидите эту тенденцию. В libС++ алгоритмы, такие как std::find, были оптимизированы для поиска слова бит за раз, а не бит за раз.

Подробнее о том, какие алгоритмы std могут быть оптимизированы вашим поставщиком, см. http://howardhinnant.github.io/onvectorbool.html.