Usando arrays ou std :: vectors em C ++, qual é a lacuna de desempenho?

Em nosso curso C ++, eles sugerem não usar matrizes C ++ em novos projetos. Tanto quanto sei, o próprio Stroustroup sugere não usar matrizes. Mas existem diferenças significativas de desempenho?

Usando arrays C ++ com new (isto é, usando arrays dynamics) deve ser evitado. Existe o problema que você tem de controlar o tamanho, e você precisa excluí-los manualmente e fazer todo o tipo de tarefas domésticas.

Usar matrizes na pilha também é desencorajado porque você não tem verificação de intervalo e, ao passar a matriz, perderá qualquer informação sobre seu tamanho (conversão de matriz em ponteiro). Você deve usar o boost::array nesse caso, que envolve um array C ++ em uma pequena class e fornece uma function de size e iteradores para iterar sobre ele.

Agora os arrays std :: vector vs. C ++ nativos (retirados da internet):

 // Comparison of assembly code generated for basic indexing, dereferencing, // and increment operations on vectors and arrays/pointers. // Assembly code was generated by gcc 4.1.0 invoked with g++ -O3 -S on a // x86_64-suse-linux machine. #include  struct S { int padding; std::vector v; int * p; std::vector::iterator i; }; int pointer_index (S & s) { return sp[3]; } // movq 32(%rdi), %rax // movl 12(%rax), %eax // ret int vector_index (S & s) { return sv[3]; } // movq 8(%rdi), %rax // movl 12(%rax), %eax // ret // Conclusion: Indexing a vector is the same damn thing as indexing a pointer. int pointer_deref (S & s) { return *sp; } // movq 32(%rdi), %rax // movl (%rax), %eax // ret int iterator_deref (S & s) { return *si; } // movq 40(%rdi), %rax // movl (%rax), %eax // ret // Conclusion: Dereferencing a vector iterator is the same damn thing // as dereferencing a pointer. void pointer_increment (S & s) { ++sp; } // addq $4, 32(%rdi) // ret void iterator_increment (S & s) { ++si; } // addq $4, 40(%rdi) // ret // Conclusion: Incrementing a vector iterator is the same damn thing as // incrementing a pointer. 

Nota: Se você alocar arrays com new e alocar objects não de class (como plain int ) ou classs sem um construtor definido pelo usuário e não desejar ter seus elementos inicializados inicialmente, o uso de arrays alocados pode ter vantagens de desempenho porque std::vector inicializa todos os elementos para valores padrão (0 para int, por exemplo) em construção (créditos para @bernie por lembrar de mim).

Preâmbulo para pessoas micro otimizador

Lembrar:

“Os programadores gastam muito tempo pensando ou se preocupando com a velocidade de partes não-críticas de seus programas, e essas tentativas de eficiência têm um forte impacto negativo quando a debugging e a manutenção são consideradas. Devemos esquecer pequenas eficiências, digamos sobre 97% do tempo: a otimização prematura é a raiz de todo o mal. No entanto, não devemos deixar passar nossas oportunidades nesse nível crítico de 3% “.

(Graças à metamorfose para a citação completa)

Não use um array C em vez de um vetor (ou qualquer outro) só porque você acredita que é mais rápido, já que deveria ser de nível inferior. Você estaria errado.

Use por padrão vector (ou o container seguro adaptado à sua necessidade), e se o seu profiler disser que é um problema, veja se você pode otimizá-lo, seja usando um algoritmo melhor ou alterando o container.

Dito isto, podemos voltar à questão original.

Matriz Estática / Dinâmica?

As classs de matriz C ++ são mais bem comportadas do que a matriz C de baixo nível porque elas sabem muito sobre si mesmas e podem responder a perguntas que as matrizes C não podem. Eles são capazes de limpar depois de si mesmos. E mais importante, eles geralmente são escritos usando templates e / ou inlining, o que significa que o que parece ser muito código nas resoluções de debugging para pouco ou nenhum código produzido na versão build, não significa nenhuma diferença em relação à concorrência menos segura.

Tudo sumdo, cai em duas categorias:

Matrizes dinâmicas

Usar um ponteiro para um array malloc-ed / new-ed será, na melhor das hipóteses, tão rápido quanto a versão std :: vector, e muito menos seguro (veja post do litb ).

Então use um std :: vector.

Matrizes estáticas

Usando uma matriz estática será na melhor das hipóteses:

  • tão rápido quanto a versão std :: array
  • e muito menos seguro.

Então use um std :: array .

Memória não inicializada

Às vezes, usar um vector vez de um buffer bruto incorre em um custo visível porque o vector inicializará o buffer na construção, enquanto o código que ele substitui não o fez, como observou bernie em sua resposta .

