Ferramentas para analisar o desempenho de um programa Haskell

Enquanto resolvia alguns problemas do Projeto Euler para aprender Haskell (atualmente, sou totalmente iniciante), resolvi o Problema 12 . Eu escrevi esta solução (ingênua):

--Get Number of Divisors of n
numDivs :: Integer -> Integer
numDivs n = toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2

--Generate a List of Triangular Values
triaList :: [Integer]
triaList =  [foldr (+) 0 [1..n] | n <- [1..]]

--The same recursive
triaList2 = go 0 1
  where go cs n = (cs+n):go (cs+n) (n+1)

--Finds the first triangular Value with more than n Divisors
sol :: Integer -> Integer
sol n = head $ filter (\x -> numDivs(x)>n) triaList2

Esta solução para n=500 (sol 500)é extremamente lenta (rodando há mais de 2 horas), então me perguntei como descobrir por que essa solução é tão lenta. Existe algum comando que me diga onde a maior parte do tempo de computação é gasto para que eu saiba qual parte do meu programa haskell está lenta? Algo como um simples profiler.

Para deixar claro, eu não estou pedindo para uma solução mais rápida, mas para uma maneira de encontrar essa solução. Como você começaria se não tivesse nenhum conhecimento sobre haskell?

Tentei escrever duas triaListfunções, mas não encontrei como testar qual delas é mais rápida, então é aqui que meus problemas começam.

obrigado

como descobrir por que essa solução é tão lenta. Há algum comando que me diga onde é gasto a maior parte do tempo de computação, para que eu saiba qual parte do meu programa haskell está lenta?

Precisamente! GHC oferece muitas ferramentas excelentes, incluindo:

• estatísticas de tempo de execução
• perfil de tempo
• perfil de heap
• análise de fio
• análise de núcleo.
• benchmarking comparativo
• Afinação GC

Um tutorial sobre o uso de perfis de tempo e espaço faz parte do Real World Haskell .

Estatísticas GC

Em primeiro lugar, certifique-se de que está compilando com ghc -O2. E você pode ter certeza de que é um GHC moderno (por exemplo, GHC 6.12.x)

A primeira coisa que podemos fazer é verificar se a coleta de lixo não é o problema. Execute seu programa com + RTS -s

