Outils d'analyse de la performance D'un programme Haskell

comment savoir pourquoi cette solution est si lent. Y a-t-il des commandes qui me disent où passe la plupart du temps de calcul pour que je sache quelle partie de mon programme haskell est lente?

précisément! GHC fournit de nombreux excellents outils, y compris:

• "statistiques d'exécution
• temps de profilage
• profilage de tas
• thread "l'analyse de l'1519190920"
• de base de l'analyse.
• étalonnage comparatif
• GC "réglage de 1519190920"

un tutoriel sur l'utilisation du profilage temporel et spatial est partie du monde réel Haskell .

statistiques GC

tout d'abord, assurez-vous de compiler avec ghc-O2. Et vous pourriez 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 la collecte des ordures 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

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 de il faut s'inquiéter que la répartition soit le problème.

Temps Des Profils

obtenir un profil de temps pour votre programme est simple: compiler 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.

Tas De Profils

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

qui nous dit qu'il n'y a rien de mal à utiliser votre mémoire: répartition en espace constant.

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

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

réparez ça, ce qui représente 100% de votre temps de course, et tout le reste est facile.

optimisations

cette expression est un bon candidat pour l'optimisation stream fusion , donc je vais la réécrire pour utiliser les données .Vecteur , 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))

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

Testing this, ghc-O2 -- make Z. hs

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

de sorte qu'il a réduit la durée de fonctionnement pour N=150 de 3,5 x, sans changer le algorithme lui-même.

Conclusion

votre problème est numDivs. C'est 100% de votre temps de course, et a terrible complexité. pensez à numDivs, et comment, par exemple, pour chaque N que vous générez [2 .. n div 2 + 1]N fois. Essayez de mémoriser ça, 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 sous-microsecondes du temps de fonctionnement.

---

Addenda

puisque numDivs est 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 ceux qui utilisent stream 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 une fonction "prefix scan" (alias 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 peu plus de code.