ghc - Making a histogram computation in Haskell faster -
i quite new haskell , wanting create histogram. using data.vector.unboxed fuse operations on data; blazing fast (when compiled -o -fllvm) , bottleneck fold application; aggregates bucket counts.
how can make faster? read trying reduce number of thunks keeping things strict i've made things strict using seq , foldr' not seeing performance increase. ideas encouraged.
import qualified data.vector.unboxed v histogram :: [(int,int)] histogram = v.foldr' agg [] $ v.zip k v n = 10000000 c = 1000000 k = v.generate n (\i -> `div` c * c) v = v.generate n (\i -> 1) agg kv [] = [kv] agg kv@(k,v) acc@((ck,cv):as) | k == ck = let = (ck,cv+v):as in `seq` | otherwise = let = kv:acc in `seq` main :: io () main = print histogram compiled with:
ghc --make -o -fllvm histogram.hs
first, compile program -o2 -rtsopts. then, first idea optimize, run program options +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 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 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 notice 67% of time spent in gc! there wrong. find out wrong, can run program heap profiling enabled (using +rts -h), produces following figure:
so, you're leaking thunks. how happen? looking @ code, time thunk build (recursively) in agg when addition. making cv strict adding bang pattern fixes issue:
{-# language bangpatterns #-} import qualified data.vector.unboxed v histogram :: [(int,int)] histogram = v.foldr' agg [] $ v.zip k v n = 10000000 c = 1000000 k = v.generate n (\i -> `div` c * c) v = v.generate n id agg kv [] = [kv] agg kv@(k,v) acc@((ck,!cv):as) -- note ! | k == ck = (ck,cv+v):as | otherwise = kv:acc main :: io () main = print histogram output:
$ 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 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 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 this better.
so ask, why did issue appear, though used seq? reason seq forces first argument whnf, , pair, (_,_) (where _ unevaluated thunks) whnf! also, seq a same a, because seq b (informally) means: evaluate before b evaluated, seq a means: evaluate before evaluated, , same evaluating a!
Comments
Post a Comment