Usando matrizes ou std :: vectors em C ++, qual é a diferença de desempenho?

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

O uso de matrizes C ++ com new(ou seja, matrizes dinâmicas) deve ser evitado. Existe o problema de manter o controle do tamanho e excluí-los manualmente e fazer todo o tipo de tarefas domésticas.

O uso de matrizes na pilha também é desencorajado, porque você não tem verificação de alcance, e passar a matriz perderá qualquer informação sobre seu tamanho (conversão de matriz em ponteiro). boost::arrayNesse caso, você deve usar , que agrupa uma matriz C ++ em uma classe pequena e fornece uma sizefunção e iteradores para iterar sobre ela.

Agora as matrizes std :: vector vs. C ++ nativas (extraídas 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 <vector>

struct S
{
  int padding;

  std::vector<int> v;
  int * p;
  std::vector<int>::iterator i;
};

int pointer_index (S & s) { return s.p[3]; }
  // movq    32(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

int vector_index (S & s) { return s.v[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 *s.p; }
  // movq    32(%rdi), %rax
  // movl    (%rax), %eax
  // ret

int iterator_deref (S & s) { return *s.i; }
  // 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) { ++s.p; }
  // addq    $4, 32(%rdi)
  // ret

void iterator_increment (S & s) { ++s.i; }
  // addq    $4, 40(%rdi)
  // ret

// Conclusion: Incrementing a vector iterator is the same damn thing as 
// incrementing a pointer.

Nota: Se você alocar matrizes com newobjetos não pertencentes a classe (como simples int) ou classes sem um construtor definido pelo usuário e não desejar inicializar seus elementos inicialmente, o uso de newmatrizes alocadas poderá ter vantagens de desempenho, pois std::vectorinicializa todos os elementos para valores padrão (0 para int, por exemplo) na construção (créditos para @bernie por me lembrar).

Preâmbulo para pessoas com micro-otimizadores

Lembrar:

"Os programadores perdem muito tempo pensando ou se preocupando com a velocidade das partes não críticas de seus programas, e essas tentativas de eficiência realmente têm um forte impacto negativo quando a depuração e a manutenção são consideradas. Devemos esquecer as pequenas eficiências, por exemplo, sobre 97% das vezes: a otimização prematura é a raiz de todo mal. No entanto, não devemos desperdiçar nossas oportunidades nesses 3% críticos ".

(Obrigado à metamorfose pela cotação completa)

Não use uma matriz C em vez de um vetor (ou o que seja) apenas porque você acredita que é mais rápido, pois deveria ser de nível inferior. Você estaria errado.

Use por vetor padrão (ou o contêiner seguro adaptado às suas necessidades) e, se o seu profiler disser que é um problema, veja se você pode otimizá-lo, usando um algoritmo melhor ou alterando o contêiner.

Dito isto, podemos voltar à pergunta original.

Matriz estática / dinâmica?

As classes de matriz C ++ são mais bem comportadas do que a matriz C de baixo nível, porque 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 o mais importante, eles geralmente são escritos usando modelos e / ou inlining, o que significa que o que parece muito código na depuração resolve pouco ou nenhum código produzido na criação da versão, o que significa que não há diferença com a concorrência menos segura interna.

Ao todo, ele se enquadra em duas categorias:

Matrizes dinâmicas

Usar um ponteiro para uma matriz malloc-ed / new-ed será tão rápido quanto a versão std :: vector e muito menos seguro (consulte a publicação do litb ).

Então use um std :: vector.

Matrizes estáticas

Usar 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 vectorbuffer em vez de um buffer bruto gera um custo visível, porque o vectorinicializará o buffer na construção, enquanto o código que ele substitui não, como observou Bernie em sua resposta .

Se esse for o caso, você poderá lidar com isso usando um em unique_ptrvez de a vectorou, se o caso não for excepcional em sua linha de código, escreva uma classe buffer_ownerque seja a proprietária dessa memória e ofereça acesso fácil e seguro a ela, incluindo bônus como redimensioná-lo (usando realloc?) ou o que você precisar.

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

Um lugar em que você pode encontrar um problema de desempenho é não dimensionar o vetor corretamente, para começar.

À medida que o vetor é preenchido, ele se redimensiona e isso pode implicar em uma nova alocação de matriz, seguida por n construtores de cópia, seguida por cerca de n chamadas de destruidor, seguidas por uma exclusão de matriz.

Se sua construção / destruição for cara, é muito melhor criar o vetor com o tamanho correto para começar.

Existe uma maneira simples de demonstrar isso. Crie uma classe simples que mostre quando é construída / destruída / copiada / atribuída. Crie um vetor dessas coisas e comece a pressioná-las na parte traseira do vetor. Quando o vetor for preenchido, haverá uma cascata de atividades à medida que o vetor for 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 (por exemplo, assembly) ou bibliotecas antigas que exigem matrizes, talvez você não consiga usar vetores.

Não é verdade. Os vetores degradam muito bem em matrizes / ponteiros se você usar:

vector<double> 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 que funcione (mesmo que funcione bem hoje).

Você tem ainda menos motivos para usar matrizes simples no C ++ 11.

Existem 3 tipos de matrizes na natureza, da mais rápida à mais lenta, dependendo dos recursos que elas possuem (é claro que a qualidade da implementação pode tornar as coisas muito rápidas, mesmo no caso 3 da lista):

1. Estático com tamanho conhecido em tempo de compilação. ---std::array<T, N>
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 . Talvezdynarray em C ++ TS após C ++ 14. Em C existem VLAs
3. Dinâmico e redimensionável em tempo de execução. ---std::vector<T>

Para 1. matrizes estáticas simples com número fixo de elementos, usestd::array<T, N> no C ++ 11.

Para 2. matrizes de tamanho fixo especificadas em tempo de execução, mas que não mudam de tamanho, há discussão no C ++ 14, mas ele foi movido para uma especificação técnica e, finalmente, feito do C ++ 14.

Pois 3. std::vector<T> normalmente pedirá memória na pilha . Isso pode ter consequências no desempenho, embora você possa usar std::vector<T, MyAlloc<T>>para melhorar a situação com um alocador personalizado. A vantagem em comparação T mytype[] = new MyType[n];é que você pode redimensioná-lo e não decair para um ponteiro, como fazem as matrizes simples.

Use os tipos de biblioteca padrão mencionados para evitar que as matrizes se deteriorem nos ponteiros . Você economizará tempo de depuração e o desempenho será exatamente o mesmo que com matrizes simples se você usar o mesmo conjunto de recursos.

Vá com 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 nos quais a maioria de nós não pensaria.

STL é uma biblioteca altamente otimizada. De fato, até é sugerido o uso do STL em jogos onde pode ser necessário alto desempenho. As matrizes são muito suscetíveis a erros para serem usadas nas tarefas diárias. Os compiladores de hoje também são muito inteligentes e podem realmente produzir um excelente código com o STL. Se você sabe o que está fazendo, o STL geralmente pode fornecer o desempenho necessário. Por exemplo, inicializando vetores com o tamanho necessário (se você souber desde o início), você pode basicamente atingir 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 (por exemplo, assembly) ou bibliotecas antigas que exigem matrizes, talvez você não consiga usar vetores.

Sobre a contribuição de duli .

A conclusão é que matrizes de números inteiros são mais rápidas que vetores de números inteiros (5 vezes no meu exemplo). Entretanto, matrizes e vetores apresentam a mesma velocidade para dados mais complexos / não alinhados.

Se você compilar o software no modo de depuração, muitos compiladores não incorporarão as funções de acessador do vetor. Isso tornará a implementação do vetor stl muito mais lenta nas circunstâncias em que o desempenho é um problema. Isso também facilitará a depuração do código, pois você pode ver no depurador quanta memória foi alocada.

No modo otimizado, eu esperaria que o vetor stl se aproximasse da eficiência de uma matriz. Isso ocorre porque muitos dos métodos de vetor estão agora alinhados.

Definitivamente, há um impacto no desempenho do uso de uma std::vectormatriz bruta versus uma bruta quando você deseja um buffer não inicializado (por exemplo, para usar como destino memcpy()). Um std::vectorinicializará todos os seus elementos usando o construtor padrão. Uma matriz bruta não.

A especificação c ++ para o std:vectorconstrutor que usa um countargumento (é a terceira forma) afirma:

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

3) Constrói o contêiner com as instâncias padrão de T. inseridas por padrão. Nenhuma cópia é feita.

Complexidade

2-3) Linear na contagem

