Dokonywanie obliczeń histogramu w Haskell szybciej

Question

Jestem całkiem nowy dla Haskell i chcę utworzyć histogram. Używam Data.Vector.Unboxed do fuse operacji na danych; który płonie szybko (gdy skompilowany z -O-flvvm) a wąskie gardło jest moją aplikacją; który agreguje liczbę kubłów.

Jak mogę przyspieszyć? Czytałem o próbach zredukowania liczby uderzeń, utrzymując ścisłą ścisłość, więc zrobiłem rzeczy ścisłe, używając seq i foldr ', ale nie widząc dużego wzrostu wydajności. Twoje pomysły są silnie wspierane.

import qualified Data.Vector.Unboxed as V 

histogram :: [(Int,Int)] 
histogram = V.foldr' agg [] $ V.zip k v 
where 
    n = 10000000 
    c = 1000000 
    k = V.generate n (\i -> i `div` c * c) 
    v = V.generate n (\i -> 1) 
    agg kv [] = [kv] 
    agg kv@(k,v) acc@((ck,cv):as) 
     | k == ck = let a = (ck,cv+v):as in a `seq` a 
     | otherwise = let a = kv:acc in a `seq` a 

main :: IO() 
main = print histogram 

skompilowany z:

ghc --make -O -fllvm histogram.hs 

Answer 1

Najpierw skompilować program z -O2 -rtsopts. Następnie, aby uzyskać pierwsze pojęcia, gdzie można zoptymalizować, uruchom program z opcjami +RTS -sstderr:

$ ./question +RTS -sstderr 
[(0,1000000),(1000000,1000000),(2000000,1000000),(3000000,1000000),(4000000,1000000),(5000000,1000000),(6000000,1000000),(7000000,1000000),(8000000,1000000),(9000000,1000000)] 
    1,193,907,224 bytes allocated in the heap 
    1,078,027,784 bytes copied during GC 
    282,023,968 bytes maximum residency (7 sample(s)) 
     86,755,184 bytes maximum slop 
      763 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  1964 colls,  0 par 3.99s 4.05s  0.0021s 0.0116s 
    Gen 1   7 colls,  0 par 1.60s 1.68s  0.2399s 0.6665s 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT  time 2.67s ( 2.68s elapsed) 
    GC  time 5.59s ( 5.73s elapsed) 
    EXIT time 0.02s ( 0.03s elapsed) 
    Total time 8.29s ( 8.43s elapsed) 

    %GC  time  67.4% (67.9% elapsed) 

    Alloc rate 446,869,876 bytes per MUT second 

    Productivity 32.6% of total user, 32.0% of total elapsed 

Uwaga, 67% swojego czasu spędza w GC! Coś jest nie tak. Aby dowiedzieć się, co jest nie tak, możemy uruchomić program z sterty profilowania (za pomocą +RTS -h), który produkuje następującą postać:

Więc masz nieszczelne łącznikami. Jak to się stało? Patrząc na kod, jedyny czas, w którym thunk jest tworzony (rekursywnie) w agg, jest po dodaniu. Dokonywanie cv ścisłego dodając wzór huk ten sposób rozwiązuje ten problem:

{-# LANGUAGE BangPatterns #-} 
import qualified Data.Vector.Unboxed as V 

histogram :: [(Int,Int)] 
histogram = V.foldr' agg [] $ V.zip k v 
where 
    n = 10000000 
    c = 1000000 
    k = V.generate n (\i -> i `div` c * c) 
    v = V.generate n id 
    agg kv [] = [kv] 
    agg kv@(k,v) acc@((ck,!cv):as) -- Note the ! 
     | k == ck = (ck,cv+v):as 
     | otherwise = kv:acc 

main :: IO() 
main = print histogram 

wyjściowa:

$ time ./improved +RTS -sstderr 
[(0,499999500000),(1000000,1499999500000),(2000000,2499999500000),(3000000,3499999500000),(4000000,4499999500000),(5000000,5499999500000),(6000000,6499999500000),(7000000,7499999500000),(8000000,8499999500000),(9000000,9499999500000)] 
    672,063,056 bytes allocated in the heap 
      94,664 bytes copied during GC 
    160,028,816 bytes maximum residency (2 sample(s)) 
     1,464,176 bytes maximum slop 
      155 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  992 colls,  0 par 0.03s 0.03s  0.0000s 0.0001s 
    Gen 1   2 colls,  0 par 0.03s 0.03s  0.0161s 0.0319s 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT  time 1.24s ( 1.25s elapsed) 
    GC  time 0.06s ( 0.06s elapsed) 
    EXIT time 0.03s ( 0.03s elapsed) 
    Total time 1.34s ( 1.34s elapsed) 

    %GC  time  4.4% (4.5% elapsed) 

    Alloc rate 540,674,868 bytes per MUT second 

    Productivity 95.5% of total user, 95.1% of total elapsed 

./improved +RTS -sstderr 1,14s user 0,20s system 99% cpu 1,352 total 

Jest to o wiele lepiej.

---

Więc teraz można zapytać, dlaczego pojawia się problem, nawet jeśli używane seq? Powodem tego jest seq tylko zmusza pierwszy argument do WHNF, a dla pary, (_,_) (gdzie _ są niedoszacowane thunks) jest już WHNF! Również seq a a jest taka sama jak a, ponieważ seq a b (nieformalnie) oznacza: ocenić przed b ocenia, więc seq a a oznacza po prostu: ocenić przed ocenia, i że jest taka sama jak tylko oceniania!