hızlı

Question

Haskell histogram hesaplama yapma ben Haskell oldukça yeni ve bir histogram oluşturmak isteyen. Verilerdeki işlemleri sigortalamak için Data.Vector.Unboxed kullanıyorum; hızlı yanan (-O-fllvm ile derlendiğinde) ve darboğaz benim katlama uygulamasıdır; Kepçe sayımları birleştirir.

Nasıl daha hızlı yapabilirim? Ben şeyleri katı tutarak thunks sayısını azaltmak için okumaya devam ediyorum, bu yüzden çok daha fazla performans artışı göremiyorum ama seq ve foldr kullanarak şeyler sıkı yaptım. Fikirleriniz kuvvetle teşvik edilir.

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 

ile Derleyen:

ghc --make -O -fllvm histogram.hs 

Answer 1

Birincisi, -O2 -rtsopts ile programı derlemek. % 67 zaman GC harcanmaktadır

$ ./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 

Bildirimi olun: Ardından, optimize seçenekleri +RTS -sstderr ile programı çalıştırabilir ilk fikir edinmek için! Açıkça yanlış bir şey var. yanlış olduğunu öğrenmek için, aşağıdaki şekle üretir (+RTS -h kullanarak) etkin yığın profilleme ile programı çalıştırabilirsiniz:

Yani, sızıntımız Thunks. Bu nasıl olur? Koduna bakıldığında, agg numaralı telefonda bir thunk'ın (yinelemeli olarak) oluşturulduğu tek zaman, eki yaptığınız zamandır. böylece patlama deseni ekleyerek sıkı cv Making sorunu giderir:

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

Çıktı:

$ 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 

Bu çok daha iyidir.

---

Yani şimdi sorabilirsiniz, neden sorun, seq kullanılan rağmen ortaya çıktı? Bunun nedeni seq sadece WHNF olmak için ilk argüman zorlar, ve bir çift için, (_ unevaluated thunks vardır) (_,_) zaten WHNF olduğunu! böylece seq a a sadece anlamına gelir, b önce değerlendirilir değerlendirmek: Ayrıca, seq a b (gayri) demektir çünkü seq a a, a aynıdır bir önce değerlendirilir değerlendirmek, ve bu sadece bir değerlendirmede aynıdır!