¿Es std::vector mucho más lento que las matrices simples?

Siempre he pensado que es la sabiduría general la que std::vectorse "implementa como una matriz", bla, bla, bla. Hoy bajé y lo probé, y parece que no es así:

Aquí hay algunos resultados de las pruebas:

UseArray completed in 2.619 seconds
UseVector completed in 9.284 seconds
UseVectorPushBack completed in 14.669 seconds
The whole thing completed in 26.591 seconds

¡Eso es entre 3 y 4 veces más lento! Realmente no justifica los vectorcomentarios de "puede ser más lento durante unos pocos nanosegundos".

Y el código que utilicé:

#include <cstdlib>
#include <vector>

#include <iostream>
#include <string>

#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>

class TestTimer
{
    public:
        TestTimer(const std::string & name) : name(name),
            start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
        {
        }

        ~TestTimer()
        {
            using namespace std;
            using namespace boost;

            posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
            posix_time::time_duration d = now - start;

            cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
                " seconds" << endl;
        }

    private:
        std::string name;
        boost::posix_time::ptime start;
};

struct Pixel
{
    Pixel()
    {
    }

    Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
    {
    }

    unsigned char r, g, b;
};

void UseVector()
{
    TestTimer t("UseVector");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
        pixels.resize(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPushBack");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
            pixels.reserve(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
            pixels.push_back(Pixel(255, 0, 0));
    }
}

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);

        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }

        free(pixels);
    }
}

int main()
{
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();
    UseVectorPushBack();

    return 0;
}

¿Lo estoy haciendo mal o algo así? ¿O acabo de romper con este mito del rendimiento?

Estoy usando el modo de lanzamiento en Visual Studio 2005 .

En Visual C++ , #define _SECURE_SCL 0se reduce UseVectora la mitad (reduciéndolo a 4 segundos). Esto es realmente enorme, en mi opinión.

Sep 08 '10 09:09 kizzx2

Gran pregunta. Vine aquí esperando encontrar alguna solución simple que acelerara las pruebas de vectores. ¡Eso no funcionó como esperaba!

La optimización ayuda, pero no es suficiente. Con la optimización activada, sigo viendo una diferencia de rendimiento 2 veces mayor entre UseArray y UseVector. Curiosamente, UseVector fue significativamente más lento que UseVectorPushBack sin optimización.

# g++ -Wall -Wextra -pedantic -o vector vector.cpp
# ./vector
UseArray completed in 20.68 seconds
UseVector completed in 120.509 seconds
UseVectorPushBack completed in 37.654 seconds
The whole thing completed in 178.845 seconds
# g++ -Wall -Wextra -pedantic -O3 -o vector vector.cpp
# ./vector
UseArray completed in 3.09 seconds
UseVector completed in 6.09 seconds
UseVectorPushBack completed in 9.847 seconds
The whole thing completed in 19.028 seconds

Idea n.º 1: utilizar nuevo[] en lugar de malloc

Intenté cambiar malloc()a new[]UseArray para que los objetos se construyeran. Y pasar de la asignación de campos individuales a la asignación de una instancia de Pixel. Ah, y cambiar el nombre de la variable del bucle interno a j.

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {   
        int dimension = 999;

        // Same speed as malloc().
        Pixel * pixels = new Pixel[dimension * dimension];

        for(int j = 0 ; j < dimension * dimension; ++j)
            pixels[j] = Pixel(255, 0, 0);

        delete[] pixels;
    }
}

Sorprendentemente (para mí), ninguno de esos cambios marcó ninguna diferencia. Ni siquiera el cambio por new[]el que se construirán de forma predeterminada todos los Píxeles. Parece que gcc puede optimizar las llamadas al constructor predeterminado cuando se usa new[], pero no cuando se usa vector.

Idea n.º 2: eliminar llamadas repetidas al operador[]

También intenté deshacerme de la operator[]búsqueda triple y almacenar en caché la referencia a pixels[j]. ¡Eso en realidad ralentizó UseVector! Ups.

for(int j = 0; j < dimension * dimension; ++j)
{
    // Slower than accessing pixels[j] three times.
    Pixel &pixel = pixels[j];
    pixel.r = 255;
    pixel.g = 0;
    pixel.b = 0;
}

# ./vector 
UseArray completed in 3.226 seconds
UseVector completed in 7.54 seconds
UseVectorPushBack completed in 9.859 seconds
The whole thing completed in 20.626 seconds

Idea n.º 3: eliminar constructores

¿Qué tal si eliminamos los constructores por completo? Entonces quizás gcc pueda optimizar la construcción de todos los objetos cuando se crean los vectores. ¿Qué pasa si cambiamos Pixel a:

struct Pixel
{
    unsigned char r, g, b;
};

Resultado: aproximadamente un 10% más rápido. Aún más lento que una matriz. Mmm.

# ./vector 
UseArray completed in 3.239 seconds
UseVector completed in 5.567 seconds

Idea n.º 4: utilizar un iterador en lugar de un índice de bucle

¿Qué tal si utilizamos un vector<Pixel>::iteratoríndice de bucle en lugar de uno?

for (std::vector<Pixel>::iterator j = pixels.begin(); j != pixels.end(); ++j)
{
    j->r = 255;
    j->g = 0;
    j->b = 0;
}

Resultado:

# ./vector 
UseArray completed in 3.264 seconds
UseVector completed in 5.443 seconds

No, no es diferente. Al menos no es más lento. Pensé que esto tendría un rendimiento similar al n.° 2, donde usé una Pixel&referencia.

Conclusión