$ time ./A +RTS -s
./A +RTS -s 
749700
   9,961,432,992 bytes allocated in the heap
       2,463,072 bytes copied during GC
          29,200 bytes maximum residency (1 sample(s))
         187,336 bytes maximum slop
               **2 MB** total memory in use (0 MB lost due to fragmentation)

  Generation 0: 19002 collections,     0 parallel,  0.11s,  0.15s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   13.15s  ( 13.32s elapsed)
  GC    time    0.11s  (  0.15s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   13.26s  ( 13.47s elapsed)

  %GC time       **0.8%**  (1.1% elapsed)

  Alloc rate    757,764,753 bytes per MUT second

  Productivity  99.2% of total user, 97.6% of total elapsed

./A +RTS -s  13.26s user 0.05s system 98% cpu 13.479 total

O que já nos dá muitas informações: você tem apenas um heap de 2M e o GC ocupa 0,8% do tempo. Portanto, não precisa se preocupar com a alocação de problemas.

Perfis de tempo

Obter um perfil de tempo para o seu programa é simples: compilar com -prof -auto-all

 $ ghc -O2 --make A.hs -prof -auto-all
 [1 of 1] Compiling Main             ( A.hs, A.o )
 Linking A ...

E, para N = 200:

$ time ./A +RTS -p                   
749700
./A +RTS -p  13.23s user 0.06s system 98% cpu 13.547 total

que cria um arquivo, A.prof, contendo:

    Sun Jul 18 10:08 2010 Time and Allocation Profiling Report  (Final)

       A +RTS -p -RTS

    total time  =     13.18 secs   (659 ticks @ 20 ms)
    total alloc = 4,904,116,696 bytes  (excludes profiling overheads)

COST CENTRE          MODULE         %time %alloc

numDivs            Main         100.0  100.0

Indica que todo o seu tempo é gasto em numDivs, e também é a fonte de todas as suas alocações.

Perfis Heap

Você também pode obter uma divisão dessas alocações, executando com + RTS -p -hy, que cria A.hp, que você pode visualizar convertendo-o em um arquivo postscript (hp2ps -c A.hp), gerando:

o que nos diz que não há nada de errado com seu uso de memória: ele está alocando em espaço constante.

Portanto, seu problema é a complexidade algorítmica de numDivs:

toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2

Conserte isso, que é 100% do seu tempo de execução e tudo o mais será fácil.

Otimizações

Esta expressão é uma boa candidata para a otimização de fusão de fluxo , então vou reescrevê-la para usar Data.Vector , assim:

numDivs n = fromIntegral $
    2 + (U.length $
        U.filter (\x -> fromIntegral n `rem` x == 0) $
        (U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int))

Que deve se fundir em um único loop sem alocações de heap desnecessárias. Ou seja, terá maior complexidade (por fatores constantes) do que a versão em lista. Você pode usar a ferramenta ghc-core (para usuários avançados) para inspecionar o código intermediário após a otimização.

Testando isso, ghc -O2 --make Z.hs

$ time ./Z     
749700
./Z  3.73s user 0.01s system 99% cpu 3.753 total

Portanto, ele reduziu o tempo de execução para N = 150 em 3,5x, sem alterar o próprio algoritmo.

Conclusão

Seu problema é numDivs. É 100% do seu tempo de execução e tem uma complexidade terrível. Pense em numDivs e como, por exemplo, para cada N você está gerando [2 .. n div2 + 1] N vezes. Tente memorizar isso, já que os valores não mudam.

Para medir qual de suas funções é mais rápida, considere usar o critério , que fornecerá informações estatisticamente robustas sobre melhorias de sub-microssegundos no tempo de execução.

Addenda

Já que numDivs é 100% do seu tempo de execução, tocar em outras partes do programa não fará muita diferença, no entanto, para fins pedagógicos, também podemos reescrever aqueles usando fusão de fluxo.

Também podemos reescrever trialList e confiar na fusão para transformá-lo no loop que você escreve à mão em trialList2, que é uma função de "varredura de prefixo" (também conhecida como scanl):

triaList = U.scanl (+) 0 (U.enumFrom 1 top)
    where
       top = 10^6

Da mesma forma para sol:

sol :: Int -> Int
sol n = U.head $ U.filter (\x -> numDivs x > n) triaList

Com o mesmo tempo de execução geral, mas um código um pouco mais limpo.

A resposta de Dons é ótima, sem ser um spoiler, dando uma solução direta para o problema.
Aqui, quero sugerir uma pequena ferramenta que escrevi recentemente. Ele economiza tempo para escrever anotações SCC à mão quando você deseja um perfil mais detalhado do que o padrãoghc -prof -auto-all . Além disso é colorido!

Aqui está um exemplo com o código que você forneceu (*), verde é bom, vermelho é lento:

O tempo todo vai criando a lista de divisores. Isso sugere algumas coisas que você pode fazer:
1. Tornar a filtragem n rem x == 0mais rápida, mas como é uma função embutida provavelmente já é rápida.
2. Crie uma lista mais curta. Você já fez algo nessa direção verificando apenas até n quot 2.
3. Jogue fora a geração da lista completamente e use um pouco de matemática para obter uma solução mais rápida. Esta é a maneira usual para problemas de projeto Euler.

(*) Consegui colocar seu código em um arquivo chamado eu13.hs, adicionando uma função principal main = print $ sol 90. Em seguida, executando visual-prof -px eu13.hs eu13e o resultado está em eu13.hs.html.

Nota relacionada a Haskell: triaList2é claro que é mais rápido triaListporque o último executa muitos cálculos desnecessários. Levará tempo quadrático para calcular n primeiros elementos de triaList, mas linear para triaList2. Existe outra maneira elegante (e eficiente) de definir uma lista preguiçosa infinita de números de triângulo:

triaList = 1 : zipWith (+) triaList [2..]

Nota relacionada à matemática: não há necessidade de verificar todos os divisores até n / 2, basta verificar até sqrt (n).

Você pode executar seu programa com sinalizadores para habilitar o perfil de tempo. Algo assim:

./program +RTS -P -sprogram.stats -RTS

Isso deve rodar o programa e gerar um arquivo chamado program.stats que terá quanto tempo foi gasto em cada função. Você pode encontrar mais informações sobre criação de perfis com GHC no guia do usuário do GHC . Para benchmarking, existe a biblioteca Criterion. Descobri que esta postagem do blog tem uma introdução útil.