Uma matriz bruta não incorre nesse custo de inicialização.

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

A diferença de desempenho entre os dois depende muito da implementação - se você comparar um std :: vector mal implementado com uma implementação de matriz ideal, a matriz venceria, mas mudaria de posição e o vetor venceria ...

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

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

Ah, e não esqueça que a matriz e o vetor compartilham o mesmo layout de memória, para que você possa usar vetores para passar dados ao código C ou C ++ herdado que espera matrizes básicas. Lembre-se de que a maioria das apostas não ocorre nesse cenário e você está lidando com a memória bruta novamente.

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

Pode haver algum caso extremo em que você tenha um acesso vetorial dentro de uma função embutida dentro de uma função embutida, onde você foi além do que o compilador incorporará e forçará uma chamada de função. Isso seria tão raro que não valeria a pena se preocupar - em geral, eu concordo com litb .

Estou surpreso que ninguém tenha mencionado isso ainda - não se preocupe com o desempenho até que se prove que é um problema, e faça uma avaliação comparativa.

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

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

O seguinte teste simples:

Matriz C ++ vs Explicação do teste de desempenho vetorial

contradiz as conclusões de "Comparação de código de assembly gerado para operações básicas de indexação, desreferenciamento e incremento em vetores e matrizes / ponteiros".

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

Às vezes, matrizes são realmente melhores que vetores. Se você está sempre manipulando um conjunto de objetos de comprimento fixo, as matrizes 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 vetorial de X é

class X {
vector<int> vec;
public:
X(const vector<int>& 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 do array será main () será mais rápida porque estamos evitando a sobrecarga de "novo" todas as vezes no loop interno.

(Esse código foi postado em comp.lang.c ++ por mim).

Se você estiver usando vetores para representar um comportamento multidimensional, há um impacto no desempenho.

Os vetores 2d + causam um impacto no desempenho?

A essência é que há uma pequena quantidade de sobrecarga com cada subvetor com informações de tamanho e não haverá necessariamente serialização de dados (como ocorre com as matrizes c multidimensionais). Essa falta de serialização pode oferecer mais do que oportunidades de micro otimização. Se você estiver fazendo arrays multidimensionais, talvez seja melhor estender o std :: vector e rolar sua própria função get / set / redimensionar bits.

Assumindo uma matriz de comprimento fixo (por exemplo , int* v = new int[1000];vs std::vector<int> v(1000);, com o tamanho de vser mantido fixo em 1000), a única consideração de desempenho que realmente importa (ou pelo menos importava para mim quando eu estava em um dilema semelhante) é a velocidade de acesso a um elemento. Procurei o código vetorial do STL e aqui está o que encontrei:

const_reference
operator[](size_type __n) const
{ return *(this->_M_impl._M_start + __n); }

Esta função certamente será incorporada pelo compilador. Portanto, desde que a única coisa que você planeja fazer vseja acessar seus elementos operator[], parece que realmente não deve haver nenhuma diferença no desempenho.