O std :: vector é muito mais lento que as matrizes simples?

Eu sempre pensei que é a sabedoria geral que std::vectoré "implementada como uma matriz", blá blá blá. Hoje desci e testei, e parece não ser assim:

Aqui estão alguns resultados dos testes:

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

Isso é cerca de 3 a 4 vezes mais lento! Realmente não justifica os comentários " vectorpode ser mais lento para alguns nanossegundos".

E o código que eu usei:

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

Estou fazendo errado ou algo assim? Ou acabei de quebrar esse mito da performance?

Estou usando o modo Release no Visual Studio 2005 .

No Visual C ++ , #define _SECURE_SCL 0reduz UseVectorpela metade (diminuindo para 4 segundos). Isso é realmente enorme, IMO.

Usando o seguinte:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray concluído em
2,196 segundos UseVector concluído em 4,412 segundos
UseVectorPushBack concluído em 8,017 segundos
A coisa toda foi concluída em 14,626 segundos

Portanto, o array é duas vezes mais rápido que o vetor.

Mas, depois de analisar o código com mais detalhes, isso é esperado; conforme você percorre o vetor duas vezes e a matriz apenas uma vez. Nota: quando você resize()vector, você não está apenas alocando a memória, mas também executando o vetor e chamando o construtor em cada membro.

Reorganizando o código levemente para que o vetor inicialize apenas cada objeto uma vez:

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

Agora, fazendo o mesmo tempo novamente:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector concluído em 2,216 segundos

O vetor agora apresenta desempenho apenas ligeiramente pior que o da matriz. Na OMI, essa diferença é insignificante e pode ser causada por várias coisas não associadas ao teste.

Eu também consideraria que você não está inicializando / destruindo corretamente o objeto Pixel no UseArrray()método, pois nem o construtor / destruidor é chamado (isso pode não ser um problema para essa classe simples, mas algo um pouco mais complexo (por exemplo, com ponteiros ou membros com ponteiros) causará problemas.

Ótima pergunta. Eu vim aqui esperando encontrar alguma correção simples que agilizasse os testes de vetores. Isso não funcionou como eu esperava!

A otimização ajuda, mas não é suficiente. Com a otimização ativada, ainda vejo uma diferença de desempenho 2X entre o UseArray e o UseVector. Curiosamente, o UseVector foi significativamente mais lento que o UseVectorPushBack sem otimização.

# 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

Idéia # 1 - Use novo [] em vez de malloc

Tentei mudar malloc()para new[]no UseArray para que os objetos fossem construídos. E mudando da atribuição de campo individual para a atribuição de uma instância de Pixel. Ah, e renomear a variável de loop interno para 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;
    }
}

Surpreendentemente (para mim), nenhuma dessas mudanças fez qualquer diferença. Nem mesmo a alteração na new[]qual o padrão será construído em todos os pixels. Parece que o gcc pode otimizar as chamadas de construtor padrão ao usar new[], mas não ao usar vector.

Idéia # 2 - Remover chamadas repetidas do operador []

Também tentei me livrar da operator[]pesquisa tripla e armazenar em cache a referência pixels[j]. Isso realmente desacelerou o UseVector! Opa

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

Idéia # 3 - Remover construtores

Que tal remover completamente os construtores? Talvez o gcc possa otimizar a construção de todos os objetos quando os vetores são criados. O que acontece se mudarmos Pixel para:

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

Resultado: cerca de 10% mais rápido. Ainda mais lento que um array. Hum.

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

Idéia # 4 - Use o iterador em vez do índice de loop

Que tal usar um vector<Pixel>::iteratoríndice em vez de um loop?

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

Não, não é diferente. Pelo menos não é mais lento. Eu pensei que isso teria desempenho semelhante ao # 2, onde eu usei uma Pixel&referência.

Conclusão

Mesmo que algum cookie inteligente descubra como fazer o loop de vetor tão rápido quanto o array, isso não fala bem do comportamento padrão de std::vector. O suficiente para o compilador ser inteligente o suficiente para otimizar todo o C ++ ness e tornar os contêineres STL tão rápidos quanto os arrays brutos.

O ponto principal é que o compilador não pode otimizar as chamadas de construtor padrão no-op ao usar std::vector. Se você usar simples, new[]ele os otimiza muito bem. Mas não com std::vector. Mesmo que você possa reescrever seu código para eliminar as chamadas do construtor que aparecem diante do mantra por aqui: "O compilador é mais inteligente que você. O STL é tão rápido quanto o normal C. Não se preocupe."

