Problemas com performance do código

[Leandro]

Estou trabalhando com FDTD (simulação eletromagnética) e infelizmente estou com alguns problemas de performance no código.

Temos duas versões. A primeira executa apenas a cálculo (versão1). A segunda versão é a aplicação inteira (GUI implementada com a wxWidgets), com a mesma rotina de cálculo (versão2). O problema é que a versão2 é quase duas vezes mais lenta que a versão1 e eu não consigo entender o porquê.

O cálculo do FDTD é um conjunto de loops (um no tempo e três no espaço). Então para facilitar eu removi todos os loops e deixei apenas 1. Em seguida, executei o "Very Sleepy" para ver o profile. De acordo com os resultados, o mesmo código roda com duas velocidades diferentes, como pode ser visto abaixo (as variáveis com colchetes são do tipo TNT::Array3D - http://math.nist.gov/tnt/overview.html)

Versão1:

0.15s void FdtdSolver::CalculateDx()

{

    int i, j, k;

double curl_h;

// Calculate the Dx field

for(i = 1; i < ia; i++)

{

0.01s for(j = 1; j < Ny; j++)

{

0.06s for(k = 1; k < Nz; k++)

{

curl_h = cay[j]*(Hz[i][j][k] - Hz[i][j-1][k]) -

0.38s caz[k]*(Hy[i][j][k] - Hy[i][j][k-1]);

0.10s idxl[i][j][k] = idxl[i][j][k] + curl_h;

Dx[i][j][k] = gj3[j]*gk3[k]*Dx[i][j][k] +

0.29s  gj2[j]*gk2[k]*(curl_h + gi1[i]*idxl[i][j][k]);

}

}

}

// Other loops with the same behavior...

}

Versão2:

0.01s void FDTDEngine::CalculateDx()

{

    int i, j, k;

double curl_h;

// Calculate the Dx field

for(i = 1; i < ia; i++)

{

0.00s for(j = 1; j < Ny; j++)

{

0.06s for(k = 1; k < Nz; k++)

{

0.01s curl_h = cay[j]*(Hz[i][j][k] - Hz[i][j-1][k]) -

0.53s caz[k]*(Hy[i][j][k] - Hy[i][j][k-1]);

0.10s idxl[i][j][k] = idxl[i][j][k] + curl_h;

0.02s Dx[i][j][k] = gj3[j]*gk3[k]*Dx[i][j][k] +

0.36s  gj2[j]*gk2[k]*(curl_h + gi1[i]*idxl[i][j][k]);

}

}

}

// Other loops with the same behavior...

}

A questão é: Que tipo de ferramentas (gratuitas, por favor) eu posso usar para tentar ir a mais a fundo nesse problema e descobrir o porquê dessa diferença e como arrumá-la? Alguma dica de como achar o erro?

Obrigado!

[Gianni]

Valgrind[0] (+ KCachegrind[1])

...e pesquise por cache-miss[2].

O que pode estar acontecendo, e isso é só um chute, é que com o GUI, suas
estruturas cresceram e não cabem mais no cache da CPU. Tente 'aproximar'
todas as variáveis usadas nos loops.


[0] http://valgrind.org/
[1] http://kcachegrind.sourceforge.net/html/Screenshots.html
[2] https://en.wikipedia.org/wiki/Cache_miss

[Leandro]

Obrigado pela resposta. Pesquisarei sobre o assunto.

Quanto às ferramentas, o sistema foi construído para executar no Windows, e a página do Valgrind e do KCachegrind dizem que são para Linux. Tem alguma sugestão de ferramentas para Windows? Desculpe a pergunta, mas sou meio novo nesse tipo de problema...

Obrigado.

[Rodrigo Madera]

Minha recomendação seria usar um Profiler e saber exatamente a causa da lentidão, sem precisar ficar adivinhando. 

Google C++ Profiler

Mx

--
--
Antes de enviar um e-mail para o grupo leia:
http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
--~--~---------~--~----~---------------------------------~----------~--~----~
[&] Colabore com a Pesquisa de Preferência de Conteúdo
para Eventos do Grupo C & C++ Brasil:
http://www.surveymonkey.com/s/GBBGTXN
------~----~-------~---~---~---~---~----------------~------------~---------~
[&] C & C++ Brasil - http://www.ccppbrasil.org/
Para sair dessa lista, envie um e-mail para ccppbrasil-...@googlegroups.com
Para mais opções, visite http://groups.google.com/group/ccppbrasil
--~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
Emprego & carreira: vag...@ccppbrasil.org
http://groups.google.com/group/dev-guys?hl=en
 
---
Você está recebendo esta mensagem porque se inscreveu no grupo "ccppbrasil" dos Grupos do Google.
Para cancelar a inscrição neste grupo e parar de receber seus e-mails, envie um e-mail para ccppbrasil+...@googlegroups.com.
Para obter mais opções, acesse https://groups.google.com/groups/opt_out.
 
 

[Josue Andrade Gomes]

Verifique se as duas versões estão sendo compiladas com as mesmas opções de otimização do compilador. A propósito qual compilador vc está usando?

--

[Leandro]

Já havia feito isso, como  Very Sleepy. Tentarei também com sua indicação, ver se consigo encontrar o problema. 

Grato.

[Leandro]

g++, com as mesmas opções de otimização -O3

[Rodrigo 'Skhaz' Delduca]

+1 Profiler. Isto[1] também pode te ajudar

1 - http://www.akkadia.org/drepper/cpumemory.pdf

[Marcelo Zimbres]

Bom dia Leandro, 

acredito que o problema não esteja na função de cálculo, já que ela funciona corretamente quando a parte gráfica não é usada. Você está chamando a função com os mesmos parâmetros? Está visualisando dados enquanto faz as contas? Essa é uma função bem custosa computacionalmente, gastar um tempo otimizado vai te economizar um bom tempo de simulação. Uma coisa que me ajudou muito com um algoritmo de complexidade O(n^4) parecido foi usar aritmética de ponteiros. Por exemplo em vez de:

for (loop em k){

a = b[i][j][k] ;

...

}

use

int* p = &b[i][j][0]; // ou b[i][j];

for (loop em k) {

a = *p

...

++p;

}

As funções que forem chamadas nos loops mais internos são preferencialmente inline normalmente, um profiler também vai te ajudar melhor a identificar os pontos onde podem haver melhorias.

Marcelo

[P.]

Em segunda-feira, 25 de fevereiro de 2013 07h42min39s UTC-3, Leandro escreveu:

 

A questão é: Que tipo de ferramentas (gratuitas, por favor) eu posso usar para tentar ir a mais a fundo nesse problema e descobrir o porquê dessa diferença e como arrumá-la? Alguma dica de como achar o erro?

Gratuitas para Windows será difícil. O Intel VTune tem um trial longo o suficiente, creio eu.

Uma possibilidade para você experimentar: tornar esta função "pura", recebendo os dados como argumentos e retornando o resultado. Se as cópias forem rápidas o suficiente, o compilador pode economizar certos loads e stores intermediários que não serão vistos por ninguém (já que os dados são locais).

--
 P.

[Rodrigo Avancini]

Da forma que esta seu código não da pra tirar alguma conclusão da causa da lentidão, parece que a complexidade O(n^3) e as matrizes são de três dimensões, mas não existe condições de parada, sentinelas, pivores, logicamente vai ser lento.. Muito vago para alguma opinião.. Uma sugestão é tentar calcular isso na placa de vídeo, falando nisso, o hardware também é um parâmetro importante pra esse tipo de teste..

Att.

Rodrigo

--

[Fernando Tonon]

Nesse código com GUI você está imprimindo alguma informação de dentro
desses loops? operações de I/O são lentas (O artigo [1] postado pelo
Skhaz explica bem isso), se for imprimir algum dado, mesmo com printf
é melhor fazer isso fora do loop...

1 - http://www.akkadia.org/drepper/cpumemory.pdf

On 25 fev, 06:42, Leandro <cari...@gmail.com> wrote:
> Estou trabalhando com FDTD (simulação eletromagnética) e infelizmente estou
> com alguns problemas de performance no código.
>
> Temos duas versões. A primeira executa apenas a cálculo (versão1). A
> segunda versão é a aplicação inteira (GUI implementada com a wxWidgets),
> com a mesma rotina de cálculo (versão2). O problema é que a versão2 é quase
> duas vezes mais lenta que a versão1 e eu não consigo entender o porquê.
>
> O cálculo do FDTD é um conjunto de loops (um no tempo e três no espaço).
> Então para facilitar eu removi todos os loops e deixei apenas 1. Em
> seguida, executei o "Very Sleepy" para ver o profile. De acordo com os
> resultados, o mesmo código roda com duas velocidades diferentes, como pode

> ser visto abaixo (as variáveis com colchetes são do tipo TNT::Array3D -http://math.nist.gov/tnt/overview.html)

[Rodrigo Madera]

Cuidado ao escrever "printf" e "debug" na mesma frase.

http://www.drdobbs.com/architecture-and-design/embedded-print-statements-debugging/240148855#

Mx

2013/2/25 Fernando Tonon <mistic...@gmail.com>

[Fernando Tonon]

Ótimo artigo, mas me senti mal lendo ele heuahuehehueueaheauhuae

Velhos hábitos são difíceis de eliminar... as vezes ainda uso o print
statement quando a versão debug está muito desatualizada e o tempo de
compilação não vai compensar o tempo perdido com o print, mas
geralmente é muito melhor usar o debug mesmo...

Mais um tópico fugindo do assunto... :)

On 25 fev, 17:13, Rodrigo Madera <rodrigo.mad...@gmail.com> wrote:
> Cuidado ao escrever "printf" e "debug" na mesma frase.
>

> http://www.drdobbs.com/architecture-and-design/embedded-print-stateme...
>
> Mx
>
> 2013/2/25 Fernando Tonon <misticgor...@gmail.com>

>
>
>
>
>
>
>
> > Nesse código com GUI você está imprimindo alguma informação de dentro
> > desses loops? operações de I/O são lentas (O artigo [1] postado pelo
> > Skhaz explica bem isso), se for imprimir algum dado, mesmo com printf
> > é melhor fazer isso fora do loop...
>

> > 1 -http://www.akkadia.org/drepper/cpumemory.pdf

> > [&] C & C++ Brasil -http://www.ccppbrasil.org/

> > Para sair dessa lista, envie um e-mail para
> > ccppbrasil-...@googlegroups.com

> > Para mais opções, visitehttp://groups.google.com/group/ccppbrasil
> > --~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
> > Emprego & carreira:  vaga...@ccppbrasil.org

[P.]

Em segunda-feira, 25 de fevereiro de 2013 17h31min05s UTC-3, Rodrigo Avancini escreveu:

Da forma que esta seu código não da pra tirar alguma conclusão da causa da lentidão, parece que a complexidade O(n^3) e as matrizes são de três dimensões, mas não existe condições de parada, sentinelas, pivores, logicamente vai ser lento.. Muito vago para alguma opinião.. Uma sugestão é tentar calcular isso na placa de vídeo, falando nisso, o hardware também é um parâmetro importante pra esse tipo de teste..

A mensagem original do Leandro inclui os resultados do profiler na coluna da esquerda, linha por linha, mas parece que ninguém viu isso.

O texto das duas funções comparadas são rigorosamente iguais, segundo o meu olhômetro.
Portanto, complexidade não pode ser o segredo do problema, já que ambas as rotinas comparadas com certeza tem a mesma complexidade.

Assumindo que o Leandro não nos está sacaneando e executou todas as vezes com o mesmo working set, somos levados a suspeitar de coisas como cache misses devido a má localidade no programa com GUI, como o Gianni sugeriu.

--
 P.

[Rodrigo Madera]

Deu pra ver os números do algoritmo, sim. Mas não do GUI, obviamente.

Mx

2013/2/25 P. <pedro....@gmail.com>

--

[Leandro]

Bom, ontem fiz mais alguns testes e ainda não consegui concluir muita coisa. Como é complicado (ou impossível) advinhar o problema, eu peguei minha classe e limpei até deixar apenas a rotina de cálculo para enviar para o grupo. O resultado foi que as duas rodaram praticamente no mesmo tempo.

P., não estou sacaneando. As duas foram executadas no mesmo computador, compiladas com as mesmas flags. A diferença principal é que uma tem a GUI e a outra não. Talvez o problema seja mesmo algo relacionado à memória, pelo menos é o que mais faz sentido até agora. Comecei a ler o artigo enviado pelo Skhaz, pelo menos para entender o que pode estar acontecendo.

Durante a semana tentarei outras alternativas que foram sugeridas aqui e em outros grupos. Se conseguir resolver o problema, atualizo aqui.

Obrigado a todos.

[Gianni]

Ve tentou isolar as vars usadas pelo cálculo em uma classe ou struct separada
do resto do GUI? Só fazer isso pode resolver o problema....

[Leandro]

Comecei a fazer isso ontem e continuarei hoje a noite. Postarei os resultados.

Obrigado

[Felipe Magno de Almeida]

2013/2/26 Leandro <car...@gmail.com>:

> Comecei a fazer isso ontem e continuarei hoje a noite. Postarei os
> resultados.

O aqtime é um ótimo profiler. E tem um tempo de evaluation, não é livre porém
e seu preço é bem salgadinho. Mas pode valer a pena testar o evaluation. Eu
acho que seria interessante você fazer o profiling dos dois códigos para ver
no que diferem. Mas com mais estátisticas que apenas o tempo de execução.
Como context switches, cache misses, essas coisas todas.

> Obrigado

[]'s
--
Felipe Magno de Almeida

[P.]

Em terça-feira, 26 de fevereiro de 2013 07h16min34s UTC-3, Gianni escreveu:

 

Ve tentou isolar as vars usadas pelo cálculo em uma classe ou struct separada
do resto do GUI?  Só fazer isso pode resolver o problema....

Hackeando a Cairo eu vi uns números incríveis apenas movendo a declaração de certas variáveis para o loop mais interno possível. Como por exemplo, numa varredura 2D qualquer:

int lineColumn = 0; /* remove este *~/

for (int x = 0; x < xMax; ++x)
{
  for (int y = 0; y < yMax; ++y)
  {
    lineColumn = area[x][y]; /* declarar aqui */
    area[x][y] = transform(lineColumn); /* isso era bem mais complexo */
  }
}

