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

Siempre he pensado que es la sabiduría general 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 la prueba:

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 para unos pocos nanosecs".

Y el código que usé:

#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 este mito del rendimiento?

Estoy usando el modo Release en Visual Studio 2005 .

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

Usando lo siguiente:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray se completó en 2.196 segundos
UseVector se completó en 4.412 segundos
UseVectorPushBack se completó en 8.017 segundos
Todo se completó en 14.626 segundos

Entonces array es dos veces más rápido que vector.

Pero después de mirar el código con más detalle, esto se espera; mientras corres por el vector dos veces y la matriz solo una vez. Nota: cuando utiliza resize()el vector, no solo asigna la memoria, sino que también lo ejecuta y llama al constructor de cada miembro.

Reorganizar el código ligeramente para que el vector solo inicialice cada objeto una vez:

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

Ahora haciendo el mismo tiempo nuevamente:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector completado en 2.216 segundos

El vector ahora solo tiene un rendimiento ligeramente peor que la matriz. En mi opinión, esta diferencia es insignificante y podría ser causada por un montón de cosas no asociadas con la prueba.

También tendría en cuenta que no está inicializando / Destruyendo correctamente el objeto Pixel en el UseArrray()método ya que no se llama a ningún constructor / destructor (esto puede no ser un problema para esta clase simple sino algo un poco más complejo (es decir, con punteros o miembros) con punteros) causará problemas.

Gran pregunta Entré 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 activada, sigo 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 - Use new [] en lugar de malloc

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

Idea # 2 - Eliminar llamadas repetidas del operador []

También intenté deshacerme del triple operator[] búsqueda y almacenar en caché la referencia 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 # 3 - Eliminar constructores

¿Qué pasa con la eliminación de los constructores por completo? Entonces, quizás 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 una 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índice de bucle en lugar de un?

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é unPixel& referencia.

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 C ++ ness y hacer que los contenedores STL sean tan rápidos como los arreglos sin formato.

La conclusión es que el compilador no puede optimizar las llamadas de constructor predeterminadas no operativas cuando se 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 de constructor que se oponen al mantra por aquí: "El compilador es más inteligente que usted. El STL es tan rápido como el simple C. No se preocupe".

Esta es una pregunta antigua pero popular.

En este punto, muchos programadores trabajarán en C ++ 11. Y en C ++ 11, el código del OP 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, si bien su Pixelestructura no estaba inicializada, std::vector<T>::resize( size_t, T const&=T() )toma una construcción predeterminada Pixely la copia . El compilador no se dio cuenta de que se le pedía que copiara datos no inicializados, por lo que realmente 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 invoca resizesin 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 omite 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 verifica el poste de la cerca, lo que lo ralentiza, por lo que sigue siendo más lento 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 aumentar su búfer, puede hacerlo con un std::vectorasignador personalizado . Si desea moverlo a una situación más normal std::vector, creo que el uso cuidadoso allocator_traitsy la anulación de esto ==podrían lograrlo, pero no estoy seguro.

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

Dicho esto, simplemente cambiar malloc a new Pixel[dimensions*dimensions]free to delete [] pixelsno hace mucha diferencia con la simple implementación 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 cosas cambian:

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 en línea para Pixel, std :: vector ahora supera a una matriz en bruto.

Parece que la complejidad de la asignación a través de std :: vector y std: allocator es demasiado para ser optimizada de manera tan efectiva como simple new Pixel[n]. Sin embargo, podemos ver que el problema es simplemente con la asignación, no el acceso al vector, ajustando un par de funciones de prueba para crear el vector / matriz una vez, moviéndolo fuera del ciclo:

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

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 la matriz.

La cuestión vectores 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, incurrirá en una sobrecarga, pero si lo usa correctamente, generalmente es básicamente una estructura de datos de sobrecarga cero. En este caso, el problema es que usted inicializó el vector por separado (haciendo que todos los elementos tengan su ctor predeterminado llamado) y luego sobrescribiendo cada elemento individualmente con el valor correcto. Eso es mucho más difícil de optimizar para el compilador que cuando haces lo mismo con una matriz. Es por eso que el vector proporciona un constructor que le permite hacer exactamente eso: .NX

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

Entonces no, no has roto el mito del rendimiento. Pero ha demostrado que solo es cierto si usa el vector de manera óptima, lo cual 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 contrasta 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 que vector, después de todo, está muy bien diseñado. No tiene que saltar a través de aros para obtener una velocidad igual a una matriz. Por el contrario, debe usar la solución más simple posible.

No fue una comparación justa cuando vi por primera vez su código; Definitivamente pensé que no estabas comparando manzanas con manzanas. Entonces pensé, vamos a llamar a los 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;
}

