Outils d'analyse des performances d'un programme Haskell

Question

En résolvant quelques problèmes du projet Euler pour apprendre Haskell (je suis donc actuellement complètement débutant), je suis tombé sur 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 (elle tourne depuis plus de deux heures maintenant), et je me suis donc demandé comment trouver pourquoi cette solution est si lente. Existe-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 que ce soit clair, je ne demande pas pour une solution plus rapide mais pour un moyen pour trouver cette solution. Comment commenceriez-vous si vous n'aviez aucune connaissance de haskell ?

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

Gracias

Answer 1

comment trouver pourquoi cette solution est si lente. Existe-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 outils excellents, notamment :

• statistiques sur l'exécution
• profilage temporel
• profilage du tas
• analyse des fils
• analyse de base.
• benchmarking comparatif
• Accord GC

Un didacticiel sur l'utilisation du profilage temporel et spatial est une 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 la GC prend 0,8% du temps. Il n'y a donc pas lieu de s'inquiéter que l'allocation soit le problème.

Profils temporels

Obtenir un profil temporel 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 tous votre temps est passé dans numDivs, et c'est aussi la source de toutes vos allocations.

Profils des tas

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

ce qui nous indique qu'il n'y a rien d'anormal dans l'utilisation de votre mémoire : elle est allouée 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

Réglez ce problème, qui représente 100% de votre temps de fonctionnement, et tout le reste est facile.

Optimisations

Cette expression est un bon candidat pour le fusion de flux l'optimisation, donc je vais la réécrire pour utiliser Vecteur de données comme ça :

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. C'est-à-dire qu'elle 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 optimisation.

Pour le tester, ghc -O2 --make Z.hs

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

Il a donc réduit de 3,5 fois le temps d'exécution pour N=150, sans modifier l'algorithme lui-même.

Conclusion

Votre problème est numDivs. Il représente 100% de votre temps d'exécution, et sa complexité est terrible. Pensez à numDivs, et à la façon dont, par exemple, pour chaque N, vous générez [2 n div 2 + 1] N fois. Essayez de mémoriser cela, puisque les valeurs ne changent pas.

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

---

Addenda

Comme numDivs représente 100% de votre temps d'exécution, toucher à d'autres parties du programme ne fera pas une grande différence, cependant, à des fins pédagogiques, nous pouvons aussi les réécrire en utilisant la fusion de flux.

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

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

De même pour le 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.

Answer 2

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 peu outil que j'ai écrit récemment. Il vous permet d'économiser le temps d'écrire les annotations SCC à la main lorsque vous souhaitez un profil plus détaillé que celui proposé par défaut. ghc -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 est consacré à la création de la liste des diviseurs. Cela suggère quelques choses que vous pouvez faire :
1. Faites le filtrage n rem x == 0 plus rapide, mais comme il s'agit d'une fonction intégrée, elle est probablement déjà rapide.
2. Créez une liste plus courte. Vous avez déjà fait quelque chose dans ce sens en vérifiant seulement jusqu'à n quot 2 .
3. Abandonnez complètement la génération de listes et utilisez les mathématiques pour obtenir une solution plus rapide. C'est la méthode habituelle pour les problèmes d'Euler de projet.

(*) 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 courant visual-prof -px eu13.hs eu13 et le résultat est dans eu13.hs.html .

Answer 3

Note relative à Haskell : triaList2 est bien sûr plus rapide que triaList car ce dernier effectue beaucoup de calculs inutiles. Il faudra un temps quadratique pour calculer les n premiers éléments de triaList mais linéaire pour triaList2 . Il existe une autre manière élégante (et efficace) de définir une liste paresseuse infinie de nombres triangulaires :

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

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

Answer 4

Vous pouvez exécuter votre programme avec des drapeaux pour activer le profilage temporel. Quelque chose comme ceci :

./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 manuel GHC guide de l'utilisateur . Pour le benchmarking, il y a la bibliothèque Criterion. J'ai trouvé este L'article du blog a une introduction utile.