Strumenti per l'analisi delle prestazioni di un programma Haskell

Question

Durante la risoluzione di alcuni problemi Euler di progetto per l'apprendimento di Haskell (così attualmente sono completamente alle prime armi) sono arrivato a Problem 13. Ho scritto questa soluzione (ingenua):

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

questa soluzione per n = 500 (sol 500) è estremamente lento (in esecuzione per più di 2 ore ora), quindi mi chiedevo come trovare il motivo per cui questa soluzione è così lento. Ci sono comandi che mi dicono dove trascorre la maggior parte del tempo di calcolo, quindi so quale parte del mio programma haskell è lenta? Qualcosa come un semplice profiler.

mettere in chiaro, non sto chiedendo per una soluzione più veloce, ma per un modo per trovare questa soluzione. Come partiresti se non avessi conoscenze di haskell?

Ho provato a scrivere due funzioni di triaList ma non ho trovato alcun modo per testare quale sia più veloce, quindi è da lì che iniziano i miei problemi.

Grazie

Answer 1

come scoprire perché questa soluzione è così lenta. Ci sono comandi che mi dicono dove trascorre la maggior parte del tempo di calcolo, quindi so quale parte del mio programma haskell è lenta?

Precisamente! GHC fornisce molti strumenti eccellenti, tra cui:

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

Un tutorial sull'uso del tempo e la profilazione dello spazio è part of Real World Haskell.

GC Statistiche

In primo luogo, assicurarsi che si sta compilando con -O2 GHC. E potresti assicurarti che sia un GHC moderno (ad esempio GHC 6.12.x)

La prima cosa che possiamo fare è controllare che la garbage collection non sia il problema. Eseguire il programma con + 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 

che già ci dà un sacco di informazioni: si ha solo un mucchio 2M, e GC occupa lo 0,8% del tempo. Quindi non c'è bisogno di preoccuparsi che l'allocazione sia il problema.

Tempo Profili

Ottenere un profilo temporale per il vostro programma è semplice: compilare con -Prof -auto-all

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

E, per N = 200:

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

che crea un file, A.prof, contenente:

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 

Indicando che all il tuo tempo è trascorso in numDivs, ed è anche la fonte di tutte le tue allocazioni.

Profili Heap

È inoltre possibile ottenere una ripartizione di queste allocazioni, eseguendo con + RTS -hy -p, che crea A.hp, che è possibile visualizzare convertendolo in un file PostScript (hp2ps -c A.hp), generando:

che ci dice non c'è niente di sbagliato con l'utilizzo di memoria: è l'allocazione nello spazio costante.

Così il vostro problema è la complessità algoritmica di numDivs:

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

correzione, che è il 100% del il tempo di esecuzione, e tutto il resto è facile.

Ottimizzazioni

questa espressione è un buon candidato per la stream fusion ottimizzazione, quindi mi riscriverlo utilizzare Data.Vector, in questo modo:

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

Che dovrebbe fondersi in un unico ciclo senza allocazioni di heap non necessarie. Cioè, avrà una migliore complessità (da fattori costanti) rispetto alla versione lista. È possibile utilizzare lo strumento ghc-core (per utenti esperti) per ispezionare il codice intermedio dopo l'ottimizzazione.

Testare questo, ghc -O2 --make Z.hs

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

Quindi ha ridotto il tempo di esecuzione per N = 150 di 3,5x, senza modificare l'algoritmo stesso.

Conclusione

Il tuo problema è numDivs. È il 100% del tempo di esecuzione e ha una complessità terribile. Pensa a numDivs e come, ad esempio, per ogni N stai generando [2 .. n div 2 + 1] N volte. Prova a memoizzarlo, poiché i valori non cambiano.

Per misurare quale delle funzioni è più veloce, considerare l'utilizzo di criterion, che fornirà informazioni statisticamente valide sui miglioramenti del microsecondo in termini di tempo di esecuzione.

---

Addenda

Dal numDivs è al 100% del il tempo di esecuzione, toccando altre parti del programma non farà molta differenza, tuttavia, a fini pedagogici, possiamo anche riscrivere quelli che utilizzano fusione di corrente.

Possiamo anche riscrivere trialList, e si basano sulla fusione per trasformarlo in loop si scrive a mano in trialList2, che è una funzione "scan prefisso" (aka scanl):

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

Allo stesso modo per sol:

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

Con lo stesso tempo di esecuzione complessivo, ma un codice un po 'più pulito.

Answer 2

Haskell nota relativa: triaList2 è ovviamente più veloce di triaList perché quest'ultimo svolge un sacco di calcoli inutili. Ci vorrà un tempo quadratico per calcolare i primi elementi di triaList, ma lineare per triaList2. C'è un altro modo elegante (ed efficiente) per definire un infinito elenco pigro dei numeri triangolo:

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

matematica nota relativa: non c'è bisogno di controllare tutti i divisori fino a n/2, è sufficiente controllare fino a sqrt (n).

Answer 3

È possibile eseguire il programma con flag per abilitare la creazione del profilo temporale. Qualcosa di simile a questo:

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

Questo dovrebbe eseguire il programma e produrre un file chiamato program.stats che dovranno quanto tempo è stato speso in ogni funzione. È possibile trovare ulteriori informazioni sulla creazione di profili con GHC in GHC user guide. Per il benchmarking, c'è la libreria Criterion. Ho trovato che il post sul blog this ha un'introduzione utile.

Answer 4

La risposta di Dons è ottima senza essere uno spoiler dando una soluzione diretta al problema.
Qui voglio suggerire un po 'di tool che ho scritto di recente. Ti consente di risparmiare tempo per scrivere annotazioni SCC a mano quando desideri un profilo più dettagliato rispetto al valore predefinito ghc -prof -auto-all. Oltre a ciò è colorato!

Ecco un esempio con il codice che hai dato (*), il verde è OK, il rosso è lento:

Tutto il passare del tempo nel creare l'elenco dei divisori. Questo suggerisce alcune cose che puoi fare:
1. Rendere il filtro n rem x == 0 più veloce, ma dal momento che è una funzione integrata probabilmente è già veloce.
2. Creare un elenco più breve. Hai già fatto qualcosa in quella direzione controllando solo fino a n quot 2.
3. Elimina completamente la generazione di elenchi e utilizza alcuni calcoli per ottenere una soluzione più rapida. Questo è il solito modo per i problemi del progetto Eulero.

(*) Ho ottenuto questo mettendo il codice in un file chiamato eu13.hs, aggiungendo una funzione principale main = print $ sol 90. Quindi eseguire visual-prof -px eu13.hs eu13 e il risultato è eu13.hs.html.