Se este for o caso, então você pode manipulá-lo usando um unique_ptr invés de um vector ou, se o caso não for excepcional em sua linha de código, realmente escreva um buffer_owner class que possua essa memory, e forneça access fácil e seguro a ela. isso, incluindo bônus como resize (usando realloc ?), ou o que você precisar.

Vetores são matrizes sob o capô. O desempenho é o mesmo.

Um lugar onde você pode encontrar um problema de desempenho, não está dimensionando corretamente o vetor para começar.

Como um vetor preenche, ele se resizeá, e isso pode implicar, uma nova alocação de matriz, seguida por n construtores de cópia, seguidos de cerca de n chamadas de destruidor, seguidas por uma exclusão de matriz.

Se o seu constructo / destruição é caro, é muito melhor que o vetor tenha o tamanho correto para começar.

Existe uma maneira simples de demonstrar isso. Crie uma class simples que mostra quando é construída / destruída / copiada / atribuída. Crie um vetor dessas coisas e comece a empurrá-las no final do vetor. Quando o vetor se enche, haverá uma cascata de atividade conforme o vetor é redimensionado. Em seguida, tente novamente com o vetor dimensionado para o número esperado de elementos. Você verá a diferença.

Para responder a algo que Mehrdad disse:

No entanto, pode haver casos em que você ainda precisa de matrizes. Ao fazer interface com código de baixo nível (ou seja, assembly) ou bibliotecas antigas que exigem matrizes, talvez você não consiga usar vetores.

Não é verdade em tudo. Os vetores se degradam muito bem em arrays / pointers se você usar:

 vector vector; vector.push_back(42); double *array = &(*vector.begin()); // pass the array to whatever low-level code you have 

Isso funciona para todas as principais implementações de STL. No próximo padrão, será necessário trabalhar (mesmo que seja ótimo hoje).

Você tem ainda menos razões para usar matrizes simples no C ++ 11.

Existem 3 tipos de arrays na natureza, do mais rápido ao mais lento, dependendo dos resources que eles têm (claro que a qualidade da implementação pode tornar as coisas realmente rápidas mesmo para o caso 3 na lista):

  1. Estático com tamanho conhecido em tempo de compilation. — std::array
  2. Dinâmico com tamanho conhecido em tempo de execução e nunca redimensionado. A otimização típica aqui é que, se a matriz puder ser alocada diretamente na pilha. – Não disponível Talvez dynarray em C ++ TS após C + + 14. Em C existem VLAs
  3. Dinâmico e redimensionável em tempo de execução. — std::vector

Para 1. arrays estáticos simples com número fixo de elementos, use std::array em C ++ 11.

Para 2. arrays de tamanho fixo especificados em tempo de execução, mas isso não mudará seu tamanho, há uma discussão em C ++ 14, mas ele foi movido para uma especificação técnica e feito de C ++ 14 finalmente.

Para 3. std::vector geralmente pede memory no heap . Isso pode ter consequências de desempenho, embora você possa usar std::vector> para melhorar a situação com um alocador personalizado. A vantagem em comparação com T mytype[] = new MyType[n]; é que você pode redimensioná-lo e que ele não irá decair para um ponteiro, como os arrays simples fazem.

Use os tipos de biblioteca padrão mencionados para evitar que as matrizes diminuam para pointers . Você economizará tempo de debugging e o desempenho será exatamente igual ao dos arrays simples, se você usar o mesmo conjunto de resources.

O STL é uma biblioteca altamente otimizada. Na verdade, é até sugerido o uso de STL em jogos em que o alto desempenho pode ser necessário. Os arrays são muito propensos a erros para serem usados ​​em tarefas do dia a dia. Os compiladores de hoje também são muito inteligentes e podem realmente produzir excelentes códigos com STL. Se você sabe o que está fazendo, o STL normalmente pode fornecer o desempenho necessário. Por exemplo, ao inicializar vetores para o tamanho requerido (se você souber desde o início), você pode basicamente obter o desempenho da matriz. No entanto, pode haver casos em que você ainda precisa de matrizes. Ao fazer interface com código de baixo nível (ou seja, assembly) ou bibliotecas antigas que exigem matrizes, talvez você não consiga usar vetores.

Vá com o STL. Não há penalidade de desempenho. Os algoritmos são muito eficientes e fazem um bom trabalho ao lidar com os tipos de detalhes que a maioria de nós não pensaria.

Sobre a contribuição de duli .

A conclusão é que as matrizes de inteiros são mais rápidas que os vetores de inteiros (5 vezes no meu exemplo). No entanto, matrizes e vetores são colocados na mesma velocidade para dados mais complexos / não alinhados.

Se você compilar o software no modo de debugging, muitos compiladores não irão embutir as funções do acessador do vetor. Isso tornará a implementação do vetor stl muito mais lenta em circunstâncias em que o desempenho é um problema. Ele também tornará o código mais fácil de depurar, já que você pode ver no depurador quanta memory foi alocada.

