¿Std:: vector es mucho más lento que los arrays simples?

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

La optimización ayuda, pero no es suficiente. Con la optimización en todavía estoy viendo una diferencia de rendimiento 2X 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 # 1-Usa nuevo[] en lugar de malloc

Intenté cambiar malloc() a new[] en UseArray para que los objetos se construyan. Y cambiar de asignación de campo individual a asignar una instancia de píxel. Oh, y renombrar la variable de 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 hizo ninguna diferencia en absoluto. Ni siquiera el cambio a new[] que construirá por defecto todos los Píxeles. Parece que gcc puede optimizar las llamadas al constructor por defecto cuando se usa new[], pero no cuando se usa vector.

Idea # 2 - Eliminar llamadas repetidas del operador []

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

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 # 3-Eliminar constructores

¿Qué pasa con la eliminación de los constructores por completo? Entonces tal vez gcc puede optimizar la construcción de todos los objetos cuando se crean los vectores. Qué sucede si cambiamos Pixel a:

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

Resultado: aproximadamente un 10% más rápido. Todavía más lento que un matriz. Hm.

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

Idea # 4-Usar iterador en lugar de índice de bucle

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

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 #2 donde usé una referencia Pixel&.

Conclusión

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

La conclusión es que el compilador no puede optimizar las llamadas al constructor predeterminadas sin op cuando usa std::vector. Si usa plain new[], los optimiza muy bien. Pero no con std::vector. Incluso si puedes reescribir tu código para eliminar las llamadas del constructor que van en contra del mantra por aquí: "El compilador es más inteligente que tú. El STL es tan rápido como C. No te preocupes."

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 malloc. malloc no crea objetos - solo asigna memoria raw. Que luego trates esa memoria como objetos sin llamar al constructor es C++ pobre (posiblemente inválido - dejaré eso a los abogados del lenguaje).

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

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 cosas cambian: {[13]]}

Pixel.h

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

    unsigned char r, g, b;
};

Pixel.cc

#include "Pixel.h"

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

Main.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 inlineado para Pixel, std::vector ahora supera a un array raw.

Parece que la complejidad de la asignación a través de std::vector y std:asignador es demasiado para ser optimizado tan eficazmente como un simple new Pixel[n]. Sin embargo, podemos ver que el problema es simplemente con la asignación no el acceso vectorial ajustando un par de las funciones de prueba para crear el vector / array 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;
}

Ahora obtenemos estos resultados:

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 raw para el acceso, pero si necesita crear y eliminar el vector/matriz muchas veces, creando una el objeto complejo consumirá más tiempo que crear una matriz simple cuando el constructor del elemento no está inlineado. No creo que esto sea muy sorprendente.

Esta 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 corre igual de rápido para UseArray o UseVector.

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

El problema fundamental era que mientras su estructura Pixel no estaba inicializada, std::vector<T>::resize( size_t, T const&=T() ) toma un construido por defecto Pixel y lo copia. El compilador no se dio cuenta de que se le estaba pidiendo copiar datos no iniciados, por lo que en realidad realizó la copia.

En C++11, std::vector<T>::resize tiene 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 invoca resize sin un segundo argumento, simplemente construye por defecto, y el compilador es lo suficientemente inteligente como para darse cuenta de que la construcción por defecto no hace nada, por lo que se salta el pase sobre el búfer.

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

La solución push_back también hace fencepost checking, que lo ralentiza, por lo que sigue siendo más lento que la versión malloc.

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 asignador personalizado std::vector. Si quieres moverlo a un std::vector más normal, creo que el uso cuidadoso de allocator_traits y la anulación de == podría lograrlo, pero inseguro.

Prueba con esto:

void UseVectorCtor()
{
    TestTimer t("UseConstructor");

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

        std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));
    }
}

Obtengo casi exactamente el mismo rendimiento que con array.

