Outils d'analyse des performances d'un programme Haskell

En résolvant certains problèmes du projet Euler pour apprendre Haskell (je suis donc actuellement complètement débutant), je suis tombé sur le problème 12 . J'ai écrit cette solution (naïve):

--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

Cette solution pour n=500 (sol 500)est extrêmement lente (fonctionne depuis plus de 2 heures maintenant), je me suis donc demandé comment savoir pourquoi cette solution était si lente. Y a-t-il des commandes qui me disent où la plupart du temps de calcul est passé afin que je sache quelle partie de mon programme haskell est lente? Quelque chose comme un simple profileur.

Pour qu'il soit clair, je ne demande pas à une solution plus rapide , mais pour un moyen de trouver cette solution. Comment commencerais-tu si tu n'avais aucune connaissance de haskell?

J'ai essayé d'écrire deux triaListfonctions mais je n'ai trouvé aucun moyen de tester laquelle est la plus rapide, c'est donc là que mes problèmes commencent.

Merci

comment découvrir pourquoi cette solution est si lente. Y a-t-il des commandes qui me disent où la plupart du temps de calcul est passé afin que je sache quelle partie de mon programme haskell est lente?

Précisément! GHC fournit de nombreux excellents outils, notamment:

• statistiques d'exécution
• profilage temporel
• profilage de tas
• analyse de fil
• analyse de base.
• benchmarking comparatif
• Réglage GC

Un tutoriel sur l'utilisation du profilage temporel et spatial fait partie de Real World Haskell .

Statistiques GC

Tout d'abord, assurez-vous que vous compilez avec ghc -O2. Et vous pouvez vous assurer qu'il s'agit d'un GHC moderne (par exemple, GHC 6.12.x)

La première chose que nous pouvons faire est de vérifier que le garbage collection n'est pas le problème. Exécutez votre programme avec + 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

Ce qui nous donne déjà beaucoup d'informations: vous n'avez qu'un tas de 2M, et GC prend 0,8% du temps. Donc pas besoin de s'inquiéter que la répartition soit le problème.

Profils horaires

Obtenir un profil horaire pour votre programme est simple: compilez avec -prof -auto-all

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

Et, pour N = 200:

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

qui crée un fichier, A.prof, contenant:

    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

Indiquant que tout votre temps est passé dans numDivs, et c'est aussi la source de toutes vos allocations.

Profils de tas

Vous pouvez également obtenir une ventilation de ces allocations, en exécutant avec + RTS -p -hy, qui crée A.hp, que vous pouvez afficher en le convertissant en fichier postscript (hp2ps -c A.hp), générant:

ce qui nous dit qu'il n'y a rien de mal avec votre utilisation de la mémoire: elle alloue dans un espace constant.

Votre problème est donc la complexité algorithmique de numDivs:

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

Corrigez cela, qui correspond à 100% de votre temps de fonctionnement, et tout le reste est facile.

Optimisations

Cette expression est un bon candidat pour l' optimisation de la fusion de flux , je vais donc la réécrire pour utiliser Data.Vector , comme ceci:

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))

Ce qui devrait fusionner en une seule boucle sans allocations de tas inutiles. Autrement dit, il aura une meilleure complexité (par des facteurs constants) que la version liste. Vous pouvez utiliser l'outil ghc-core (pour les utilisateurs avancés) pour inspecter le code intermédiaire après l'optimisation.

Tester ceci, ghc -O2 - faire Z.hs

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

Cela a donc réduit le temps d'exécution de N = 150 de 3,5x, sans changer l'algorithme lui-même.

Conclusion

Votre problème est numDivs. C'est 100% de votre temps de fonctionnement et sa complexité est terrible. Pensez à numDivs, et comment, par exemple, pour chaque N que vous générez [2 .. ndiv 2 + 1] N fois. Essayez de mémoriser cela, car les valeurs ne changent pas.

Pour mesurer laquelle de vos fonctions est la plus rapide, envisagez d'utiliser le critère , qui fournira des informations statistiquement robustes sur les améliorations inférieures à la microseconde du temps d'exécution.

Addenda

Étant donné que numDivs représente 100% de votre temps de fonctionnement, toucher d'autres parties du programme ne fera pas beaucoup de différence, cependant, à des fins pédagogiques, nous pouvons également réécrire celles en utilisant la fusion de flux.

Nous pouvons également réécrire trialList, et nous fier à la fusion pour la transformer en boucle que vous écrivez à la main dans trialList2, qui est une fonction "prefix scan" (aka scanl):

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

De même pour sol:

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

Avec le même temps de fonctionnement global, mais un code un peu plus propre.

La réponse de Dons est excellente sans être un spoiler en donnant une solution directe au problème.
Ici, je veux suggérer un petit outil que j'ai écrit récemment. Cela vous fait gagner du temps pour écrire des annotations SCC à la main lorsque vous souhaitez un profil plus détaillé que le profil par défautghc -prof -auto-all . En plus, c'est coloré!

Voici un exemple avec le code que vous avez donné (*), le vert est OK, le rouge est lent:

Tout le temps passe à créer la liste des diviseurs. Cela suggère plusieurs choses que vous pouvez faire:
1. Accélérez le filtrage n rem x == 0, mais comme il s'agit d'une fonction intégrée, il est probablement déjà rapide.
2. Créez une liste plus courte. Vous avez déjà fait quelque chose dans ce sens en ne vérifiant que jusqu'à n quot 2.
3. Jetez complètement la génération de liste et utilisez des mathématiques pour obtenir une solution plus rapide. C'est la manière habituelle pour les problèmes du projet Euler.

(*) J'ai obtenu cela en mettant votre code dans un fichier appelé eu13.hs, en ajoutant une fonction principale main = print $ sol 90. Puis en cours d'exécution visual-prof -px eu13.hs eu13et le résultat est entré eu13.hs.html.

Note liée à Haskell: triaList2est bien sûr plus rapide que triaListparce que ce dernier effectue beaucoup de calculs inutiles. Il faudra un temps quadratique pour calculer n premiers éléments de triaList, mais linéaire pour triaList2. Il existe une autre façon élégante (et efficace) de définir une liste infinie de nombres triangulaires paresseux:

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

Note relative aux mathématiques: il n'est pas nécessaire de vérifier tous les diviseurs jusqu'à n / 2, il suffit de vérifier jusqu'à sqrt (n).

Vous pouvez exécuter votre programme avec des indicateurs pour activer le profilage temporel. Quelque chose comme ça:

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

Cela devrait exécuter le programme et produire un fichier appelé program.stats qui indiquera le temps passé dans chaque fonction. Vous pouvez trouver plus d'informations sur le profilage avec GHC dans le guide de l'utilisateur du GHC . Pour l'analyse comparative, il existe la bibliothèque Criterion. J'ai trouvé que ce billet de blog avait une introduction utile.