Esta é uma pergunta antiga, mas popular.

Neste ponto, muitos programadores estarão trabalhando no C ++ 11. E no C ++ 11, o código do OP, como escrito, é executado igualmente rápido para UseArrayou UseVector.

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

O problema fundamental era que, enquanto sua Pixelestrutura não foi inicializada, cria std::vector<T>::resize( size_t, T const&=T() )um padrão Pixele o copia . O compilador não percebeu que estava sendo solicitado a copiar dados não inicializados e, portanto, executou a cópia.

No C ++ 11, std::vector<T>::resizetem duas sobrecargas. O primeiro é std::vector<T>::resize(size_t), o outro é std::vector<T>::resize(size_t, T const&). Isso significa que quando você invoca resizesem um segundo argumento, ele simplesmente constrói o padrão, e o compilador é inteligente o suficiente para perceber que a construção padrão não faz nada, portanto ignora a passagem sobre o buffer.

(As duas sobrecargas foram adicionadas para lidar com tipos móveis, construtíveis e não copiáveis ​​- a melhoria de desempenho ao trabalhar com dados não inicializados é um bônus).

A push_backsolução também faz a verificação de vedação, o que a torna mais lenta, permanecendo mais lenta que a mallocversão.

exemplo ao vivo (também substituí o temporizador por chrono::high_resolution_clock).

Observe que, se você possui uma estrutura que geralmente requer inicialização, mas deseja manipulá-la após aumentar seu buffer, pode fazer isso com um std::vectoralocador personalizado . Se você quiser movê-lo para um estado mais normal std::vector, acredito que o uso cuidadoso allocator_traitse a substituição de ==podem fazer isso, mas não tenho certeza.

Para ser justo, você não pode comparar uma implementação C ++ com uma implementação C, como eu chamaria sua versão malloc. O malloc não cria objetos - apenas aloca memória não processada. O fato de você tratar essa memória como objetos sem chamar o construtor é um C ++ ruim (possivelmente inválido - deixarei isso para os advogados de linguagem).

Dito isso, simplesmente alterar o malloc para new Pixel[dimensions*dimensions]e free to delete [] pixelsnão faz muita diferença com a implementação simples do Pixel que você possui. Aqui estão os resultados na minha caixa (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

Mas com uma ligeira mudança, as mesas viram:

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 desta maneira:

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

obtemos resultados muito 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

Com um construtor não embutido para Pixel, std :: vector agora supera uma matriz bruta.

Parece que a complexidade da alocação por meio de std :: vector e std: alocador é demais para ser otimizada de maneira tão eficaz quanto simples new Pixel[n]. No entanto, podemos ver que o problema está simplesmente na alocação e não no acesso ao vetor, ajustando algumas das funções de teste para criar o vetor / matriz uma vez movendo-o para fora do loop:

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

e

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

Agora obtemos esses 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

O que podemos aprender com isso é que std :: vector é comparável a uma matriz bruta de acesso, mas se você precisar criar e excluir o vetor / matriz muitas vezes, a criação de um objeto complexo consumirá mais tempo do que a criação de uma matriz simples quando o construtor do elemento não estiver embutido. Não acho que isso seja muito surpreendente.

Tente com isto:

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

Eu tenho quase exatamente o mesmo desempenho que com o array.

A questão vectoré que é uma ferramenta muito mais geral do que uma matriz. E isso significa que você deve considerar como usá-lo. Ele pode ser usado de várias maneiras diferentes, fornecendo funcionalidades que nem mesmo uma matriz possui. E se você usá-lo "errado" para o seu objetivo, gera muita sobrecarga, mas se usá-lo corretamente, geralmente é basicamente uma estrutura de dados com zero sobrecarga. Nesse caso, o problema é que você inicializou o vetor separadamente (fazendo com que todos os elementos tivessem seu nome padrão chamado) e, em seguida, substituiu cada elemento individualmente com o valor correto. Isso é muito mais difícil para o compilador otimizar o processo do que quando você faz a mesma coisa com uma matriz. É por isso que o vetor fornece um construtor que permite fazer exatamente isso:NX.

E quando você usa isso, o vetor é tão rápido quanto uma matriz.

Então não, você não quebrou o mito da performance. Mas você mostrou que isso só é verdade se você usar o vetor de maneira ideal, o que também é um bom argumento. :)