Lo que pasa con vector es que es una herramienta mucho más general que una matriz. Y eso significa que tienes que considerar cómo lo usas. Se puede usar de muchas maneras diferentes, proporcionando una funcionalidad que una matriz ni siquiera tiene. Y si lo usa " mal " para su propósito, incurre en una gran cantidad de gastos generales, pero si lo usa correctamente, generalmente es básicamente un dato de gastos generales cero estructura. En este caso, el problema es que inicializaste por separado el vector (haciendo que todos los elementos tengan su ctor predeterminado llamado), y luego sobrescribiste cada elemento individualmente con el valor correcto. Eso es mucho más difícil de optimizar para el compilador que cuando se hace lo mismo con una matriz. Es por eso que el vector proporciona un constructor que le permite hacer exactamente eso: inicializar N elementos con valor X.

Y cuando usas eso, el vector es igual de rápido como una matriz.

Así que no, no has roto el mito del rendimiento. Pero usted ha demostrado que solo es cierto si se utiliza el vector de manera óptima, que es un punto bastante bueno también. :)

En el lado positivo, es realmente el uso más simple que resulta ser el más rápido. Si comparas mi fragmento de código (una sola línea) con la respuesta de John Kugelman, que contiene montones y montones de ajustes y optimizaciones, que aún no eliminan la diferencia de rendimiento, está bastante claro eso vector está muy inteligentemente diseñado después de todo. Usted no tiene que saltar a través de aros para obtener una velocidad igual a una matriz. Por el contrario, hay que utilizar la solución más simple posible.

No fue una comparación justa cuando miré por primera vez su código; definitivamente pensé que no estaba comparando manzanas con manzanas. Así que pensé, vamos a llamar a constructores y destructores en todas las pruebas; y luego comparar.

const size_t dimension = 1000;

void UseArray() {
    TestTimer t("UseArray");
    for(size_t j = 0; j < dimension; ++j) {
        Pixel* pixels = new Pixel[dimension * dimension];
        for(size_t i = 0 ; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
        delete[] pixels;
    }
}

void UseVector() {
    TestTimer t("UseVector");
    for(size_t j = 0; j < dimension; ++j) {
        std::vector<Pixel> pixels(dimension * dimension);
        for(size_t i = 0; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
    }
}

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

    UseArray();
    UseVector();

    return 0;
}

Mis pensamientos eran, que con esta configuración, deberían ser exactamente lo mismo. Resulta que estaba equivocado.

UseArray completed in 3.06 seconds
UseVector completed in 4.087 seconds
The whole thing completed in 10.14 seconds

Entonces, ¿por qué se produjo esta pérdida de rendimiento del 30%? El STL tiene todo en encabezados, por lo que debería haber sido posible para el compilador para entender todo lo que se requiere.

Mis pensamientos fueron que está en cómo el bucle inicializa todos los valores al constructor predeterminado. Así que realicé una prueba:

class Tester {
public:
    static int count;
    static int count2;
    Tester() { count++; }
    Tester(const Tester&) { count2++; }
};
int Tester::count = 0;
int Tester::count2 = 0;

int main() {
    std::vector<Tester> myvec(300);
    printf("Default Constructed: %i\nCopy Constructed: %i\n", Tester::count, Tester::count2);

    return 0;
}

Los resultados fueron los que sospeché:{[14]]}

Default Constructed: 1
Copy Constructed: 300

Esta es claramente la fuente de la desaceleración, el hecho de que el vector utiliza el constructor de copia para inicializar los elementos de un objeto construido por defecto.

Esto significa, que el siguiente orden pseudo-operación está sucediendo durante la construcción del vector:

Pixel pixel;
for (auto i = 0; i < N; ++i) vector[i] = pixel;

Que, debido al constructor de copia implícito hecho por el compilador, se expande a lo siguiente:

Pixel pixel;
for (auto i = 0; i < N; ++i) {
    vector[i].r = pixel.r;
    vector[i].g = pixel.g;
    vector[i].b = pixel.b;
}