Incluso si alguna cookie inteligente descubre cómo hacer que el bucle vectorial sea tan rápido como el de matriz, esto no habla bien del comportamiento predeterminado de std::vector. Hasta aquí el hecho de que el compilador sea lo suficientemente inteligente como para optimizar todo el contenido de C++ y hacer que los contenedores STL sean tan rápidos como las matrices sin formato.

La conclusión es que el compilador no puede optimizar las llamadas al constructor predeterminado no operativo cuando usa std::vector. Si usas simple, new[]los optimiza muy bien. Pero no con std::vector. Incluso si puede reescribir su código para eliminar las llamadas al constructor que se oponen al mantra por aquí: "El compilador es más inteligente que usted. El STL es tan rápido como el C simple. No se preocupe por eso".

Sep 08 '2010 03:09 John Kugelman

Ésta es una pregunta antigua pero popular.

En este punto, muchos programadores estarán trabajando en C++11. Y en C++ 11, el código del OP tal como está escrito se ejecuta igualmente rápido para UseArrayo UseVector.

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

El problema fundamental era que mientras tu Pixelestructura no estaba inicializada, std::vector<T>::resize( size_t, T const&=T() )toma una construida por defecto Pixely la copia . El compilador no se dio cuenta de que se le pedía que copiara datos no inicializados, por lo que realizó la copia.

En C++11, std::vector<T>::resizetiene dos sobrecargas. El primero es std::vector<T>::resize(size_t), el otro es std::vector<T>::resize(size_t, T const&). Esto significa que cuando se invoca resizesin un segundo argumento, simplemente se construye de forma predeterminada, y el compilador es lo suficientemente inteligente como para darse cuenta de que la construcción predeterminada no hace nada, por lo que se salta el paso sobre el búfer.

(Las dos sobrecargas se agregaron para manejar tipos móviles, construibles y no copiables; la mejora del rendimiento cuando se trabaja con datos no inicializados es una ventaja).

La push_backsolución también realiza comprobaciones de postes, lo que la ralentiza, por lo que sigue siendo más lenta que la mallocversión.

ejemplo en vivo (también reemplacé el temporizador con chrono::high_resolution_clock).

Tenga en cuenta que si tiene una estructura que generalmente requiere inicialización, pero desea manejarla después de hacer crecer su búfer, puede hacerlo con un std::vectorasignador personalizado. Si desea pasarlo a un modo más normal std::vector, creo que el uso cuidadoso allocator_traitsy la anulación ==podrían lograrlo, pero no estoy seguro.

Jul 17 '2014 14:07 Yakk - Adam Nevraumont

Para ser justos, no se puede comparar una implementación de C++ con una implementación de C, como yo llamaría a su versión de malloc. malloc no crea objetos, solo asigna memoria sin procesar. Que luego trates esa memoria como objetos sin llamar al constructor es un C++ deficiente (posiblemente no válido; se lo dejaré a los abogados del lenguaje).

Dicho esto, simplemente cambiar malloc a new Pixel[dimensions*dimensions]y free delete [] pixelsno hace mucha diferencia con la implementación simple de Pixel que tienes. Aquí están los resultados en mi caja (E6600, 64 bits):

UseArray completed in 0.269 seconds
UseVector completed in 1.665 seconds
UseVectorPushBack completed in 7.309 seconds
The whole thing completed in 9.244 seconds

Pero con un ligero cambio, las tornas cambian:

Píxel.h

struct Pixel
{
    Pixel();
    Pixel(unsigned char r, unsigned char g, unsigned char b);

    unsigned char r, g, b;
};

Píxel.cc

#include "Pixel.h"

Pixel::Pixel() {}
Pixel::Pixel(unsigned char r, unsigned char g, unsigned char b) 
  : r(r), g(g), b(b) {}

principal.cc

#include "Pixel.h"
[rest of test harness without class Pixel]
[UseArray now uses new/delete not malloc/free]

Compilado de esta manera:

$ g++ -O3 -c -o Pixel.o Pixel.cc
$ g++ -O3 -c -o main.o main.cc
$ g++ -o main main.o Pixel.o

obtenemos resultados muy diferentes:

UseArray completed in 2.78 seconds
UseVector completed in 1.651 seconds
UseVectorPushBack completed in 7.826 seconds
The whole thing completed in 12.258 seconds

Con un constructor no integrado para Pixel, std::vector ahora supera a una matriz sin formato.

Parecería que la complejidad de la asignación a través de std::vector y std:allocator es demasiado para optimizarla con tanta eficacia como un simple archivo new Pixel[n]. Sin embargo, podemos ver que el problema es simplemente con la asignación, no con el acceso al vector, modificando un par de funciones de prueba para crear el vector/matriz una vez moviéndolo fuera del bucle:

void UseVector()
{
    TestTimer t("UseVector");

    int dimension = 999;
    std::vector<Pixel> pixels;
    pixels.resize(dimension * dimension);

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

y

void UseArray()
{
    TestTimer t("UseArray");

    int dimension = 999;
    Pixel * pixels = new Pixel[dimension * dimension];

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
    delete [] pixels;
}

Obtenemos estos resultados ahora:

UseArray completed in 0.254 seconds
UseVector completed in 0.249 seconds
UseVectorPushBack completed in 7.298 seconds
The whole thing completed in 7.802 seconds

Lo que podemos aprender de esto es que std::vector es comparable a una matriz sin formato para el acceso, pero si necesita crear y eliminar el vector/matriz muchas veces, crear un objeto complejo llevará más tiempo que crear una matriz simple. cuando el constructor del elemento no está incluido. No creo que esto sea muy sorprendente.

Sep 08 '2010 12:09 camh