Narzędzia do analizy wydajności programu Haskell

Jak dowiedzieć się, dlaczego to rozwiązanie jest tak powolne. Czy są jakieś polecenia, które mówią mi, gdzie spędza się większość czasu obliczeniowego, abym wiedział, która część mojego programu haskell jest wolna?

• statystyki runtime
• profilowanie czasu
• profilowanie stosu
• analiza wątków
• rdzeń analiza.
• porównawczy benchmarking
• GC tuning

Samouczek na temat korzystania z profilowania w czasie i przestrzeni jest częścią realnego świata Haskell .

Statystyki GC

Po pierwsze, upewnij się, że kompilujesz z ghc-O2. I możesz się upewnić, że jest to nowoczesny GHC (np. GHC 6.12.x)

Pierwszą rzeczą, którą możemy zrobić, to sprawdzić, czy wywóz śmieci nie jest problemem. Uruchom program z + 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

Co daje nam już wiele informacji: masz tylko 2M sterty, a GC zajmuje 0,8% czasu. Więc nie musisz się martwić, że alokacja jest problemem.

Profile Czasowe

Uzyskanie profilu czasu dla Twojego programu jest proste: skompiluj za pomocą-prof-auto-all

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

I, dla N=200:

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

Który tworzy plik, A. prof, zawierający:

    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

Wskazując, że cały twój czas spędzony jest w numDivs, jest to również źródło wszystkich Twoich przydziałów.

Profile Sterty

Możesz również uzyskać podział tych alokacji, uruchamiając z +RTS-p-hy, który tworzy A. hp, który możesz wyświetlić, konwertując go do pliku postscriptowego (hp2ps-c A. hp), generując:

Co mówi nam, że nie ma nic złego w używaniu pamięci: jest alokowana w stałej przestrzeni.

Więc Twoim problemem jest algorytmiczna złożoność numDivs:

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

Napraw to, co jest 100% twojego czasu pracy, a Wszystko inne jest łatwe.

Optymalizacje

To wyrażenie jest dobrym kandydatem do optymalizacjistream fusion , więc napiszę je ponownie aby użyć danych.Wektor , tak:

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

Który powinien połączyć się w jedną pętlę bez zbędnych przydziałów sterty. Oznacza to, że będzie miała lepszą złożoność (przez stałe czynniki) niż wersja listy. Możesz użyć ghc-core tool (dla zaawansowanych użytkowników) do kontroli kodu pośredniego po optymalizacji.

Testowanie tego, ghc-O2 -- make Z. hs

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

Skróciła więc czas pracy dla N=150 o 3,5 x, bez zmiany samego algorytmu.

Wniosek

Twój problem to numDivs. Jest to 100% twojego czasu pracy i ma straszną złożoność. pomyśl o numdivach i jak, na przykład, dla każdego N generujesz [2 .. n div 2 + 1] N razy. Spróbuj zapamiętać to, skoro wartości się nie zmieniają.

Aby zmierzyć, która z twoich funkcji jest szybsza, rozważ użycie kryterium , które dostarczy statystycznie solidnych informacji o ulepszeniach sub-mikrosekund w czasie działania.

Addenda

Ponieważ numDivs to 100% twojego czasu pracy, dotykanie innych części programu nie będzie miało większego znaczenia, jednak dla celów pedagogicznych możemy również przepisać te, które używają strumienia fuzja.

Możemy również przepisać triallistę i polegać na fusion, aby przekształcić ją w pętlę, którą piszesz ręcznie w trialList2, co jest funkcją "skanowania przedrostkowego" (aka scanl):

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

Podobnie dla sol:

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

Z tym samym ogólnym czasem pracy, ale nieco czystszym kodem.