Pelo lado positivo, é realmente o uso mais simples que acaba sendo o mais rápido. Se você contrastar meu snippet de código (uma única linha) com a resposta de John Kugelman, contendo montes e montes de ajustes e otimizações, que ainda não eliminam completamente a diferença de desempenho, é bem claro que, apesar de tudo, vectoré muito inteligente. Você não precisa pular aros para obter velocidade igual a uma matriz. Pelo contrário, você deve usar a solução mais simples possível.

Não foi uma comparação justa quando olhei seu código pela primeira vez; Eu definitivamente pensei que você não estava comparando maçãs com maçãs. Então pensei: vamos chamar construtores e destruidores em todos os testes; e depois compare.

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

Meu pensamento era que, com essa configuração, eles deveriam ser exatamente os mesmos. Acontece que eu estava errado.

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

Então, por que essa perda de desempenho de 30% ocorreu? O STL possui tudo nos cabeçalhos, portanto, deveria ter sido possível para o compilador entender tudo o que era necessário.

Meu pensamento era que é como o loop inicializa todos os valores para o construtor padrão. Então eu fiz um teste:

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

Os resultados foram como eu suspeitava:

Default Constructed: 1
Copy Constructed: 300

Essa é claramente a fonte da desaceleração, o fato de o vetor usar o construtor de cópia para inicializar os elementos de um objeto construído padrão.

Isso significa que a seguinte ordem de pseudo-operação está acontecendo durante a construção do vetor:

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

Que, devido ao construtor de cópia implícita feito pelo compilador, é expandido para o seguinte:

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

Assim, o padrão Pixelcontinua a ser inicializado-un, enquanto o resto são inicializados com o padrão Pixel's inicializado-un valores.

Em comparação com a situação alternativa com 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 são deixados com seus valores não inicializados e sem a iteração dupla sobre a sequência.

Armado com esta informação, como podemos testá-la? Vamos tentar sobrescrever o construtor de cópias implícitas.

Pixel(const Pixel&) {}

E os resultados?

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

Então, em resumo, se você estiver criando centenas de vetores com muita frequência: repense seu algoritmo .

Em qualquer caso, a implementação do STL não é mais lenta por algum motivo desconhecido, apenas faz exatamente o que você pede; esperando que você saiba melhor.

Tente desativar os iteradores verificados e criar no modo de liberação. Você não deve ver muita diferença de desempenho.

O STL do GNU (e outros), dado vector<T>(n), o padrão constrói um objeto prototípico T()- o compilador otimizará o construtor vazio - mas, em seguida, uma cópia do lixo que estiver nos endereços de memória agora reservados para o objeto é obtida pelos STLs __uninitialized_fill_n_aux, que loops que preenchem cópias desse objeto como os valores padrão no vetor. Portanto, "my" STL não está construindo um loop, mas construindo um loop / cópia. É contra-intuitivo, mas eu deveria ter lembrado quando comentei uma recente pergunta sobre o stackoverflow sobre esse ponto: a construção / cópia pode ser mais eficiente para objetos de referência contados etc.

Assim:

vector<T> x(n);

ou

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

é - em muitas implementações de STL - algo como:

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

O problema é que a geração atual de otimizadores de compilador não parece funcionar com a percepção de que temp é um lixo não inicializado e falha ao otimizar as invocações de loop e construtor de cópia padrão. Você pode argumentar com credibilidade que os compiladores absolutamente não devem otimizar isso, pois um programador que escrever o acima tem uma expectativa razoável de que todos os objetos serão idênticos após o loop, mesmo que lixo (advertências comuns sobre 'idêntico' / operador == vs memcmp / operator = etc aplicável). Não se pode esperar que o compilador tenha uma visão extra do contexto maior de std :: vector <> ou o uso posterior dos dados que sugerem que essa otimização é segura.

Isso pode ser contrastado com a implementação direta mais óbvia:

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

O que podemos esperar que um compilador otimize.

Para ser um pouco mais explícito sobre a justificativa para esse aspecto do comportamento do vetor, considere:

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

Claramente, é uma grande diferença se criarmos 10000 objetos independentes versus 10000 fazendo referência aos mesmos dados. Há um argumento razoável de que a vantagem de proteger usuários casuais de C ++ de fazer algo acidentalmente supera o custo muito pequeno do mundo real da construção de cópias difíceis de otimizar.

