Optimizar C ++ matrizes de 2-D

Question

I necessário uma forma de representar uma matriz 2-D (uma matriz densa) da dobra em C ++, com um mínimo absoluto aceder sobrecarga.

Já fiz algumas tempo em várias máquinas Linux / Unix e versões gcc. Um vetor de STL de vetores, declarado como:

vector<vector<double> > matrix(n,vector<double>(n));

e acedido através matrix[i][j] é entre 5% e 100% mais lenta para o acesso de uma matriz declarada como:

double *matrix = new double[n*n];

acedido através de uma função de indexação matrix[index(i,j)] inline, onde avalia index(i,j) a i + n * j. Outras maneiras de organizar uma matriz 2-D sem STL - um array de n ponteiros para o início de cada linha, ou definindo a coisa toda na pilha como um matrix[n][n] tamanho constante - executados em quase exatamente a mesma velocidade que o método da função de índice .

versões recentes do gcc (> 4.0) parece ser capaz de compilar o STL vector-de-vetores para quase a mesma eficiência que o código não-STL quando otimizações estão ligados, mas isso é um pouco dependente da máquina.

Eu gostaria de usar STL, se possível, mas terá que escolher a solução mais rápida. Alguém tem alguma experiência em otimização de STL com GCC?

Answer 1

Se você estiver usando o compilador GCC pode analisar seus acessos de matriz e alterar a ordem na memória em certos casos. A bandeira compilador mágica é definido como:

-fipa-matrix-reorg

Executar matriz de achatamento e transposição. Matrix achatamento tentativas para substituir uma matriz de m-dimensional com a sua matriz equivalente de n-dimensional, onde n

Note que esta opção não é habilitada por -O2 ou O3. Você tem que passá-lo a si mesmo.

Answer 2

Meu palpite seria o mais rápido é, para uma matriz, para usar variedade STL 1D e substituir o operador () para usá-lo como matriz 2D.

No entanto, o STL também define um tipo especificamente para matrizes numéricas não-resizeable: valarray. Você também tem várias otimizações para as operações no local.

valarray aceitar como argumento um tipo numérico:

valarray<double> a;

Em seguida, você pode usar fatias, matrizes indiretos, ... e, claro, você pode herdar a valarray e definir seu próprio operador () (int i, j int) para arrays 2D ...

Answer 3

É muito provável que esta é uma questão localidade-de-referência. utilizações vector new alocar sua matriz interna, de modo que cada fila será pelo menos um pouco para além da memória devido ao cabeçalho de cada bloco; poderia ser uma longa distância apart se a memória já está fragmentado quando alocá-los. Diferentes linhas da matriz é provável que pelo menos incorrer em uma falha da linha de cache e poderia incorrer em uma falha de página; se você estiver realmente azarados duas linhas adjacentes poderia ser em linhas de memória que compartilham um slot TLB e acessando um vai expulsar o outro.

Em contraste suas outras soluções garantem que todos os dados é adjacente. Poderia ajudar o seu desempenho se você alinhar a estrutura para que ele atravessa o menor número de linhas de cache quanto possível.

vector é projetado para redimensionável arrays. Se você não precisa redimensionar as matrizes, use uma matriz regular C ++. operações STL em geral pode operar em matrizes C ++.

Do não deixe de caminhada da matriz na direção correta, ou seja, através de (endereços de memória consecutivos) em vez de para baixo. Isto irá reduzir falhas de cache.

Answer 4

A minha recomendação seria usar Boost.UBLAS, que oferece aulas de matriz rápido / vetor.

Answer 5

Para ser justo depende dos algoritmos que você está usando em cima da matriz.

O nome duplo [n * m] formato é muito rápido quando você está acessando dados por linhas tanto porque não tem quase nenhuma sobrecarga além de uma multiplicação e adição e porque suas linhas são embalados dados que vai ser coerente em cache.

Se a sua coluna de acesso algoritmos de dados ordenados em seguida, outros layouts pode ter muito melhor cache de coerência. Se os seus dados de acesso algoritmo em quadrantes da matriz, mesmo outros layouts pode ser melhor.

Tente fazer alguma pesquisa dirigida ao tipo de uso e algoritmos que você está usando. Isso é especialmente importante se a matriz é muito grande, já que erros de cache pode ferir o seu caminho desempenho mais do que a necessidade 1 ou 2 operações matemáticas extras para acessar cada endereço.

Answer 6

Você poderia facilmente fazer vector (n * m);

Answer 7

Você pode querer olhar para o Eigen C ++ biblioteca de modelos em http://eigen.tuxfamily.org/. Ele gera AltiVec ou código SSE2 para optimizar os cálculos vetor / matriz.

Answer 8

Não é a implementação uBLAS em Boost. É olhar um valor.

http: //www.boost .org / doc / libs / 1_36_0 / libs / numérica / ublas / doc / matrix.htm

Answer 9

Outra biblioteca relacionado é Blitz ++: http://www.oonumerics.org/blitz /docs/blitz.html

Blitz ++ está concebido para a manipulação de matriz optimize.

Answer 10

Eu tenho feito isso de volta algum tempo para imagens RAW, declarando meus próprios 2 classes de matriz dimensional.

Em uma matriz 2D normal, você acessar os elementos como:

matriz [2] [3]. Agora, para obter esse efeito, você teria uma matriz classe com um sobrecarregada [] Assessor matriz. Mas, isso seria, essencialmente, voltar outra matriz, dando assim -lhe a segunda dimensão.

O problema com esta abordagem é que ele tem uma chamada de função dupla sobrecarga.

A maneira que eu fiz foi usar o) sobrecarga de estilo (.

Então, ao invés de matriz [2] [3], alterar I a fazer esta matriz de estilo (2,3).

Essa função () era muito pequeno e tenho a certeza que foi embutido.

Veja este link para o conceito geral de que: http://www.learncpp.com/cpp-tutorial / 99-sobrecarregando-a-parêntese-operador /

Você pode modelo o tipo se você precisa.
A diferença que eu tinha era que minha matriz era dinâmico. Eu tinha um bloco de memória de char eu declarar. E eu empregava um cache de coluna, então eu sabia que na minha seqüência de bytes a próxima linha começou. O acesso foi otimizado para acessar valores vizinhos, porque eu estava usando-o para processamento de imagem.

É difícil de explicar sem o código, mas, essencialmente, o resultado foi o mais rápido que C, e muito mais fácil de entender e usar.