O std :: vector é muito mais lento que os arrays simples?

Sempre achei que é a sabedoria geral de que o std::vector é “implementado como um array”, blá, blá, blá. Hoje eu desci e testei, e parece não ser assim:

Aqui estão alguns resultados de 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! Não justifica realmente que os comentários de ” vector podem ser mais lentos por alguns nanosecs”.

E o código que usei:

 #include  #include  #include  #include  #include  #include  class TestTimer { public: TestTimer(const std::string & name) : name(name), start(boost::date_time::microsec_clock::local_time()) { } ~TestTimer() { using namespace std; using namespace boost; posix_time::ptime now(date_time::microsec_clock::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 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 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 acabar com esse mito da performance?

Estou usando o modo Release no Visual Studio 2005 .


No Visual C ++ , #define _SECURE_SCL 0 reduz a UseVector de UseVector pela metade (reduzindo-a para 4 segundos). Isso é realmente enorme, IMO.

Usando o seguinte:

g ++ -O3 Time.cpp -I
./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 concluída em 14,626 segundos

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

Mas depois de olhar o código com mais detalhes, isso é esperado; como você percorrer o vetor duas vezes e a matriz apenas uma vez. Nota: quando você resize() o vetor, você não está apenas alocando a memory, mas também correndo através do vetor e chamando o construtor em cada membro.

Reorganizando o código ligeiramente para que o vetor apenas inicialize cada object uma vez:

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

Agora fazendo o mesmo tempo novamente:

g ++ -O3 Time.cpp -I
./a.out
UseVector concluído em 2.216 segundos

O vetor agora apresenta apenas um pouco pior que o array. IMO esta diferença é insignificante e pode ser causada por um monte de coisas não associadas ao teste.

Eu também levaria em conta que você não está inicializando corretamente / Destruindo o object Pixel no método UseArrray() como nenhum construtor / destruidor não é chamado (isso pode não ser um problema para esta class simples, mas algo um pouco mais complexo pointers ou membros com pointers) causará problemas.

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

A otimização ajuda, mas não é suficiente. Com a otimização em diante, ainda vejo uma diferença de desempenho de 2X entre UseArray e 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 o novo [] em vez de malloc

Eu tentei mudar malloc() para new[] em UseArray para que os objects fossem construídos. E mudar de atribuição de campo individual para atribuir uma ocorrência de pixel. Ah, e renomeando 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 mudança para o new[] que será o padrão, construirá todos os Pixels. Parece que o gcc pode otimizar as chamadas de construtor padrão ao usar o new[] , mas não ao usar o vector .

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

