Thực hiện phép tính biểu đồ trong Haskell nhanh hơn

Question

Tôi khá mới đối với Haskell và tôi muốn tạo biểu đồ. Tôi đang sử dụng Data.Vector.Unboxed để hoạt động cầu chì trên dữ liệu; đó là blazing nhanh (khi biên dịch với -O-fllvm) và nút cổ chai là ứng dụng gấp của tôi; tổng hợp số lượng xô.

Tôi làm cách nào để nhanh hơn? Tôi đã đọc về việc cố gắng giảm số lượng các thunks bằng cách giữ mọi thứ nghiêm ngặt vì vậy tôi đã thực hiện mọi thứ nghiêm ngặt bằng cách sử dụng seq và foldr 'nhưng không thấy tăng hiệu suất nhiều. Ý tưởng của bạn được khuyến khích mạnh mẽ.

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 

Biên soạn với:

ghc --make -O -fllvm histogram.hs 

Answer 1

Thứ nhất, biên dịch chương trình với -O2 -rtsopts. Sau đó, để có được một ý tưởng đầu tiên mà bạn có thể tối ưu hóa, chạy chương trình với các tùy chọn +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 

ý rằng 67% thời gian của bạn là chi tiêu trong GC! Rõ ràng có điều gì đó sai trái. Để tìm hiểu những gì là sai, chúng ta có thể chạy chương trình với đống hồ sơ cho phép (sử dụng +RTS -h), trong đó sản xuất hình sau:

thunks Vì vậy, bạn đang bị rò rỉ. Điều này xảy ra như thế nào? Nhìn vào mã, thời gian duy nhất mà một thunk được xây dựng (đệ quy) trong agg là khi bạn làm việc bổ sung. Làm cv nghiêm ngặt bằng cách thêm một mô hình vụ nổ như vậy, sửa chữa các vấn đề:

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

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

này là tốt hơn nhiều.

---

Bây giờ bạn có thể hỏi, tại sao sự cố xuất hiện, mặc dù bạn đã sử dụng seq? Lý do cho điều này là seq chỉ buộc đối số đầu tiên là WHNF và đối với một cặp, (_,_) (trong đó _ là khối không được đánh giá) đã là WHNF! Ngoài ra, seq a a cũng giống như a, bởi vì nó seq a b (không chính thức) có nghĩa là: đánh giá một trước khi b được đánh giá, vì vậy seq a a chỉ có nghĩa là: đánh giá một trước một được đánh giá, và đó là giống như chỉ đánh giá một!