Así que el valor predeterminado Pixelpermanece sin inicializar, mientras que el resto se inicializa con los valores predeterminados Pixels no inicializados.

En comparación con la situación alternativa con New[]/Delete[]:

int main() {
    Tester* myvec = new Tester[300];

    printf("Default Constructed: %i\nCopy Constructed:%i\n", Tester::count, Tester::count2);

    delete[] myvec;

    return 0;
}

Default Constructed: 300
Copy Constructed: 0

Todos se dejan a sus valores no inicializados, y sin el doble iteración sobre la secuencia.

Armado con esta información, ¿cómo podemos probarlo? Intentemos sobreescribir el constructor de copia implícito.

Pixel(const Pixel&) {}

Y los resultados?

UseArray completed in 2.617 seconds
UseVector completed in 2.682 seconds
The whole thing completed in 5.301 seconds

Así que en resumen, si estás haciendo cientos de vectores muy a menudo: repensar su algoritmo.

En cualquier caso, la implementación de STL no es más lenta por alguna razón desconocida, solo hace exactamente lo que pides; esperando que sepas mejor.

Intente deshabilitar los iteradores marcados y compilar en modo release. No deberías ver mucha diferencia de rendimiento.

El STL de GNU (y otros), dado vector<T>(n), construye por defecto un objeto prototípico T() - el compilador optimizará el constructor vacío - pero luego una copia de cualquier basura que estuviera en las direcciones de memoria ahora reservadas para el objeto es tomada por el STL __uninitialized_fill_n_aux, que loops rellenando copias de ese objeto como los valores predeterminados en el vector. Por lo tanto," mi " STL no está construyendo en bucle, sino construyendo luego loop/copying. Es contra intuitivo, pero debería haber recordado como comentó sobre una pregunta reciente de stackoverflow sobre este mismo punto: la construcción / copia puede ser más eficiente para objetos contados de referencia, etc..

Así que:

vector<T> x(n);

O

vector<T> x;
x.resize(n);

Es - en muchas implementaciones STL-algo como:

T temp;
for (int i = 0; i < n; ++i)
    x[i] = temp;

El problema es que la generación actual de optimizadores de compiladores no parece funcionar desde la idea de que temp es basura no inicializada, y no optimiza las invocaciones de bucle y constructor de copia por defecto. Podrías argumentan creíblemente que los compiladores absolutamente no deberían optimizar esto, ya que un programador que escribe lo anterior tiene una expectativa razonable de que todos los objetos serán idénticos después del bucle, incluso si se aplican las advertencias habituales sobre 'idéntico'/operator== vs memcmp/operator= etc). No se puede esperar que el compilador tenga información adicional sobre el contexto más amplio de std:: vector o el uso posterior de los datos que sugeriría esta optimización segura.

Esto se puede contrastar con el aplicación más obvia y directa:

for (int i = 0; i < n; ++i)
    x[i] = T();

Que podemos esperar que un compilador optimice.

Para ser un poco más explícito sobre la justificación de este aspecto del comportamiento del vector, considere:

std::vector<big_reference_counted_object> x(10000);

Claramente es una gran diferencia si hacemos 10000 objetos independientes frente a 10000 haciendo referencia a los mismos datos. Hay un argumento razonable de que la ventaja de proteger a los usuarios casuales de C++ de hacer accidentalmente algo tan caro supera a la muy pequeña coste real de la construcción de copias difíciles de optimizar.

RESPUESTA ORIGINAL (para referencia / dar sentido a los comentarios): Ni hablar. vector es tan rápido como una matriz, al menos si se reserva el espacio con sensatez. ...

La respuesta de Martin York me molesta porque parece un intento de ocultar el problema de la inicialización. Pero tiene razón al identificar la construcción redundante por defecto como la fuente de problemas de rendimiento.

[EDITAR: La respuesta de Martin ya no sugiere cambiar el constructor predeterminado.]