Não analisei o assembler gerado porque nessa época eu estava investigando OpenMP. Mas eu verifiquei e o ganho nessa transformação acontecia mesmo sem OpenMP. Acho que aqui ocorreu mais que apenas a localidade dos dados; provavelmente o GCC novíssimo que eu usei conseguiu desenrolar melhor o loop ou vetorizar alguma operação. Minha intuição geral é de que a variável local permite ao compilador provar que o valor não será observado fora de um minúsculo trecho do programa.

--
 P.

[Rodrigo 'Skhaz' Delduca]

P.
Está técnica é mencionada no link que postei acima, e completa o que o
Gianni disse. E sim, faz muita muita diferença

2013/2/26 P. <pedro....@gmail.com>:

> --
> --
> Antes de enviar um e-mail para o grupo leia:
> http://www.ccppbrasil.org/wiki/Lista:AntesdePerguntar
> --~--~---------~--~----~---------------------------------~----------~--~----~
> [&] Colabore com a Pesquisa de Preferência de Conteúdo
> para Eventos do Grupo C & C++ Brasil:
> http://www.surveymonkey.com/s/GBBGTXN
> ------~----~-------~---~---~---~---~----------------~------------~---------~
> [&] C & C++ Brasil - http://www.ccppbrasil.org/
> Para sair dessa lista, envie um e-mail para
> ccppbrasil-...@googlegroups.com
> Para mais opções, visite http://groups.google.com/group/ccppbrasil
> --~--~---------~--~----~--~-~--~---~----~-----------------~--~----------~
> Emprego & carreira: vag...@ccppbrasil.org
> http://groups.google.com/group/dev-guys?hl=en
>
> ---
> Você está recebendo esta mensagem porque se inscreveu no grupo "ccppbrasil"
> dos Grupos do Google.
> Para cancelar a inscrição neste grupo e parar de receber seus e-mails, envie
> um e-mail para ccppbrasil+...@googlegroups.com.
> Para obter mais opções, acesse https://groups.google.com/groups/opt_out.
>
>

