Вектор C ++ 11 & lt; bool & gt; проблема производительности (с примером кода)

Question

Вектор C ++ 11 & lt; bool & gt; проблема производительности (с примером кода)

Я заметил, что vector намного медленнее, чем массив 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> Быстрее ? Кстати, оба std::vector::push_back а также std::vector::emplace_back даже медленнее, чем std::vector::assign,

21

bitvector c++c++11 performance vector

Решение

Другие решения

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

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

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

10

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

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

#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, вы, вероятно, не увидите эту тенденцию. На алгоритмах libc ++, таких как std::find были оптимизированы для поиска слова бит за раз, а не бит за раз.

Увидеть http://howardhinnant.github.io/onvectorbool.html для получения более подробной информации о том, какие алгоритмы STD могут быть оптимизированы вашим поставщиком.

3

Источник

Accepted Answer

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, попробуйте 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> выглядит не так уж плохо (исходный код Вот).

13