Para el problema inmediato en cuestión, ciertamente podría llamar a la versión de 2 parámetros del vector<Pixel> ctor en su lugar:

std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));

Eso funciona si desea inicializar con un valor constante, que es un caso común. Pero el problema más general es: ¿Cómo se puede inicializar eficientemente con algo más complicado que un valor constante?

Para esto puede usar un back_insert_iterator, que es un adaptador iterador. Aquí hay un ejemplo con un vector de int s, aunque la idea general funciona igual de bien para Pixel s:

#include <iterator>
// Simple functor return a list of squares: 1, 4, 9, 16...
struct squares {
    squares() { i = 0; }
    int operator()() const { ++i; return i * i; }

private:
    int i;
};

...

std::vector<int> v;
v.reserve(someSize);     // To make insertions efficient
std::generate_n(std::back_inserter(v), someSize, squares());

Alternativamente puedes usar copy() o transform() en lugar de generate_n().

La desventaja es que el la lógica para construir los valores iniciales necesita ser movida a una clase separada, lo cual es menos conveniente que tenerla en su lugar (aunque las lambdas en C++1x hacen esto mucho más agradable). También espero que esto todavía no sea tan rápido como una versión no STL basada en malloc(), pero espero que sea cercano, ya que solo hace una construcción para cada elemento.

Los vectores están llamando adicionalmente a constructores de píxeles.

Cada una está causando casi un millón de corridas ctor que estás sincronizando.

Editar: luego está el 1 exterior...1000 bucle, así que hacer que un billón de llamadas ctor!

Edit 2: sería interesante ver el desmontaje del estuche UseArray. Un optimizador podría optimizar todo el asunto, ya que no tiene otro efecto que quemar CPU.

Así es como funciona el método push_back en vector:

1. El vector asigna X cantidad de espacio cuando se inicializa.
2. Como se indica a continuación, comprueba si hay espacio en la matriz subyacente actual para el elemento.
3. Hace una copia del elemento en la llamada push_back.

Después de llamar push_back X elementos:

1. El vector reasigna kX cantidad de espacio en una 2da matriz.
2. Copia las entradas del primer array en el segundo.
3. Descarta el primer array.
4. Ahora usa la segunda matriz como almacenamiento hasta que alcanza las entradas kX.

Repita. Si no estás reserving el espacio definitivamente va a ser más lento. Más que eso, si es caro copiar el artículo entonces 'push_back' así te va a comer vivo.

En cuanto a la cosa vector versus matriz, voy a tener que estar de acuerdo con las otras personas. Ejecutar en release, activar optimizaciones, y poner en un par de banderas más para que el amistoso la gente en Microsoft no # @ % ^ ^ es para ti.

Una cosa más, si no necesita cambiar el tamaño, use Boost.Matriz.

Algunos datos del perfilador (el píxel está alineado a 32 bits):

g++ -msse3 -O3 -ftree-vectorize -g test.cpp -DNDEBUG && ./a.out
UseVector completed in 3.123 seconds
UseArray completed in 1.847 seconds
UseVectorPushBack completed in 9.186 seconds
The whole thing completed in 14.159 seconds

Blah

andrey@nv:~$ opannotate --source libcchem/src/a.out  | grep "Total samples for file" -A3
Overflow stats not available
 * Total samples for file : "/usr/include/c++/4.4/ext/new_allocator.h"
 *
 * 141008 52.5367
 */
--
 * Total samples for file : "/home/andrey/libcchem/src/test.cpp"
 *
 *  61556 22.9345
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_vector.h"
 *
 *  41956 15.6320
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_uninitialized.h"
 *
 *  20956  7.8078
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_construct.h"
 *
 *   2923  1.0891
 */

En allocator:

               :      // _GLIBCXX_RESOLVE_LIB_DEFECTS
               :      // 402. wrong new expression in [some_] allocator::construct
               :      void
               :      construct(pointer __p, const _Tp& __val)