Pensé 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é ocurrió esta pérdida de rendimiento del 30%? El STL tiene todo en los encabezados, por lo que debería haber sido posible para el compilador comprender todo lo que se requería.

Pensé que es en cómo el bucle inicializa todos los valores al constructor predeterminado. Entonces 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 como sospechaba:

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 de pseudooperación ocurre durante la construcción del vector:

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

Lo cual, debido al constructor de copia implícita 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;
}

Por lo que el defecto Pixelsigue siendo un-inicializado, mientras que el resto se inicializa con el valor por defecto Pixel's un-inicializado valores.

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 la doble iteración sobre la secuencia.

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

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

En resumen, si está haciendo cientos de vectores muy a menudo: reconsidere 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 le pides; esperando que sepas mejor.

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

El STL de GNU (y otros), dado vector<T>(n), por defecto construye un objeto prototipo T()(el compilador optimizará el constructor vacío), pero luego los STL toman una copia de cualquier basura que haya quedado en las direcciones de memoria ahora reservadas para el objeto.__uninitialized_fill_n_aux que bucles que completan copias de ese objeto como los valores predeterminados en el vector. Entonces, "mi" STL no está construyendo en bucle, sino construyendo luego en bucle / copia. Es contrario a la intuición, pero debería haberlo recordado cuando comenté una pregunta reciente de stackoverflow sobre este mismo punto: la construcción / copia puede ser más eficiente para los objetos contados de referencia, etc.

Entonces:

vector<T> x(n);

o

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

es, en muchas implementaciones de 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 a partir de la idea de que temp es basura no inicializada, y no puede optimizar el bucle y las invocaciones de constructor de copia predeterminadas. Podría argumentar de manera creíble que los compiladores 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 ciclo, incluso si es basura (advertencias habituales sobre 'idéntico' / operador == vs memcmp / operator = etc aplica). No se puede esperar que el compilador tenga ninguna idea adicional sobre el contexto más amplio de std :: vector <> o el uso posterior de los datos que sugeriría que esta optimización es segura.

Esto puede contrastarse con la implementación directa más obvia:

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 versus 10000 que hacen referencia a los mismos datos. Existe un argumento razonable de que la ventaja de proteger a los usuarios ocasionales de C ++ de hacer accidentalmente algo tan costoso supera el costo muy pequeño del mundo real de la construcción de copias difíciles de optimizar.

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

La respuesta de Martin York me molesta porque parece un intento de rozar el problema de inicialización debajo de la alfombra. Pero tiene razón al identificar la construcción redundante predeterminada 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, podría llamar a la versión de 2 parámetros del vector<Pixel>ctor:

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 iniciar de manera eficiente con algo más complicado que un valor constante?

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

#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, podría usar copy()o en transform()lugar de generate_n().

La desventaja es que la lógica para construir los valores iniciales debe trasladarse a una clase separada, lo que es menos conveniente que tenerlo en su lugar (aunque las lambdas en C ++ 1x lo hacen mucho más agradable). También espero que esto aún no sea tan rápido como una malloc()versión no STL basada en la base, pero espero que esté cerca, ya que solo hace una construcción para cada elemento.

Los vectores también están llamando constructores de píxeles.

Cada uno está causando casi un millón de corridas que estás cronometrando.

editar: luego está el bucle externo 1 ... 1000, ¡así que haz que mil millones de llamadas ctor!

Edición 2: sería interesante ver el desmontaje del caso UseArray. Un optimizador podría optimizar todo, ya que no tiene otro efecto que no sea quemar la CPU.

Así es como funciona el push_backmétodo en vector:

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

Después de llamar a push_backX artículos:

3. El vector reasigna la cantidad de espacio kX en una segunda matriz.
4. Copia las entradas de la primera matriz en la segunda.
5. Descarta la primera matriz.
6. Ahora usa la segunda matriz como almacenamiento hasta que alcanza las entradas kX.

Repetir. Si no tienes reservingespacio, definitivamente será más lento. Más que eso, si es costoso copiar el artículo, entonces 'push_back' así te va a comer vivo.

En cuanto a lo de la vectormatriz versus, voy a tener que estar de acuerdo con las otras personas. Ejecútelo en la versión, active las optimizaciones y coloque algunas banderas más para que la gente amigable de Microsoft no lo haga.

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

Algunos datos del generador de perfiles (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

Paja

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

formación

               :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 una matriz.

Mi laptop es Lenova G770 (4 GB de RAM).

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

El compilador es MinGW 4.6.1.

El IDE es Code :: Blocks .

Pruebo los códigos fuente de la primera publicación.

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 del vector es peor con 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 que ...), el compilador debido a las optimizaciones puede cambiar el código, porque los resultados de los vectores / matrices asignados no se usan en ninguna parte. 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)

