Narzędzia do analizy wydajności programu Haskell

Podczas rozwiązywania niektórych problemów projektu Eulera, aby nauczyć się Haskella (więc obecnie jestem całkowicie początkującym), natknąłem się na Problem 12 . Napisałem to (naiwne) rozwiązanie:

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

To rozwiązanie dla n=500 (sol 500)jest bardzo wolne (działa teraz ponad 2 godziny), więc zastanawiałem się, jak dowiedzieć się, dlaczego to rozwiązanie jest tak wolne. Czy są jakieś polecenia, które mówią mi, gdzie spędza się większość czasu obliczeń, aby wiedzieć, która część mojego programu haskell działa wolno? Coś w rodzaju prostego profilera.

Żeby było jasne, nie pytam o szybszym rozwiązaniem, ale na sposób znalezienia tego rozwiązania. Jak byś zaczął, gdybyś nie miał wiedzy o haskellach?

Próbowałem napisać dwie triaListfunkcje, ale nie znalazłem sposobu, aby przetestować, która z nich jest szybsza, więc tutaj zaczynają się moje problemy.

Dzięki

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 obliczeń, aby wiedzieć, która część mojego programu haskell działa wolno?

Dokładnie! GHC zapewnia wiele doskonałych narzędzi, w tym:

• statystyki działania
• profilowanie czasu
• profilowanie sterty
• analiza wątku
• analiza podstawowa.
• porównawcza analiza porównawcza
• Strojenie GC

Samouczek na temat korzystania z profilowania w czasie i przestrzeni jest częścią Real World 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ą, jaką możemy zrobić, jest sprawdzenie, czy czyszczenie pamięci nie stanowi problemu. Uruchom swój 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 już daje nam wiele informacji: masz tylko stertę 2M, a GC zajmuje 0,8% czasu. Nie musisz się więc martwić, że problemem jest alokacja.

Profile czasowe

Uzyskanie profilu czasowego dla twojego programu jest proste: skompiluj z -prof -auto-all

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

A 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

Wskazuje, że cały czas spędzasz w numDivs i jest to również źródło wszystkich twoich przydziałów.

Profile sterty

Możesz również uzyskać zestawienie tych przydziałów, uruchamiając + RTS -p -hy, co tworzy A.hp, który można 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: alokuje ona w stałej przestrzeni.

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

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

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

Optymalizacje

To wyrażenie jest dobrym kandydatem do optymalizacji fuzji strumienia , więc przepiszę je, aby używał Data.Vector , na przykład:

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óre powinny zostać połączone w jedną pętlę bez zbędnych alokacji sterty. Oznacza to, że będzie miał większą złożoność (według stałych czynników) niż wersja listy. Możesz użyć narzędzia ghc-core (dla zaawansowanych użytkowników), aby sprawdzić kod pośredni po optymalizacji.

Testując to, ghc -O2 --make Z.hs

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

Więc skrócił czas działania dla N = 150 o 3,5x, bez zmiany samego algorytmu.

Wniosek

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

Aby zmierzyć, która z funkcji jest szybsza, rozważ zastosowanie kryterium , które zapewni statystycznie wiarygodne informacje o poprawie czasu działania poniżej mikrosekundy.

Uzupełnienia

Ponieważ numDivs to 100% twojego czasu pracy, dotykanie innych części programu nie zrobi dużej różnicy, jednak ze względów pedagogicznych możemy również przepisać te za pomocą fuzji strumieniowej.

Możemy również przepisać trialList i polegać na fusion, aby przekształcić ją w pętlę, którą piszesz ręcznie w trialList2, która jest funkcją „skanowania prefiksów” (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 takim samym ogólnym czasem działania, ale nieco czystszym kodem.

Odpowiedź Donsa jest świetna, nie będąc spoilerem, dając bezpośrednie rozwiązanie problemu.
Tutaj chcę zasugerować małe narzędzie, które niedawno napisałem. Oszczędza czas potrzebny na ręczne pisanie adnotacji SCC, gdy chcesz uzyskać bardziej szczegółowy profil niż domyślny ghc -prof -auto-all. Poza tym jest kolorowo!

Oto przykład z kodem, który podałeś (*), zielony jest OK, czerwony jest wolny:

Cały czas trwa tworzenie listy dzielników. Sugeruje to kilka rzeczy, które możesz zrobić:
1. n rem x == 0Przyspiesz filtrowanie , ale ponieważ jest to funkcja wbudowana, prawdopodobnie jest już szybkie.
2. Utwórz krótszą listę. Zrobiłeś już coś w tym kierunku, sprawdzając tylko do n quot 2.
3. Całkowicie odrzuć generowanie listy i użyj matematyki, aby uzyskać szybsze rozwiązanie. Jest to typowy sposób rozwiązywania problemów związanych z projektem Eulera.

(*) Otrzymałem to, umieszczając Twój kod w pliku o nazwie eu13.hs, dodając główną funkcję main = print $ sol 90. Następnie działa visual-prof -px eu13.hs eu13i wynik jest gotowy eu13.hs.html.

Uwaga związana z Haskellem: triaList2jest oczywiście szybsza niż triaListdlatego, że ten ostatni wykonuje wiele niepotrzebnych obliczeń. Obliczenie pierwszych elementów n pierwszych elementów zajmie kwadratowe triaList, ale liniowe dla triaList2. Istnieje inny elegancki (i skuteczny) sposób definiowania nieskończonej leniwej listy liczb trójkątnych:

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

Uwaga związana z matematyką: nie ma potrzeby sprawdzania wszystkich dzielników do n / 2, wystarczy sprawdzić do sqrt (n).

Możesz uruchomić swój program z flagami, aby włączyć profilowanie czasu. Coś takiego:

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

Powinno to uruchomić program i utworzyć plik o nazwie program.stats, który będzie zawierał informacje o ilości czasu spędzonego na każdej funkcji. Więcej informacji na temat profilowania za pomocą GHC można znaleźć w podręczniku użytkownika GHC . Do testów porównawczych dostępna jest biblioteka kryteriów. Znalazłem ten blog post ma użyteczną wprowadzenie.