141008 52.5367 :      { ::new((void *)__p) _Tp(__val); }

vector:

               :void UseVector()
               :{ /* UseVector() total:  60121 22.3999 */
...
               :
               :
 10790  4.0201 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
   495  0.1844 :            pixels[i].r = 255;
               :
 12618  4.7012 :            pixels[i].g = 0;
               :
  2253  0.8394 :            pixels[i].b = 0;
               :
               :        }

Array

               :void UseArray()
               :{ /* UseArray() total:  35191 13.1114 */
               :
...
               :
   136  0.0507 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
  9897  3.6874 :            pixels[i].r = 255;
               :
  3511  1.3081 :            pixels[i].g = 0;
               :
 21647  8.0652 :            pixels[i].b = 0;

La mayor parte de la sobrecarga está en el constructor de copia. Por ejemplo,

    std::vector < Pixel > pixels;//(dimension * dimension, Pixel());

    pixels.reserve(dimension * dimension);

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

        pixels[i].r = 255;

        pixels[i].g = 0;

        pixels[i].b = 0;
    }

Tiene el mismo rendimiento que un array.

Mi laptop es Lenova G770 (4 GB RAM).

El sistema operativo es Windows 7 de 64 bits (el que tiene computadora portátil)

El compilador es MinGW 4.6.1.

El IDE es Code::Blocks.

Pruebo los códigos fuente del primer post.

Los resultados

Optimización de O2

UseArray completado en 2.841 segundos

UseVector completado en 2.548 segundos

UseVectorPushBack completado en 11.95 segundos

Todo se completó en 17.342 segundos

Pausa del sistema

Optimización de O3

UseArray completado en 1.452 segundos

UseVector completado en 2.514 segundos

UseVectorPushBack completado en 12.967 segundos

Todo se completó en 16.937 segundos

Parece que el rendimiento de vector es peor bajo la optimización de O3.

Si cambia el bucle a

    pixels[i].r = i;
    pixels[i].g = i;
    pixels[i].b = i;

La velocidad de la matriz y el vector bajo O2 y O3 son casi iguales.

Un mejor punto de referencia (creo...), el compilador debido a optimizaciones puede cambiar el código, porque los resultados de vectores/arrays asignados no se utilizan en ningún lugar. Resultados:

$ g++ test.cpp -o test -O3 -march=native
$ ./test 
UseArray inner completed in 0.652 seconds
UseArray completed in 0.773 seconds
UseVector inner completed in 0.638 seconds
UseVector completed in 0.757 seconds
UseVectorPushBack inner completed in 6.732 seconds
UseVectorPush completed in 6.856 seconds
The whole thing completed in 8.387 seconds

Compilador:

gcc version 6.2.0 20161019 (Debian 6.2.0-9)

CPU:

model name  : Intel(R) Core(TM) i7-3630QM CPU @ 2.40GHz

Y el código:

#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(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVector inner");

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

        std::vector<Pixel>& pixels = results.at(i);
        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(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVectorPushBack inner");

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

        std::vector<Pixel>& pixels = results.at(i);
            pixels.reserve(dimension * dimension);

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

void UseArray(Pixel** results)
{
    TestTimer t("UseArray inner");

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

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

        results[i] = pixels;

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

        // free(pixels);
    }
}

void UseArray()
{
    TestTimer t("UseArray");
    Pixel** array = (Pixel**)malloc(sizeof(Pixel*)* 1000);
    UseArray(array);
    for(int i=0;i<1000;++i)
        free(array[i]);
    free(array);
}

void UseVector()
{
    TestTimer t("UseVector");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVector(vector);
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPush");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVectorPushBack(vector);
    }
}


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

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

    return 0;
}

Con las opciones correctas, vectores y matrices pueden generar asm idénticos. En estos casos, son, por supuesto, la misma velocidad, porque se obtiene el mismo archivo ejecutable de cualquier manera.