UPC:

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

Y el codigo:

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

Hice algunas pruebas exhaustivas que quería por un tiempo ahora. Bien podría compartir esto.

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

Programa de prueba

#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

• Montado por un promedio de 10 carreras.
• Inicialmente también realicé pruebas con std::sort()(puede verlo comentado) pero las eliminé más tarde porque no hubo diferencias relativas significativas.

Mis conclusiones y observaciones

• observe cómo la matriz global de estilo c toma casi tanto tiempo como la matriz de estilo c dinámico
• De todas las pruebas, noté una notable estabilidad en std::arraylas variaciones de tiempo entre ejecuciones consecutivas, mientras que otras, especialmente las estructuras std :: data, variaron enormemente en comparación
• La optimización de O3 no mostró diferencias de tiempo notables
• Eliminar la optimización en Windows cl (no -O2) y en g ++ (Win / Linux no -O2, no -march = native) aumenta los tiempos SIGNIFICATIVAMENTE. Particularmente para estructuras std :: data. En general, tiempos más altos en MSVS que g ++, pero std::arrayy matrices de estilo c más rápido en Windows sin optimización
• g ++ produce un 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 una compilación optimizada. Y como la pregunta era sobre std::vectorentonces, sí, ¡es mucho! más lento que las matrices simples (optimizado / no optimizado). Pero cuando está haciendo un punto de referencia, naturalmente desea producir código optimizado.

Sin embargo, la estrella del espectáculo para mí ha sido std::array.

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

Por cierto, la ralentización de su visión en las clases usando el vector también ocurre con tipos estándar como int. Aquí hay 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 del vector es la parte más larga del código. Una vez que atraviesas el cuello de la botella. El resto del código se ejecuta extremadamente rápido. Esto es cierto sin importar cuántos hilos esté ejecutando.

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

Solo quiero mencionar que vector (y smart_ptr) es solo una capa delgada agregada sobre matrices sin formato (y punteros sin formato). 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 al vector y a la 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;
}

El resultado es:

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

Por lo tanto, la velocidad será casi la misma si la usa correctamente. (como otros mencionaron usando reserve () o resize ()).

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

Intente poner un punto de interrupción en su constructor de copias (¡defínalo para que pueda tener 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 parece extraño es el rendimiento de "UseFillConstructor" 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));
    }
}

Por lo tanto, el "valor" adicional proporcionado ralentiza bastante el rendimiento, lo que creo que se debe a la llamada múltiple para copiar el 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

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

Parece depender de los indicadores del compilador. Aquí hay un código de referencia:

#include <chrono>
#include <cmath>
#include <ctime>
#include <iostream>
#include <vector>


int main(){

    int size = 1000000; // reduce this number in case your program crashes
    int L = 10;

    std::cout << "size=" << size << " L=" << L << std::endl;
    {
        srand( time(0) );
        double * data = new double[size];
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C style heap array:    " << duration << "ms\n";
        delete data;
    }

    {
        srand( 1 + time(0) );
        double data[size]; // technically, non-compliant with C++ standard.
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C99 style stack array: " << duration << "ms\n";
    }

    {
        srand( 2 + time(0) );
        std::vector<double> data( size );
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of std::vector array:     " << duration << "ms\n";
    }

    return 0;
}

Diferentes indicadores de optimización dan diferentes respuestas:

$ g++ -O0 benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181182
Duration of C style heap array:    118441ms
Calculation result is 181240
Duration of C99 style stack array: 104920ms
Calculation result is 181210
Duration of std::vector array:     124477ms
$g++ -O3 benchmark.cpp
$ ./a.out 
size=1000000 L=10
Calculation result is 181213
Duration of C style heap array:    107803ms
Calculation result is 181198
Duration of C99 style stack array: 87247ms
Calculation result is 181204
Duration of std::vector array:     89083ms
$ g++ -Ofast benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181164
Duration of C style heap array:    93530ms
Calculation result is 181179
Duration of C99 style stack array: 80620ms
Calculation result is 181191
Duration of std::vector array:     78830ms

Sus resultados exactos variarán, pero esto es bastante típico en mi máquina.

En mi experiencia, a veces, solo a veces, vector<int>puede ser muchas veces más lento que int[]. Una cosa a tener en cuenta es que los vectores de vectores son muy diferentes int[][]. Como los elementos probablemente no son contiguos en la memoria. Esto significa que puede cambiar el tamaño de diferentes vectores dentro del principal, pero es posible que la CPU no pueda almacenar elementos en caché tan bien como en el caso de int[][].