Também tentei me livrar da consulta de operator[] triplo operator[] e armazenar em cache a referência a pixels[j] . Isso realmente diminuiu o uso de UseVector! Oops

 for(int j = 0; j < dimension * dimension; ++j) { // Slower than accessing pixels[j] three times. Pixel &pixel = pixels[j]; pixel.r = 255; pixel.g = 0; pixel.b = 0; } # ./vector UseArray completed in 3.226 seconds UseVector completed in 7.54 seconds UseVectorPushBack completed in 9.859 seconds The whole thing completed in 20.626 seconds 

Idéia # 3 - Remover construtores

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

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

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

 # ./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::iterator vez de um índice de loop?

 for (std::vector::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 um desempenho semelhante ao # 2, em que usei um Pixel& reference.

Conclusão

Mesmo que alguns cookies inteligentes descubram como tornar o loop de vetores tão rápido quanto o array, isso não fala bem do comportamento padrão de std::vector . Tanto para o compilador ser inteligente o suficiente para otimizar todo o C ++ ness e fazer contêineres STL tão rápido quanto matrizes-primas.

A linha inferior é que o compilador é incapaz de otimizar afastado as chamadas de construtor padrão não-op quando usando std::vector . Se você usar plain new[] ele os otimizará bem. Mas não com std::vector . Mesmo que você possa rewrite seu código para eliminar as chamadas de construtor que pairam diante do mantra por aqui: "O compilador é mais inteligente que você. O STL é tão rápido quanto o C. Não se preocupe com isso."

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 objects – apenas aloca memory bruta. Que você então trate essa memory como objects sem chamar o construtor é pobre em C ++ (possivelmente inválido – eu deixarei isso para os advogados da linguagem).

Dito isso, simplesmente alterar o malloc para o new Pixel[dimensions*dimensions] e liberar para delete [] pixels não faz muita diferença com a simples implementação do Pixel que você tem. Aqui estão os resultados na minha checkbox (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 assim:

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

temos 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 alinhado para o Pixel, o std :: vector agora bate um array bruto.

Parece que a complexidade da alocação através de std :: vector e std: allocator é demais para ser otimizada de forma tão eficaz quanto um new Pixel[n] simples new Pixel[n] . No entanto, podemos ver que o problema é simplesmente com a alocação não o access ao vetor, ajustando algumas das funções de teste para criar o vetor / array uma vez, movendo-o para fora do loop:

 void UseVector() { TestTimer t("UseVector"); int dimension = 999; std::vector 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; } 

Nós obtemos estes resultados agora:

 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 o std :: vector é comparável a um array bruto para access, mas se você precisar criar e excluir o vetor / array muitas vezes, criar um object complexo consumirá mais tempo do que criar um array simples quando o construtor do elemento não está embutido. Eu não acho que isso seja muito surpreendente.

Esta é uma questão antiga, mas popular.

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

 UseVector completed in 3.74482 seconds UseArray completed in 3.70414 seconds 

O problema fundamental era que, enquanto sua estrutura Pixel era não inicializada, std::vector::resize( size_t, T const&=T() ) pega um Pixel construído padrão e o copia . O compilador não percebeu que estava sendo solicitado a copiar dados não inicializados, de modo que, na verdade, realizou a cópia.

Em C ++ 11, std::vector::resize tem duas sobrecargas. A primeira é std::vector::resize(size_t) , a outra é std::vector::resize(size_t, T const&) . Isso significa que quando você chama o resize sem 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, por isso ignora a passagem sobre o buffer.

(As duas sobrecargas, quando 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 solução push_back também faz a verificação do fencepost, o que a torna mais lenta, de modo que permanece mais lenta que a versão malloc .

exemplo vivo (eu também substitui o timer por chrono::high_resolution_clock ).

Observe que, se você tiver uma estrutura que geralmente requer boot, mas você deseja manipulá-la depois de aumentar seu buffer, poderá fazer isso com um alocador std::vector personalizado. Se você quiser movê-lo para um padrão std::vector mais normal, acredito que o uso cuidadoso de allocator_traits e a sobreposição de == podem causar isso, mas não tenho certeza.

Tente com isso:

 void UseVectorCtor() { TestTimer t("UseConstructor"); for(int i = 0; i < 1000; ++i) { int dimension = 999; std::vector pixels(dimension * dimension, Pixel(255, 0, 0)); } } 

Eu recebo quase exatamente o mesmo desempenho que com array.

A coisa sobre vector é que é uma ferramenta muito mais geral que uma matriz. E isso significa que você tem que considerar como você o usa. Ele pode ser usado de muitas maneiras diferentes, fornecendo funcionalidades que uma matriz nem sequer possui. E se você usá-lo “errado” para o seu propósito, você incorrerá em muita sobrecarga, mas se você usá-lo corretamente, geralmente é basicamente uma estrutura de dados de sobrecarga zero. Nesse caso, o problema é que você inicializou separadamente o vetor (fazendo com que todos os elementos tenham seu ctor padrão chamado) e, em seguida, sobrescrevendo cada elemento individualmente com o valor correto. Isso é muito mais difícil para o compilador otimizar a distância do que quando você faz a mesma coisa com uma matriz. É por isso que o vetor fornece um construtor que permite fazer exatamente isso: inicializar N elementos com valor X

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

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 forma otimizada, o que também é um bom ponto. 🙂

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

Não foi uma comparação justa quando olhei pela primeira vez para o seu código; Eu definitivamente pensei que você não estivesse 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 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; } 

Meus pensamentos eram que, com essa configuração, eles deveriam ser exatamente iguais. 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 tem tudo nos headers, então deveria ter sido possível para o compilador entender tudo o que era necessário.

Meus pensamentos eram que é em 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 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 origem da lentidão, o fato de o vetor usar o construtor de cópia para inicializar os elementos de um object 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ícito 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; } 

Portanto, o Pixel padrão permanece não inicializado, enquanto o restante é inicializado com os valores não inicializados do Pixel padrão.

Comparado 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 

Eles são todos deixados para seus valores não inicializados e sem a dupla iteração sobre a sequência.

Armado com esta informação, como podemos testá-lo? Vamos tentar escrever o construtor de cópia implícito.

 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ê está fazendo centenas de vetores com muita frequência: repensar 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; Espero que você conheça melhor.

Tente desabilitar 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(n) , o padrão constrói um object protótipo T() – o compilador otimizará o construtor vazio – mas então uma cópia de qualquer lixo que esteja nos endereços de memory agora reservados para o object é tomado pelo __uninitialized_fill_n_aux do STL, que faz o loop preenchendo cópias desse object como valores padrão no vetor. Então, “meu” STL não está em loop construindo, mas construindo então loop / copying. É contra-intuitivo, mas eu deveria ter lembrado como eu comentei sobre uma questão recente de stackoverflow sobre este ponto: a construção / cópia pode ser mais eficiente para objects contados de referência, etc.

Assim:

 vector x(n); 

ou

 vector 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 é lixo não inicializado e falha ao otimizar as invocações de construtor de cópia de loop e padrão. Você poderia argumentar com credibilidade que os compiladores absolutamente não deveriam otimizar isso, já que um programador que escreve acima tem uma expectativa razoável de que todos os objects serão idênticos após o loop, mesmo que seja lixo (advertências habituais sobre 'idêntico' / operador == vs memcmp / operator = etc aplicar). Não se pode esperar que o compilador tenha qualquer percepção extra sobre o contexto maior de std :: vector <> ou o uso posterior dos dados que sugerem essa otimização segura.

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

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

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 x(10000); 

Claramente, é uma grande diferença se fizermos 10000 objects independentes versus 10000 referenciando os mesmos dados. Há um argumento razoável de que a vantagem de proteger usuários ocasionais de C ++ de fazerem algo tão caro ultrapassa o custo muito pequeno do mundo real de construção de cópia difícil de otimizar.

RESPOSTA ORIGINAL (para referência / sentido dos comentários): Sem chance. O vetor é tão rápido quanto um array, pelo menos se você reservar espaço de maneira sensata. ...

A resposta de Martin York me incomoda porque parece uma tentativa de escovar o problema de boot sob o tapete. Mas ele está certo em identificar a construção padrão redundante como fonte de problemas de desempenho.

[EDIT: resposta de Martin não sugere mais a alteração do construtor padrão.]

Para o problema imediato, você poderia chamar a versão de 2 parâmetros do vector ctor:

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

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

Para isso, você pode usar um back_insert_iterator , que é um adaptador iterador. Aqui está um exemplo com um vetor de int s, embora a ideia geral funcione tão bem quanto para o Pixel :

 #include  // 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 v; v.reserve(someSize); // To make insertions efficient std::generate_n(std::back_inserter(v), someSize, squares()); 

Alternativamente, você poderia usar copy() ou transform() vez de generate_n() .

A desvantagem é que a lógica para construir os valores iniciais precisa ser movida para uma class separada, o que é menos conveniente do que tê-la no local (embora lambdas em C ++ 1x tornem isso muito mais interessante). Também espero que isso ainda não seja tão rápido quanto uma versão não-STL baseada em malloc() , mas espero que seja próxima, já que ela só faz uma construção para cada elemento.

Os vetores estão chamando construtores de Pixel.

Cada um está causando quase um milhão de corridas que você está cronometrando.

editar: então tem o loop externo de 1 … 1000, então faça um bilhão de chamadas!

edição 2: seria interessante ver a desassembly do caso UseArray. Um otimizador pode otimizar tudo, já que não tem efeito além de queimar a CPU.

Veja como o método push_back no vetor funciona:

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

Depois de chamar os itens push_back X:

  1. O vetor realoca a quantidade de espaço kX em um segundo array.
  2. Copia as inputs da primeira matriz para a segunda.
  3. Descarta o primeiro array.
  4. Now uses the second array as storage until it reaches kX entries.

Repetir. If you’re not reserving space its definitely going to be slower. More than that, if it’s expensive to copy the item then ‘push_back’ like that is going to eat you alive.

As to the vector versus array thing, I’m going to have to agree with the other people. Run in release, turn optimizations on, and put in a few more flags so that the friendly people at Microsoft don’t #@%$^ it up for ya.

One more thing, if you don’t need to resize, use Boost.Array.

Some profiler data (pixel is aligned to 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 */ 

In allocator :

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

vector :

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

array

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

Most of the overhead is in the copy constructor. 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; } 

It has the same performance as an array.

My laptop is Lenova G770 (4 GB RAM).

The OS is Windows 7 64-bit (the one with laptop)

Compiler is MinGW 4.6.1.

The IDE is Code::Blocks .

I test the source codes of the first post.

The results

O2 optimization

UseArray completed in 2.841 seconds

UseVector completed in 2.548 seconds

UseVectorPushBack completed in 11.95 seconds

The whole thing completed in 17.342 seconds

system pause

O3 optimization

UseArray completed in 1.452 seconds

UseVector completed in 2.514 seconds

UseVectorPushBack completed in 12.967 seconds

The whole thing completed in 16.937 seconds

It looks like the performance of vector is worse under O3 optimization.

If you change the loop to

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

The speed of array and vector under O2 and O3 are almost the same.

A better benchmark (I think…), compiler due to optimizations can change code, becouse results of allocated vectors/arrays are not used anywhere. 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 

Compiler:

 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  #include  #include  #include  #include  #include  class TestTimer { public: TestTimer(const std::string & name) : name(name), start(boost::date_time::microsec_clock::local_time()) { } ~TestTimer() { using namespace std; using namespace boost; posix_time::ptime now(date_time::microsec_clock::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 >& results) { TestTimer t("UseVector inner"); for(int i = 0; i < 1000; ++i) { int dimension = 999; std::vector& 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 >& results) { TestTimer t("UseVectorPushBack inner"); for(int i = 0; i < 1000; ++i) { int dimension = 999; std::vector& 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 > vector(1000, std::vector()); UseVector(vector); } } void UseVectorPushBack() { TestTimer t("UseVectorPush"); { std::vector > vector(1000, std::vector()); UseVectorPushBack(vector); } } int main() { TestTimer t1("The whole thing"); UseArray(); UseVector(); UseVectorPushBack(); return 0; } 

With the right options, vectors and arrays can generate identical asm . In these cases, they are of course the same speed, because you get the same executable file either way.

By the way the slow down your seeing in classs using vector also occurs with standard types like int. Heres a multithreaded code:

 #include  #include  #include  #include  #include  #include  #include  #include  #include  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 (input); // reproduce member type vector test= *static_cast*> (info->member); for (int i=info->id; inum) { //printf("am in viterate loop\n"); test[i]; } pthread_exit(NULL); } void * piterate(void * input) { printf("am in piterate\n"); iterate * info=static_cast (input);; int * test=static_cast (info->member); for (int i=info->id; inum) { //printf("am in piterate loop\n"); test[i]; } pthread_exit(NULL); } int main() { cout< <"producing vector of size "< vtest(num); cout< <"produced a vector of size "<member=&pint; ans=pthread_create(&thread[i], NULL, piterate, (void*) it[i]); } for (int i=0; i 

The behavior from the code shows the instantiation of vector is the longest part of the code. Once you get through that bottle neck. The rest of the code runs extremely fast. This is true no matter how many threads you are running on.

By the way ignore the absolutely insane number of includes. I have been using this code to test things for a project so the number of includes keep growing.

I just want to mention that vector (and smart_ptr) is just a thin layer add on top of raw arrays (and raw pointers). And actually the access time of an vector in continuous memory is faster than array. The following code shows the result of initialize and access vector and array.

 #include  #include  #include  #define SIZE 20000 int main() { srand (time(NULL)); vector> 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(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. 

So the speed will be almost the same if you use it properly. (as others mentioned using reserve() or resize()).

Well, because vector::resize() does much more processing than plain memory allocation (by malloc).

Try to put a breakpoint in your copy constructor (define it so that you can breakpoint!) and there goes the additional processing time.

I Have to say I’m not an expert in C++. But to add some experiments results:

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

machine:

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

OS:

 2.6.32-642.13.1.el6.x86_64 

Saída:

 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 

Here the only thing I feel strange is that “UseFillConstructor” performance compared with “UseConstructor”.

O código:

 void UseConstructor() { TestTimer t("UseConstructor"); for(int i = 0; i < 1000; ++i) { int dimension = 999; std::vector 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 pixels(dimension*dimension, Pixel(255,0,0)); } } 

So the additional “value” provided slows down performance quite a lot, which I think is due to multiple call to copy constructor. Mas…

Compile:

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

Saída:

 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 

So in this case, gcc optimization is very important but it can’t help you much when a value is provided as default. This, is against my tuition actually. Hopefully it helps new programmer when choose which vector initialization format.