Melhorando o uso do STL Vector

Eu uso bastante o STL (Standard Template Library) do C++. Ele está disponível em diversas plataformas, é rápido e é (relativamente) fácil de aprender. As vezes, seus desenvolvedores tomam atitudes conservadoras: só recentemente o STL incluiu uma estrutura de dados de tabela hash padrão ( com C++11). No entanto, usar STL é muito mais seguro do que lidar diretamente com ponteiros.

Eu uso o template em quase todo o meu software C++. Essencialmente, você pode usá-lo sempre que precisar de uma matriz dinâmica. Neste post escrevo sobre o uso de vectors STL, porém, você deve saber usá-los corretamente, se você precisa de velocidade!

Ao usar um vector em código de alto desempenho, é preciso estar ciente de vários fatores importantes. Por exemplo, a capacidade (uso de memória) de um vector nunca vai diminuir, mesmo se você chamar o método “clear”, a menos que você use o método de “swap”. Na minha opinião, o que torna difícil para liberar memória foi uma decisão infeliz de projeto. Outro problema com o template é que sempre que você copiar um “vector”, você copia todos os dados que ele contém. Mais uma vez, a fim de evitar esse problema, você deve usar o método “swap”.

Mas um problema complicado com vectors STL é que existem muitas maneiras de construí-los. Suponha que eu queira criar uma matriz em C++ que contém os números de 0 a N em ordem crescente. Então eu quero calcular a soma destes valores. Ouvi dizer que os matemáticos possuem com uma fórmula para este problema :), mas o microprocessador Intel não sabe disso.

A abordagem convencional usada pela maioria dos programadores é de alocar memória usando o comando new do C++:


int * bigarray = new int[N];
for(unsigned int k = 0; k<N; ++k)
bigarray[k] = k;
int sum = total(bigarray,N);
delete [] bigarray;
return sum;

Ou, você pode fazer o mesmo usando STL:


vector bigarray(N);
for(unsigned int k = 0; k<N; ++k)
bigarray[k] = k;
int sum = total(bigarray,N);
return sum;

É mais cômodo usar a última abordagem, porque você não precisa se lembrar de liberar a memória alocada. Há um preço a pagar no entanto, porque quando você constrói o vector desta forma, a memória é inicializada com zero.

Você pode fazer isso usando STL puro, com o método push_back:


vector bigarray;
for(unsigned int k = 0; k<N; ++k)
bigarray.push_back(k);
int sum = total(bigarray,N);
return sum;

We can improve the push_back method by using the fact that we know ahead of time how big the array will be. Thus, we can reserve the memory before the push_backs.
Podemos melhorar o método push_back, usando o fato de que sabemos de antemão o quão grande a matriz será. Assim, podemos reservar a memória antes de chamar os push_backs.


vector bigarray;
bigarray.reserve(N);
for(unsigned int k = 0; k<N; ++k)
bigarray.push_back(k);
int sum = total(bigarray,N);
return sum;
It is likely to be slightly faster.

Então, qual é o resultado disto? No meu desktop Intel Core i7, recebo os seguintes números de ciclos de CPU por inteiro processados​​:

método usado  ciclos por inteiro processado
C++ new 8.5
STL vector 8.9
push_back 20.6
reserve + push_back 12.6

Como de costume, meu código esta gratuitamente disponível neste link

Note que você pode enganar e obter a mesma velocidade que um C + + novo, construindo o vetor vazio, reservando a memória (reserva) e nunca redimensionamento o tamanho da matriz. Isto está fora das especificações padrão e pode ser perigoso, mas poupa-lhe até a metade de um ciclo de CPU por inteiro.

Concluindo, usar vectors STL pode ser muito rápido mas se você usá-los para armazenar inteiro, o uso do método push_back pode ser reltivamente caro.

Artigo original: http://lemire.me/blog/archives/2012/06/20/do-not-waste-time-with-stl-vectors/

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s