c++ - guia - qgis español

C++ 11 vector<bool> problema de rendimiento(con ejemplo de código)

Question

Noté que el vector es mucho más lento que el arreglo bool cuando se ejecuta el siguiente código.

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;
}

¿Hay alguna manera en que pueda hacer para que vector<bool> más rápido? Por cierto, tanto std::vector::push_back como std::vector::emplace_back son incluso más lentos que std::vector::assign .

Answer 1

std::vector<bool> puede tener varios problemas de rendimiento (por ejemplo, visite https://isocpp.org/blog/2012/11/on-vectorbool ).

En general puedes:

• use std::vector<std::uint8_t> lugar de std::vector<bool> (pruebe también a std::valarray<bool> ).

  Esto requiere más memoria y es menos compatible con la memoria caché, pero no hay una sobrecarga (en forma de manipulación de bits) para acceder a un solo valor, por lo que hay situaciones en las que funciona mejor (después de todo, es como su matriz de bool pero sin la molestia de la gestión de memoria)

• use std::bitset si sabe en el momento de la compilación el tamaño de su matriz booleana (o si al menos puede establecer un límite superior razonable)
• si Boost es una opción, pruebe boost::dynamic_bitset (el tamaño puede especificarse en tiempo de ejecución)

Pero para las optimizaciones de velocidad tienes que probar ...

Con su ejemplo específico, puedo confirmar una diferencia de rendimiento solo cuando las optimizaciones están desactivadas (por supuesto, este no es el camino a seguir).

Algunas pruebas con g ++ v4.8.3 y clang ++ v3.4.5 en un sistema Intel Xeon (nivel de optimización -O3 ) dan una imagen diferente:

                    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

(tiempo transcurrido para 100 ejecuciones del código en la respuesta)

std::vector<bool> no se ve tan mal (código fuente here ).

Answer 2

vector<bool> puede ser de alto rendimiento, pero no es obligatorio que lo sea. Para que vector<bool> sea ​​eficiente, debe operar en muchos bools a la vez (por ejemplo, isPrime.assign(n, true) ), y el implementador ha tenido que poner cuidado en él. La indexación de bools individuales en un vector<bool> es lenta.

Aquí hay un buscador principal que escribí hace un tiempo usando vector<bool> y clang + libc ++ (la parte de libc ++ es importante):

#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";
}

Esto se ejecuta para mí en unos 28s (-O3). Cuando lo cambio para devolver un vector<char> lugar, el tiempo de ejecución sube a unos 44 segundos.

Si ejecuta esto usando algún otro std :: lib, probablemente no verá esta tendencia. En libc ++, los algoritmos como std::find se han optimizado para buscar una palabra de bits a la vez, en lugar de bits a la vez.

Consulte http://howardhinnant.github.io/onvectorbool.html para obtener más detalles sobre qué algoritmos estándar podrían ser optimizados por su proveedor.

Answer 3

vector<bool> puede tener una especialización de plantilla y puede implementarse utilizando una matriz de bits para ahorrar espacio. Extraer y guardar un poco y convertirlo de / a bool puede causar la caída del rendimiento que está observando. Si usa std::vector::push_back , está redimensionando el vector, lo que causará un rendimiento aún peor. El siguiente asesino de rendimiento se puede assign (Peor complejidad: lineal del primer argumento), en su lugar, utilice el operator [] (Complejidad: constante).

Por otro lado, bool [] está garantizado como matriz de bool .

Y debe cambiar el tamaño a n lugar de n-1 para evitar un comportamiento indefinido.