No modo otimizado, esperaria que o vetor stl se aproximasse da eficiência de um array. Isso ocorre porque muitos dos methods vetoriais estão agora embutidos.

A diferença de desempenho entre os dois é muito dependente da implementação – se você comparar um std :: vector mal implementado a uma implementação de array ideal, o array ganharia, mas o inverteria e o vetor venceria …

Contanto que você compare maçãs com maçãs (tanto a matriz quanto o vetor tenham um número fixo de elementos, ou ambos sejam redimensionados dinamicamente), eu pensaria que a diferença de desempenho é insignificante, desde que você siga a prática de codificação STL. Não se esqueça que o uso de contêineres C ++ padrão também permite que você faça uso dos algoritmos pré-definidos que fazem parte da biblioteca C ++ padrão e a maioria deles terá melhor desempenho do que a implementação média do mesmo algoritmo que você construiu .

Dito isto, IMHO o vetor ganha em um cenário de debugging com um STL de debugging, já que a maioria das implementações STL com um modo de debugging adequado pode, pelo menos, destacar os erros típicos cometidos por pessoas ao trabalhar com contêineres padrão.

Ah, e não se esqueça de que a matriz e o vetor compartilham o mesmo layout de memory para que você possa usar vetores para transmitir dados ao código legado C ou C ++ que espera matrizes básicas. Tenha em mente que a maioria das apostas está desligada nesse cenário, e você está lidando com a memory bruta novamente.

Se você não precisar ajustar dinamicamente o tamanho, terá a sobrecarga de memory de salvar a capacidade (um ponteiro / tamanho_t). É isso aí.

Pode haver alguns casos extremos em que você tem um access vetorial dentro de uma function inline dentro de uma function inline, onde você foi além do que o compilador inline e forçará uma chamada de function. Isso seria tão raro a ponto de não valer a pena se preocupar – em geral, eu concordaria com o litb .

Estou surpreso que ninguém tenha mencionado isso ainda – não se preocupe com o desempenho até que se prove que é um problema, então faça um benchmark.

Eu diria que a principal preocupação não é o desempenho, mas a segurança. Você pode cometer muitos erros com matrizes (considere resize, por exemplo), onde um vetor pouparia muita dor.

Os vetores usam um pouco mais de memory que os arrays, pois contêm o tamanho do array. Eles também aumentam o tamanho do disco rígido dos programas e, provavelmente, a pegada de memory dos programas. Esses aumentos são pequenos, mas podem ser importantes se você estiver trabalhando com um sistema embarcado. Embora a maioria dos lugares onde essas diferenças importam sejam locais onde você usaria C em vez de C ++.

O seguinte teste simples:

Explicação do teste de desempenho do Vector array vs C ++

contradiz as conclusões de “Comparação do código assembly gerado para operações básicas de indexação, desreferenciação e incremento em vetores e arrays / pointers”.

Deve haver uma diferença entre as matrizes e os vetores. O teste diz que sim … apenas tente, o código está lá …

Às vezes, as matrizes são realmente melhores que vetores. Se você está sempre manipulando um conjunto de objects de tamanho fixo, os arrays são melhores. Considere os seguintes trechos de código:

 int main() { int v[3]; v[0]=1; v[1]=2;v[2]=3; int sum; int starttime=time(NULL); cout < < starttime << endl; for (int i=0;i<50000;i++) for (int j=0;j<10000;j++) { X x(v); sum+=x.first(); } int endtime=time(NULL); cout << endtime << endl; cout << endtime - starttime << endl; } 

onde a versão do vetor de X é

 class X { vector vec; public: X(const vector& v) {vec = v;} int first() { return vec[0];} }; 

e a versão do array do X é:

 class X { int f[3]; public: X(int a[]) {f[0]=a[0]; f[1]=a[1];f[2]=a[2];} int first() { return f[0];} }; 

A versão da matriz de main () será mais rápida porque estamos evitando a sobrecarga de "novo" toda vez no loop interno.

(Este código foi postado no comp.lang.c ++ por mim).

Definitivamente há um impacto no desempenho ao usar um std::vector versus um array raw quando você deseja um buffer não inicializado (por exemplo, para usar como destino para memcpy() ). Um std::vector irá inicializar todos os seus elementos usando o construtor padrão. Uma matriz não será.

A especificação c ++ para o construtor std:vector usando um argumento de count (é a terceira forma) declara:

`Constrói um novo contêiner a partir de uma variedade de fonts de dados, opcionalmente usando uma alocação de alocador fornecida pelo usuário.

3) Constrói o container com a contagem de instâncias inseridas por padrão de T. Nenhuma cópia é feita.

Complexidade

2-3) Linear em contagem

Um array bruto não incorre nesse custo de boot.

Veja também Como posso evitar std :: vector <> para inicializar todos os seus elementos?