Por cierto, la ralentización de su visualización en clases usando vector también ocurre con tipos estándar como int. He aquí un código multiproceso:

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <typeinfo>
#include <vector>
#include <pthread.h>
#include <sstream>
#include <fstream>
using namespace std;

//pthread_mutex_t map_mutex=PTHREAD_MUTEX_INITIALIZER;

long long num=500000000;
int procs=1;

struct iterate
{
    int id;
    int num;
    void * member;
    iterate(int a, int b, void *c) : id(a), num(b), member(c) {}
};

//fill out viterate and piterate
void * viterate(void * input)
{
    printf("am in viterate\n");
    iterate * info=static_cast<iterate *> (input);
    // reproduce member type
    vector<int> test= *static_cast<vector<int>*> (info->member);
    for (int i=info->id; i<test.size(); i+=info->num)
    {
        //printf("am in viterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

void * piterate(void * input)
{
    printf("am in piterate\n");
    iterate * info=static_cast<iterate *> (input);;
    int * test=static_cast<int *> (info->member);
    for (int i=info->id; i<num; i+=info->num) {
        //printf("am in piterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

int main()
{
    cout<<"producing vector of size "<<num<<endl;
    vector<int> vtest(num);
    cout<<"produced  a vector of size "<<vtest.size()<<endl;
    pthread_t thread[procs];

    iterate** it=new iterate*[procs];
    int ans;
    void *status;

    cout<<"begining to thread through the vector\n";
    for (int i=0; i<procs; i++) {
        it[i]=new iterate(i, procs, (void *) &vtest);
    //  ans=pthread_create(&thread[i],NULL,viterate, (void *) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the vector";
    //reuse the iterate structures

    cout<<"producing a pointer with size "<<num<<endl;
    int * pint=new int[num];
    cout<<"produced a pointer with size "<<num<<endl;

    cout<<"begining to thread through the pointer\n";
    for (int i=0; i<procs; i++) {
        it[i]->member=&pint;
        ans=pthread_create(&thread[i], NULL, piterate, (void*) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the pointer\n";

    //delete structure array for iterate
    for (int i=0; i<procs; i++) {
        delete it[i];
    }
    delete [] it;

    //delete pointer
    delete [] pint;

    cout<<"end of the program"<<endl;
    return 0;
}

El comportamiento del código muestra que la instanciación de vector es la parte más larga del código. Una vez que atravieses ese cuello de botella. El resto del código se ejecuta extremadamente rápido. Esto es cierto sin importar cuántos hilos esté ejecutando.

Por cierto ignorar el número absolutamente loco de includes. He estado usando este código para probar cosas para un proyecto por lo que el número de incluye seguir creciendo.

Solo quiero mencionar que vector (y smart_ptr) es solo un complemento de capa delgada sobre matrices raw (y punteros raw). Y en realidad el tiempo de acceso de un vector en memoria continua es más rápido que la matriz. El siguiente código muestra el resultado de inicializar y acceder vector y matriz.

#include <boost/date_time/posix_time/posix_time.hpp>
#include <iostream>
#include <vector>
#define SIZE 20000
int main() {
    srand (time(NULL));
    vector<vector<int>> vector2d;
    vector2d.reserve(SIZE);
    int index(0);
    boost::posix_time::ptime start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        vector2d.push_back(vector<int>(SIZE));
    }
    boost::posix_time::ptime start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            vector2d[index][index]++;
        }
    }
    boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time();
    boost::posix_time::time_duration msdiff = end - start_total;
    cout << "Vector total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Vector access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 


    int index(0);
    int** raw2d = nullptr;
    raw2d = new int*[SIZE];
    start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        raw2d[i] = new int[SIZE];
    }
    start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            raw2d[index][index]++;
        }
    }
    end = boost::posix_time::microsec_clock::local_time();
    msdiff = end - start_total;
    cout << "Array total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Array access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 
    for (int i = 0; i < SIZE; i++) {
        delete [] raw2d[i];
    }
    return 0;
}

La salida es:

    Vector total time: 925milliseconds.
    Vector access time: 4milliseconds.
    Array total time: 30milliseconds.
    Array access time: 21milliseconds.

Así que la velocidad será casi la misma si la usas correctamente. (como otros mencionaron usando reserve () o resize ()).

Bueno, porque vector::resize() hace mucho más procesamiento que la asignación de memoria simple (por malloc).

Intenta poner un punto de interrupción en tu constructor de copia (¡defínelo para que pueda llegar a un punto de interrupción!) y ahí va el tiempo de procesamiento adicional.

Tengo que decir que no soy un experto en C++. Pero para agregar algunos resultados de experimentos:

Compilar: gcc-6.2.0 / bin / g++ - O3-std = c++14 vector.cpp

Máquina:

Intel(R) Xeon(R) CPU E5-2690 v2 @ 3.00GHz 

OS:

2.6.32-642.13.1.el6.x86_64

Salida:

UseArray completed in 0.167821 seconds
UseVector completed in 0.134402 seconds
UseConstructor completed in 0.134806 seconds
UseFillConstructor completed in 1.00279 seconds
UseVectorPushBack completed in 6.6887 seconds
The whole thing completed in 8.12888 seconds

Aquí lo único que me siento extraño es que "UseFillConstructor" rendimiento en comparación con "UseConstructor".

El código:

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

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

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


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

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

        std::vector<Pixel> pixels(dimension*dimension, Pixel(255,0,0));
    }
}

