Outils pour l'analyse des performances d'un programme Haskell

comment savoir pourquoi cette solution est si lent. Existe-il des commandes dites-moi où la plupart des calculs de temps donc je sais quelle partie de mon haskell-le programme est-il lent?

Précisément! GHC fournit beaucoup d'excellents outils, y compris:

• statistiques d'exécution
• le temps de profilage
• tas de profilage
• fil de l'analyse
• l'analyse des carottes.
• étalonnage comparatif
• GC tuning

Un tutoriel sur l'utilisation du temps et de l'espace de profilage est une partie de Real World Haskell.

GC Statistiques

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

La première chose que nous pouvons faire est de vérifier que la collecte des ordures n'est pas le problème.
Exécuter 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

Qui nous donne déjà beaucoup d'informations: vous n'avez qu'à 2M tas, et la cg prend en hausse de 0,8% du temps. Donc pas besoin de s'inquiéter que l'allocation est le problème.

Des Profils De Temps

L'obtention d'un profil de temps pour votre programme est simple: le compiler avec -prof -auto-tous les

 $ 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 consacré au numDivs, et c'est aussi la source de toutes vos allocations.

Tas De Profils

Vous pouvez également obtenir une ventilation de ces allocations, en exécutant avec +RTS-p -hy, qui crée de l'A. hp, que vous pouvez consulter en le convertissant vers un fichier postscript (hp2ps -c A. ch), la génération:

qui nous dit il n'y a rien de mal avec votre utilisation de la mémoire: c'est l'allocation de la constante de l'espace.

Si votre problème est la complexité algorithmique de numDivs:

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

Correctif, qui est de 100% de votre temps de course, et tout le reste est facile.

Optimisations

Cette expression est un bon candidat pour la flux de fusion d'optimisation, donc je vais le réécrire
pour utiliser Les données.Vecteur, comme suit:

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

Qui devraient fusionner en une seule boucle avec pas de superflu allocations de tas. C'est, il aura une meilleure complexité (par des facteurs constants) que la version de liste. Vous pouvez utiliser le ghc-outils de base (pour les utilisateurs avancés) pour inspecter le code intermédiaire après l'optimisation.

De tester ce, ghc -O2 --faire Z. hs

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

De sorte qu'il réduit les temps d'exécution pour N=150 par 3,5 x, sans modification de l'algorithme lui-même.

Conclusion

Votre problème est numDivs. C'est 100% de votre temps de course, et a terrible complexité. Penser numDivs, et comment, par exemple, pour chaque N de la production [2 .. n div 2 + 1] N fois.
Essayez memoizing que, puisque les valeurs ne changent pas.

À mesure de vos fonctions est plus rapide, pensez à utiliser critère, qui fournira statistiquement robuste de l'information sur la sous-microseconde des améliorations dans la gestion du temps.

---

Addenda

Depuis numDivs est de 100% de votre temps de course, de toucher d'autres parties du programme ne fera pas beaucoup de différence,
toutefois, à des fins pédagogiques, on peut aussi réécrire ces à l'aide de flux de fusion.

On peut aussi réécrire trialList, et de s'appuyer sur la fusion pour en faire la boucle de vous écrire à la main dans trialList2,
qui est un "préfixe d'analyse de la fonction" (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 course total, mais un peu plus propre code.

Haskell note: triaList2 est bien sûr plus rapide que triaList parce que celui-ci effectue beaucoup de calculs inutiles. Il faudra quadratique du temps pour calculer les n premiers éléments de triaList, mais linéaire pour triaList2. Il y a un autre élégant (et efficace) de manière à définir une infinie paresseux liste de triangle numéros:

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

Mathématiques liée remarque: il n'est pas nécessaire de vérifier tous les diviseurs de n /2, il suffit de vérifier jusqu'à sqrt(n).