Iteração linha-coluna x coluna-linha

[rhcarvalho]

Olá,

Não estou conseguindo fazer comentário direto na linha do arquivo no commit por conta de algum problema no GitHub (recebo mensagens de que o servidor está em manutenção).

Do pouco que aprendi de FORTRAN lembro de uma coisa marcante que é o fato da alocação de memória de arrays ser feita por coluna, diferente de C em que a alocação é feita por linha.

Isto implica que em C você "quer sempre" escrever algo do tipo:

for (int i = 0; i <= linhas; i++) {
  for (int j = 0; j <= colunas; j++) {
    ...
  }
}

Mas em FORTRAN deveria escrever:

do 1, colunas
  do 1, linhas
    ...
  end do
end do

Não sei se é o caso no arquivo matriz.f90 por não ter entendido ainda muito bem o código e a intenção. Minha consideração se aplica aqui?

O porquê da diferença grotesca de desempenho entre fazer linha-coluna x coluna-linha pode ser entendida pelo conceito de "locality of reference".

Uma referência mais educativa é este post que explica em mais detalhes o que eu citei.

Peço desculpas se fiz barulho desnecessariamente.

[crysttian]

Olá Rodolfo,

Concordo com você com relação a otimização do algoritmo.

Agora eu fiquei com uma dúvida e você pode me ajudar. Eu faço a compactação dos dados por colunas. Suponha que uma matriz M com n colunas e m linhas, após aplicar o algoritmo, ela passa a ter n' colunas e m linhas. Como n' < n, ocorre a compactação dos dados na memória com a redução do número de colunas. Após a compactação, a matriz M será manipulada com diferentes operações, então da forma que ela está representada, torna-se possível acessar uma maior quantidade de informações por linha, uma vez que cada elemento da matriz, existem várias colunas compactadas em uma. Concorda com isso?

Qualquer coisa, passe aqui na sala que podemos discutir. Colaborações são sempre bem vindas.

Até

[rhcarvalho]

Oi :)

Vamos ver se eu entendi. Hipoteticamente temos:

M = [[1,  2,  3],
     [4,  5,  6],
     [7,  8,  9],
     [10, 11, 12]]

Depois de compactar temos:

M' = [[2.5, 3.5, 4.5],
      [8.5, 9.5, 10.5]]

Dado que a matriz M' está armazenada de tal forma que as colunas ocupam endereços de memória próximos, e a matriz M' não cabe por completo em memória, então o fato de dim(M') < dim(M) implica em podermos ter mais linhas em memória (cada linha contém uma coluna completa).

Se uma coluna completa couber em memória, é "barato" fazer operações que operem em colunas, e "caro" fazer operações em linhas.

Exemplo: é barato calcular a soma dos elementos de uma coluna, mas caro calcular a soma de uma linha.

Se uma coluna completa não cabe em memória, qualquer operação que opere em linhas ou colunas vai precisar ir no disco (lento).

[crysttian]

Inicialmente temos:

M = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]

depois de compactada, a matriz será representad por

M = [ X1, X2, X3, X4]

de tal forma que X1, quando analisado de forma binária, está representando 1, 2 e 3.

Até

[rhcarvalho]

Isto quer dizer que M' é na verdade um vetor? Um vetor onde cada elemento representa uma linha da M original?

Se for isso, eu proponho transpor a matriz M de tal forma que cada elemento de M' represente colunas de M, pois assim a etapa de compactação será mais eficiente (pelo princípio de localidade dos dados).

Feito isto, M', um vetor, vai te permitir iterar em cada elemento sequencialmente -- o que equivale mais uma vez a operar nas colunas de M (depois da descompactação).

[crysttian]

Rodolfo,

Pode vir a ser um vetor, mas na maioria dos casos não é. Na maioria das vezes o resultado é uma outra matriz.

Até

[rhcarvalho]

Neste caso, reforço só a ideia geral do meu comentário inicial:

Em FORTRAN, quando estiver trabalhando com matrizes (arrays multi-dimensionais), escreva seu loop interno operando nas colunas, pois estas estão alocadas em endereços contíguos de memória.

[crysttian]

Sim, será isso que vou fazer.

Valeu