Así que el "valor" adicional proporcionado ralentiza el rendimiento bastante, lo que creo que se debe a múltiples llamadas para copiar constructor. Pero...

Compilar:

gcc-6.2.0/bin/g++ -std=c++14 -O vector.cpp

Salida:

UseArray completed in 1.02464 seconds
UseVector completed in 1.31056 seconds
UseConstructor completed in 1.47413 seconds
UseFillConstructor completed in 1.01555 seconds
UseVectorPushBack completed in 6.9597 seconds
The whole thing completed in 11.7851 seconds

Así que en este caso, la optimización de gcc es muy importante, pero no puede ayudarlo mucho cuando se proporciona un valor por defecto. Esto va en contra de mi matrícula. Con suerte, ayuda al nuevo programador cuando elija qué formato de inicialización vectorial.

Hice algunas pruebas extensas que quería desde hace un tiempo. Bien podría compartir esto.

Esta es mi máquina de arranque dual i7-3770, 16 GB de Ram, x86_64, en Windows 8.1 y en Ubuntu 16.04. Más información y conclusiones, observaciones a continuación. Probado tanto MSVS 2017 como g++ (tanto en Windows como en Linux).

Programa de pruebas

#include <iostream>
#include <chrono>
//#include <algorithm>
#include <array>
#include <locale>
#include <vector>
#include <queue>
#include <deque>

// Note: total size of array must not exceed 0x7fffffff B = 2,147,483,647B
//  which means that largest int array size is 536,870,911
// Also image size cannot be larger than 80,000,000B
constexpr int long g_size = 100000;
int g_A[g_size];


