Tools zum Analysieren der Leistung eines Haskell-Programms

Question

Beim Lösen einiger Projekt-Euler-Probleme, um Haskell zu lernen (also bin ich momentan ein absoluter Anfänger), kam ich über Problem 13. Ich schrieb diese (naive) Lösung:

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

Diese Lösung für n = 500 (sol 500) extrem langsam ist (für mehr als 2 Stunden läuft jetzt), so dass ich fragte mich, wie um herauszufinden, warum diese Lösung so ist langsam. Gibt es irgendwelche Befehle, die mir sagen, wo die meiste Rechenzeit ausgegeben wird, damit ich weiß, welcher Teil meines Haskell-Programms langsam ist? So etwas wie ein einfacher Profiler.

Um deutlich zu machen, ich bitte nicht für eine schnellere Lösung, aber für eine Art und Weise diese Lösung zu finden. Wie würdest du anfangen, wenn du kein harkell Wissen hättest?

Ich habe versucht, zwei triaList-Funktionen zu schreiben, habe aber keine Möglichkeit gefunden, zu testen, welche schneller ist, so dass meine Probleme beginnen.

Dank

Answer 1

wie Sie herausfinden, warum diese Lösung so langsam ist. Gibt es irgendwelche Befehle, die mir sagen, wo die meiste Rechenzeit ausgegeben wird, damit ich weiß, welcher Teil meines Haskell-Programms langsam ist?

Genau! GHC bietet viele hervorragende Werkzeuge, darunter:

• runtime statistics
• time profiling
• heap profiling
• thread analysis
• core analysis.
• comparative benchmarking
• GC tuning

Ein Tutorial zur Verwendung von Zeit- und Raumprofilen ist part of Real World Haskell.

GC Statistik

Zum einen stellen Sie sicher, mit ghc -O2 sind kompilieren. Und Sie können sicherstellen, dass es sich um einen modernen GHC handelt (z. B. GHC 6.12.x)

Das erste, was wir tun können, ist zu überprüfen, dass Garbage Collection nicht das Problem ist. Führen Sie Ihr Programm mit + 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 

Was uns schon eine Menge Informationen gibt: Sie haben nur einen 2M Haufen haben, und GC nimmt 0,8% der Zeit. Sie müssen sich also keine Sorgen machen, dass die Zuweisung das Problem ist.

Zeitprofile

Erste ein Zeitprofil für Ihr Programm ist einfach: kompilieren mit -Prof -auto-all

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

Und für N = 200:

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

erstellt eine Datei, A.prof, die enthält:

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 

Angabe, dass alle Ihre Zeit in numDivs ausgegeben wird, und es ist auch die Quelle all Ihrer Zuweisungen.

Heap Profile

Sie auch ein Abbau dieser Zuweisungen erhalten können, indem sie mit + RTS -p -Hy ausgeführt wird, die A.hp erstellt, die Sie durch Umwandlung in eine Postscript-Datei anzeigen können, (hp2ps -c A.hp), Erzeugen:

die uns sagt, es ist nichts falsch mit Ihrem Gedächtnis Verwendung: es wird in konstanten Raum zuordnet.

So ist Ihr Problem algorithmische Komplexität von numDivs:

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

Fix, die, die zu 100% der Laufzeit ist, und alles andere ist einfach.

Optimizations

Dieser Ausdruck ist ein guter Kandidat für die stream fusion Optimierung, also werde ich es umschreiben Data.Vector zu verwenden, etwa so:

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

, die in einer einzigen Schleife verschmelzen sollte ohne unnötige Heapzuweisungen. Das heißt, es wird eine bessere Komplexität (durch konstante Faktoren) als die Listenversion haben. Sie können das ghc-core-Tool (für fortgeschrittene Benutzer) verwenden, um den Zwischencode nach der Optimierung zu überprüfen.

Testen Sie dies, ghc -O2 - machen Z.hs

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