--
http://nullonerror.org/

[Virgilio Fornazin]

Que por sinal, é sempre uma boa prática. Tudo que tem o escopo mais reduzido tem maiores chances de ser candidatos a otimização em compilação ou em runtime pelo processador (cache)

2013/2/26 P. <pedro....@gmail.com>

--

[Leandro]

Bom, dando um retorno sobre o caso....

Tirei toda a parte de cálculo e joguei numa struct separada, conforme sugerido. Mesma coisa, resolveu nada.

Mas então notei que estava comparando as versões debug do programa com interface e do programa versão console (só cálculo), compilando com -g3. Depois que gerei uma versão release, as coisas melhoraram um pouco. O tempo de execução da versão console não foi alterado, mas da versão gui reduziu consideravelmente. Agora GUI está menos de 50% mais lento que o console. Comi mosca (ou bola, dependendo da UF) total.

Agora vou pegar algumas sugestões de vocês e começar a otimizar o código, ver se consigo melhorar isso. Alterar algumas manipulações no loop e ver o que dá. Depois, quem sabe, tentar junto com a OpenMP.

Bom, era isso. Obrigado a todos pela ajuda!

[Gianni]

Último palpite meu vai... copia a struct e/ou os valores no stack antes dos
loops e copia o resultado depois de volta p/ a struct.