int main()
{
    std::locale loc("");
    std::cout.imbue(loc);
    constexpr int long size = 100000;  // largest array stack size

    // stack allocated c array
    std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
    int A[size];
    for (int i = 0; i < size; i++)
        A[i] = i;

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style stack array size=" << sizeof(A) << "B\n\n";

    // global stack c array
    start = std::chrono::steady_clock::now();
    for (int i = 0; i < g_size; i++)
        g_A[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "global c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "global c-style stack array size=" << sizeof(g_A) << "B\n\n";

    // raw c array heap array
    start = std::chrono::steady_clock::now();
    int* AA = new int[size];    // bad_alloc() if it goes higher than 1,000,000,000
    for (int i = 0; i < size; i++)
        AA[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style heap array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style heap array size=" << sizeof(AA) << "B\n\n";
    delete[] AA;

    // std::array<>
    start = std::chrono::steady_clock::now();
    std::array<int, size> AAA;
    for (int i = 0; i < size; i++)
        AAA[i] = i;
    //std::sort(AAA.begin(), AAA.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::array size=" << sizeof(AAA) << "B\n\n";

    // std::vector<>
    start = std::chrono::steady_clock::now();
    std::vector<int> v;
    for (int i = 0; i < size; i++)
        v.push_back(i);
    //std::sort(v.begin(), v.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::vector duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::vector size=" << v.size() * sizeof(v.back()) << "B\n\n";

    // std::deque<>
    start = std::chrono::steady_clock::now();
    std::deque<int> dq;
    for (int i = 0; i < size; i++)
        dq.push_back(i);
    //std::sort(dq.begin(), dq.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::deque duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::deque size=" << dq.size() * sizeof(dq.back()) << "B\n\n";

    // std::queue<>
    start = std::chrono::steady_clock::now();
    std::queue<int> q;
    for (int i = 0; i < size; i++)
        q.push(i);

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::queue duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::queue size=" << q.size() * sizeof(q.front()) << "B\n\n";
}

Resultados

//////////////////////////////////////////////////////////////////////////////////////////
// with MSVS 2017:
// >> cl /std:c++14 /Wall -O2 array_bench.cpp
//
// c-style stack array duration=0.15ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.130ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.90ms
// c-style heap array size=4B
//
// std::array duration=0.20ms
// std::array size=400,000B
//
// std::vector duration=0.544ms
// std::vector size=400,000B
//
// std::deque duration=1.375ms
// std::deque size=400,000B
//
// std::queue duration=1.491ms
// std::queue size=400,000B
//
//////////////////////////////////////////////////////////////////////////////////////////
//
// with g++ version:
//      - (tdm64-1) 5.1.0 on Windows
//      - (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609 on Ubuntu 16.04
// >> g++ -std=c++14 -Wall -march=native -O2 array_bench.cpp -o array_bench
//
// c-style stack array duration=0ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.124ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.648ms
// c-style heap array size=8B
//
// std::array duration=1ms
// std::array size=400,000B
//
// std::vector duration=0.402ms
// std::vector size=400,000B
//
// std::deque duration=0.234ms
// std::deque size=400,000B
//
// std::queue duration=0.304ms
// std::queue size=400,000
//
//////////////////////////////////////////////////////////////////////////////////////////

Notas

• Ensamblado por un promedio de 10 corridas.
• Inicialmente realicé pruebas con std::sort() también (puedes verlo comentado) pero los eliminó más tarde porque no había diferencias relativas significativas.

Mis Conclusiones y observaciones

• observe cómo la matriz de estilo c global toma casi tanto tiempo como la matriz de estilo c de montón
• De todas las pruebas que noté una estabilidad notable en std::array's variaciones de tiempo entre carreras consecutivas, mientras que otros especialmente std:: estructuras de datos variaron enormemente en comparación
• La optimización de O3 no mostró ninguna diferencias horarias notables
• Eliminar la optimización en Windows cl (no-O2) y en g++ (Win/Linux no-O2, no-march=native) aumenta las veces SIGNIFICATIVAMENTE. Particularmente para std::estructuras de datos. En general, tiempos más altos en MSV que en g++, pero std::array y matrices de estilo c más rápido en Windows sin optimización
• g++ produce código más rápido que el compilador de Microsoft (aparentemente se ejecuta más rápido incluso en Windows).

Veredicto

Por supuesto, este es el código para un optimizado construir. Y ya que la pregunta era acerca de std::vector entonces sí lo es !much! más lento que los arrays simples (optimizado/no optimizado). Pero cuando estás haciendo un benchmark, naturalmente quieres producir código optimizado.

La estrella del espectáculo para mí ha sido std::array.