So reduzierte es die Laufzeit für N = 150 um 3,5x, ohne den Algorithmus selbst zu ändern.

Fazit

Ihr Problem ist numDivs. Es ist 100% Ihrer Laufzeit und hat eine schreckliche Komplexität. Denken Sie an numDivs und wie zum Beispiel für jedes N Sie [2 .. n div 2 + 1] N-mal erzeugen. Versuchen Sie, dies zu notieren, da sich die Werte nicht ändern.

Um zu messen, welche Ihrer Funktionen schneller ist, sollten Sie die Verwendung von criterion in Erwägung ziehen, die statistisch robuste Informationen über Verbesserungen der Laufzeit im Sub-Mikrosekunden-Bereich liefert.

---

Addenda

Seit numDivs 100% Ihrer Laufzeit ist, werden andere Teile des Programms berührt nicht viel Unterschied machen, jedoch für pädagogische Zwecke, können wir auch umschreiben diejenigen mit Strom Fusion.

Wir können auch trialList umschreiben, und verlassen sich auf Fusion in die Schleife drehen Sie von Hand in trialList2 schreiben, , die ein "Präfix-Scan" -Funktion (aka scanl):

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

Ähnliches gilt für sol:

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

Mit der gleichen Gesamtlaufzeit, aber ein bisschen sauberer Code.

Answer 2

Haskell Anmerkung: triaList2 ist natürlich schneller als triaList weil letztere eine Menge unnötiger Berechnungen durchführt. Es wird quadratische Zeit benötigen, um n erste Elemente von triaList zu berechnen, aber linear für triaList2. Es ist eine weitere elegante (und effizient) Art und Weise eine unendliche faul Liste von Dreieckszahlen zu definieren:

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

Math In Verbindung stehende Anmerkung: Es gibt keine Notwendigkeit, all Divisoren n bis überprüfen/2, es ist genug, um zu überprüfen, bis zu sqrt (n).

Answer 3

Sie können Ihr Programm mit Flags ausführen, um Zeitprofile zu aktivieren. Etwas wie folgt aus:

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

, dass das Programm ausgeführt werden soll und erzeugen eine angerufene program.stats Datei, die, wie viel Zeit wird in jeder Funktion verbracht. Weitere Informationen zum Profiling mit GHC finden Sie im GHC user guide. Zum Benchmarking gibt es die Criterion-Bibliothek. Ich habe gefunden this Blog-Post hat eine nützliche Einführung.

Answer 4

Dons Antwort ist großartig, ohne ein Spoiler zu sein, indem man eine direkte Lösung für das Problem gibt.
Hier möchte ich vorschlagen, ein wenig tool, dass ich kürzlich schrieb. Es spart Ihnen die Zeit, SCC-Anmerkungen von Hand zu schreiben, wenn Sie ein detaillierteres Profil als das Standardprofil ghc -prof -auto-all wünschen. Außerdem ist es bunt!

Hier ist ein Beispiel mit dem Code, den Sie gab (*), grün ist OK, rot ist langsam:

Die ganze Zeit geht die Liste der Teilern zu schaffen. Dies schlägt ein paar Dinge vor, die Sie tun können:
1. Machen Sie die Filterung n rem x == 0 schneller, aber da es eine eingebaute Funktion ist, ist es wahrscheinlich schon schnell.
2. Erstellen Sie eine kürzere Liste. Sie haben bereits etwas in diese Richtung getan, indem Sie nur bis zu n quot 2 überprüft haben.
3. Werfen Sie die Listengenerierung vollständig weg und verwenden Sie etwas Mathe, um eine schnellere Lösung zu erhalten. Dies ist der übliche Weg für Projekt Euler Probleme.

(*) Ich habe das, indem Sie Ihren Code in eine Datei namens eu13.hs, eine Hauptfunktion main = print $ sol 90 hinzufügen. Dann läuft visual-prof -px eu13.hs eu13 und das Ergebnis ist in eu13.hs.html.