RESPOSTA ORIGINAL (para referência / interpretação dos comentários): Sem chance. o vetor é tão rápido quanto uma matriz, pelo menos se você reservar espaço sensatamente. ...

A resposta de Martin York me incomoda porque parece uma tentativa de escovar o problema de inicialização debaixo do tapete. Mas ele tem razão em identificar a construção padrão redundante como a fonte de problemas de desempenho.

[EDIT: A resposta de Martin não sugere mais alterar o construtor padrão.]

Para o problema imediato em questão, você certamente poderia chamar a versão de 2 parâmetros do vector<Pixel>ctor:

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

Isso funciona se você deseja inicializar com um valor constante, que é um caso comum. Mas o problema mais geral é: como você pode inicializar eficientemente com algo mais complicado que um valor constante?

Para isso, você pode usar a back_insert_iterator, que é um adaptador iterador. Aqui está um exemplo com um vetor de ints, embora a ideia geral funcione igualmente bem 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());

Como alternativa, você pode usar copy()ou em transform()vez de generate_n().

A desvantagem é que a lógica para construir os valores iniciais precisa ser movida para uma classe separada, o que é menos conveniente do que tê-lo no lugar (embora as lambdas em C ++ 1x tornem isso muito melhor). Também espero que isso ainda não seja tão rápido quanto uma malloc()versão não-STL baseada em, mas espero que seja próxima, pois ele faz apenas uma construção para cada elemento.

Os vetores também estão chamando construtores de Pixel.

Cada um deles está causando quase um milhão de execuções de ctor que você está cronometrando.

edit: então há o loop externo 1 ... 1000, então faça com que um bilhão de ctor ligue!

edit 2: seria interessante ver a desmontagem do caso UseArray. Um otimizador pode otimizar tudo, já que não tem outro efeito senão queimar a CPU.

Veja como o push_backmétodo no vetor funciona:

1. O vetor aloca uma quantidade X de espaço quando é inicializado.
2. Conforme indicado abaixo, ele verifica se há espaço na matriz subjacente atual para o item.
3. Faz uma cópia do item na chamada push_back.

Depois de chamar os push_backitens X:

3. O vetor realoca a quantidade de espaço kX em uma segunda matriz.
4. Ele copia as entradas da primeira matriz para a segunda.
5. Descarta a primeira matriz.
6. Agora usa a segunda matriz como armazenamento até atingir as entradas do kX.

Repetir. Se você não está no reservingespaço, definitivamente será mais lento. Mais do que isso, se for caro copiar o item, então 'push_back' assim o comerá vivo.

Quanto à vectorcoisa versus matriz, vou ter que concordar com as outras pessoas. Execute a liberação, ative as otimizações e coloque mais algumas bandeiras para que as pessoas amigáveis ​​da Microsoft não # #% $ ^ façam isso por você.

Mais uma coisa, se você não precisar redimensionar, use o Boost.Array.

