하스켈에서 히스토그램 계산이 더 빠릅니다.

Question

저는 하스켈을 처음 접했고 히스토그램을 만들고 싶습니다. Data.Vector.Unboxed를 사용하여 데이터에 대한 연산을 통합합니다. (-O -fllvm으로 컴파일 될 때) 빠른 속도로 빨라지고 병목 현상이 접힌 다. 버킷 수를 집계합니다.

어떻게하면 더 빨리 만들 수 있습니까? 나는 물건을 엄격하게 유지함으로써 썽크의 수를 줄이려고 노력했기 때문에 seq와 foldr를 사용하여 엄격한 것을 만들었지 만 많은 성능 향상을 보지 못했다. 귀하의 아이디어는 적극 권장됩니다.

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 

과 함께 컴파일 :

ghc --make -O -fllvm histogram.hs 

Answer 1

첫째, -O2 -rtsopts로 프로그램을 컴파일합니다. 67 %의 시간는 GC에 소요되는

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

공지 것을 : 그런 다음, 최적화 옵션 +RTS -sstderr으로 프로그램을 실행할 수있는 최초의 아이디어를 얻을 수 있습니다! 분명히 잘못된 것이 있습니다. 어떤 문제가 있는지 확인하려면, 우리는 다음 그림을 생성 (+RTS -h 사용)를 활성화 힙 프로파일 링 프로그램을 실행할 수 있습니다

그래서, 당신은 누출하고 썽크를. 어떻게 될까요? 코드를 보면, 썽크가 (재귀 적으로) agg에 빌드되는 유일한 시간은 추가 작업입니다. 따라서 쾅 패턴을 추가하여 엄격한 cv를 만드는 것은 문제를 해결

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

출력 :

$ 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 

이 훨씬 낫다.

---

그래서 지금 당신이 질문을 할 수있어, 왜 문제가 당신이 seq을 사용하더라도 나타 납니까? 그 이유는 seq은 첫 번째 인수가 WHNF이고 두 번째 쌍이 (_,_) (_은 평가되지 않은 썽크 임)은 이미 WHNF입니다. 너무 seq a a 단지 수단 B 전에이을 평가 평가 : 또한,이 seq a b (비공식적) 의미하기 때문에 seq a a는 a와 동일 는 전에이을 평가 평가하고, 그 단의 평가와 동일!