Разрыв в производительности между вектором <bool> и массивом

Ответ 1

std::vector<bool> не похож на любой другой вектор. В документации сказано:

std::vector<bool> является, возможно, пространственно-эффективной специализацией std::vector для типа bool.

Вот почему он может использовать меньше памяти, чем массив, потому что он может представлять несколько логических значений одним байтом, как битовый набор. Это также объясняет разницу в производительности, так как доступ к ней уже не так прост. Согласно документации, ему даже не нужно хранить его как непрерывный массив.

Ответ 2

std::vector<bool> является особым случаем. Это специализированный шаблон. Каждое значение хранится в одном бите, поэтому необходимы битовые операции. Эта память компактна, но имеет пару недостатков (например, нет способа иметь указатель на bool внутри этого контейнера).

Теперь bool flag[n+1]; компилятор обычно выделяет ту же память тем же способом, что и для char flag[n+1]; и он будет делать это в стеке, а не в куче.

Теперь, в зависимости от размеров страницы, пропусков кэша и значений i одно может быть быстрее другого. Трудно предсказать (для маленьких n массив будет быстрее, но для больших n результат может измениться).

В качестве интересного эксперимента вы можете изменить std::vector<bool> на std::vector<char>. В этом случае у вас будет такое же отображение памяти, как и в случае с массивом, но оно будет находиться в куче, а не в стеке.

Ответ 3

Я хотел бы добавить некоторые замечания к хорошим ответам, уже опубликованным.

• Различия в производительности между std::vector<bool> и std::vector<char> могут сильно отличаться для разных реализаций библиотеки и разных размеров векторов.

  См., Например, эти быстрые скамейки: clang++/libc++ (LLVM) против g++/libstdc++ (GNU).

• Это: bool flag[n+1]; объявляет массив переменной длины, который (несмотря на некоторые преимущества в производительности из-за его размещения в стеке) никогда не был частью стандарта C++, даже если он предоставляется в качестве расширения некоторыми (совместимыми с C99) компиляторами.

• Другим способом повышения производительности может быть уменьшение количества вычислений (и занимаемой памяти) путем рассмотрения только нечетных чисел, учитывая, что все простые числа, кроме 2, являются нечетными.

Если вы можете обнажить менее читаемый код, вы можете попытаться профилировать следующий фрагмент.

int countPrimes(int n)
{
    if ( n < 2 )
        return 0;
    // Sieve starting from 3 up to n, the number of odd number between 3 and n are
    int sieve_size = n / 2 - 1;
    std::vector<char> sieve(sieve_size); 
    int result = 1;  // 2 is a prime.

    for (int i = 0; i < sieve_size; ++i)
    {
        if ( sieve[i] == 0 )
        {
            // It a prime, no need to scan the vector again
            ++result;
            // Some ugly transformations are needed, here
            int prime = i * 2 + 3;
            for ( int j = prime * 3, k = prime * 2; j <= n; j += k)
                sieve[j / 2 - 1] = 1;
        }
    }

    return result;
}

редактировать

Как заметил в комментариях Питер Кордес, используя тип без знака для переменной j

Компилятор может реализовать J/2 как можно дешевле. C знаковое деление степени 2 имеет другую семантику округления (для отрицательных дивидендов), чем сдвиг вправо, и компиляторы не всегда распространяют доказательства диапазона значений в достаточной степени, чтобы доказать, что j всегда будет неотрицательным.

Также возможно уменьшить количество кандидатов, использующих тот факт, что все простые числа (последние 2 и 3) равны одному ниже или выше кратному 6.

Ответ 4

Я получаю другие тайминги и использование памяти, чем те, которые упомянуты в вопросе при компиляции с g++-7.4.0 -g -march=native -O2 -Wall и работает на процессоре Ryzen 5 1600:

• vector<bool>: 0,038 секунды, память 3344 КиБ, IPC 3,16
• vector<char>: 0,048 секунды, память 12004 КиБ, IPC 1,52
• bool[N]: 0,050 секунды, 12644 КБ памяти, IPC 1,69

Вывод: vector<bool> - самый быстрый вариант из-за его более высокого IPC (количество команд за такт).

#include <stdio.h>
#include <stdlib.h>
#include <sys/resource.h>
#include <vector>

size_t countPrimes(size_t n) {
    std::vector<bool> flag(n+1,1);
    //std::vector<char> flag(n+1,1);
    //bool flag[n+1]; std::fill(flag,flag+n+1,true);
    for(size_t i=2;i<n;i++) {
        if(flag[i]==1) {
            for(size_t j=i;i*j<n;j++) {
                flag[i*j]=0;
            }
        }
    }
    size_t result=0;
    for(size_t i=2;i<n;i++) {
        result+=flag[i];
    }
    return result;
}

int main() {
    {
        const rlim_t kStackSize = 16*1024*1024; 
        struct rlimit rl;
        int result = getrlimit(RLIMIT_STACK, &rl);
        if(result != 0) abort();
        if(rl.rlim_cur < kStackSize) {
            rl.rlim_cur = kStackSize;
            result = setrlimit(RLIMIT_STACK, &rl);
            if(result != 0) abort();
        }
    }

    printf("%zu\n", countPrimes(10e6));
    return 0;
}