Alguns dados do criador de perfil (o pixel está alinhado 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
 */

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

matriz

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

A maior parte da sobrecarga está no construtor de cópias. Por exemplo,

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

Tem o mesmo desempenho que uma matriz.

Meu laptop é o Lenova G770 (4 GB de RAM).

O sistema operacional é o Windows 7 de 64 bits (aquele com laptop)

O compilador é o MinGW 4.6.1.

O IDE é Code :: Blocks .

Eu testo os códigos-fonte do primeiro post.

Os resultados

Otimização de O2

UseArray concluído em 2,841 segundos

UseVector concluído em 2.548 segundos

UseVectorPushBack concluído em 11,95 segundos

A coisa toda concluída em 17,342 segundos

pausa no sistema

Otimização de O3

UseArray concluído em 1.452 segundos

UseVector concluído em 2.514 segundos

UseVectorPushBack concluído em 12,967 segundos

A coisa toda concluída em 16.937 segundos

Parece que o desempenho do vetor é pior na otimização do O3.

Se você alterar o loop para

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

A velocidade da matriz e do vetor sob O2 e O3 é quase a mesma.

Uma referência melhor (eu acho ...), o compilador devido às otimizações pode alterar o código, porque os resultados dos vetores / matrizes alocados não são usados ​​em lugar algum. 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

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

Eu fiz alguns testes extensivos que eu queria por um tempo agora. Pode muito bem compartilhar isso.

Esta é a minha máquina de inicialização dupla i7-3770, 16 GB de RAM, x86_64, no Windows 8.1 e no Ubuntu 16.04. Mais informações e conclusões, comentários abaixo. Testou o MSVS 2017 e o g ++ (no Windows e no Linux).

Programa de teste

#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 uma média de 10 execuções.
• Inicialmente, também realizei testes std::sort()(você pode vê-lo comentado), mas os removi mais tarde porque não havia diferenças significativas.

Minhas conclusões e observações

• observe como a matriz global de estilo c leva quase tanto tempo quanto a matriz heap de estilo c
• Em todos os testes, notei uma estabilidade notável no std::array variações de tempo entre execuções consecutivas, enquanto outras, especialmente as estruturas std :: data, variaram bastante em comparação
• A otimização da O3 não mostrou diferenças de tempo notáveis
• A remoção da otimização no Windows cl (sem -O2) e no g ++ (Win / Linux não -O2, sem -march = nativo) aumenta o tempo SIGNIFICANTEMENTE. Particularmente para estruturas std :: data. Tempos gerais mais altos no MSVS do que no g ++, mas std::arraymatrizes no estilo c mais rapidamente no Windows sem otimização
• O g ++ produz código mais rápido que o compilador da microsoft (aparentemente ele roda mais rápido, mesmo no Windows).

Veredito

Claro que isso é código para uma compilação otimizada. E já que a pergunta era sobrestd::vector sim, é sim! matrizes mais lentas do que simples (otimizadas / não otimizadas). Mas quando você está fazendo um benchmark, naturalmente deseja produzir código otimizado.

A estrela do show para mim foi std::array.

Com as opções corretas, vetores e matrizes podem gerar asm idênticas . Nesses casos, é claro que eles têm a mesma velocidade, porque você obtém o mesmo arquivo executável de qualquer maneira.

A propósito, a desaceleração da visualização em classes usando vetor também ocorre com tipos padrão como int. Heres um código multithread:

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

O comportamento do código mostra que a instanciação do vetor é a parte mais longa do código. Depois de passar pelo gargalo da garrafa. O restante do código é executado extremamente rápido. Isso é verdade, não importa quantos threads você esteja executando.

A propósito, ignore o número absolutamente insano de inclusões. Eu tenho usado esse código para testar as coisas de um projeto, para que o número de inclusões continue crescendo.

Eu só quero mencionar que vetor (e smart_ptr) é apenas uma fina camada adicionada em cima de matrizes brutas (e ponteiros brutos). E, na verdade, o tempo de acesso de um vetor na memória contínua é mais rápido que o array. O código a seguir mostra o resultado da inicialização e acesso ao vetor e 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;
}

A saída é:

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

Portanto, a velocidade será quase a mesma se você a usar corretamente. (como outros mencionados usando reserve () ou redimensionar ()).

Bem, porque vector :: resize () faz muito mais processamento do que alocação de memória simples (por malloc).

Tente colocar um ponto de interrupção no construtor de cópias (defina-o para que você possa interromper!) E o tempo de processamento adicional será gasto.

Devo dizer que não sou especialista em C ++. Mas, para adicionar alguns resultados de experimentos:

compile: 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

Resultado:

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

Aqui, a única coisa que me parece estranha é o desempenho do "UseFillConstructor" em comparação com o "UseConstructor".

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

Portanto, o "valor" adicional fornecido diminui bastante o desempenho, o que eu acho que é devido à chamada múltipla para copiar o construtor. Mas...

Compilar:

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

Resultado:

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

Portanto, nesse caso, a otimização do gcc é muito importante, mas não pode ajudá-lo muito quando um valor é fornecido como padrão. Isso é contra a minha mensalidade, na verdade. Espero que ajude o novo programador a escolher qual formato de inicialização do vetor.

Parece depender dos sinalizadores do compilador. Aqui está um código de referência:

#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 sinalizadores de otimização fornecem respostas diferentes:

$ 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

Seus resultados exatos variam, mas isso é bastante típico na minha máquina.

Na minha experiência, às vezes, apenas às vezes, vector<int>pode ser muitas vezes mais lento que int[]. Uma coisa a ter em mente é que os vetores de vetores são muito diferentes int[][]. Como os elementos provavelmente não são contíguos na memória. Isso significa que você pode redimensionar vetores diferentes dentro do principal, mas a CPU pode não ser capaz de armazenar em cache elementos, assim como no caso de int[][].