在Haskell中做高效數字

Question

我被這篇名爲「Only fast languages are interesting」的帖子所啓發，看看他在Haskell中提出的問題（總結了幾百萬個來自矢量的數字），並與他的結果進行比較。

我是一個Haskell新手，所以我真的不知道如何正確的時間或如何有效地做到這一點，我對這個問題的第一次嘗試是以下。請注意，我沒有在矢量中使用隨機數字，因爲我不知道如何以良好的方式進行操作。爲了確保全面評估，我還印刷了一些東西。

import System.TimeIt 

import Data.Vector as V 

vector :: IO (Vector Int) 
vector = do 
    let vec = V.replicate 3000000 10 
    print $ V.length vec 
    return vec 

sumit :: IO() 
sumit = do 
    vec <- vector 
    print $ V.sum vec 

time = timeIt sumit 

加載這件事在GHCI和運行time告訴我，花了約0.22s至3萬個號碼和2.69s 30萬個號碼中運行。

與Lush中0.02s和0.18s的博客作者結果相比，情況要糟得多，這讓我相信這可以以更好的方式完成。

注意：上面的代碼需要運行包TimeIt。 cabal install timeit將爲您提供。

Answer 1

首先，認識到GHCi是一個解釋器，它的設計不是很快。要獲得更有用的結果，您應該在啓用優化的情況下編譯代碼。這可以產生巨大的差異。

此外，對於任何嚴肅的Haskell代碼基準測試，我推薦使用criterion。它使用各種統計技術來確保您獲得可靠的測量結果。

我修改了您的代碼以使用條件並刪除了打印語句，以便我們不計時I/O。

import Criterion.Main 
import Data.Vector as V 

vector :: IO (Vector Int) 
vector = do 
    let vec = V.replicate 3000000 10 
    return vec 

sumit :: IO Int 
sumit = do 
    vec <- vector 
    return $ V.sum vec 

main = defaultMain [bench "sumit" $ whnfIO sumit] 

與-O2編譯此，我得到一個相當緩慢的上網本這樣的結果：

$ ghc --make -O2 Sum.hs 
$ ./Sum 
warming up 
estimating clock resolution... 
mean is 56.55146 us (10001 iterations) 
found 1136 outliers among 9999 samples (11.4%) 
    235 (2.4%) high mild 
    901 (9.0%) high severe 
estimating cost of a clock call... 
mean is 2.493841 us (38 iterations) 
found 4 outliers among 38 samples (10.5%) 
    2 (5.3%) high mild 
    2 (5.3%) high severe 

benchmarking sumit 
collecting 100 samples, 8 iterations each, in estimated 6.180620 s 
mean: 9.329556 ms, lb 9.222860 ms, ub 9.473564 ms, ci 0.950 
std dev: 628.0294 us, lb 439.1394 us, ub 1.045119 ms, ci 0.950 

所以我想起來了超過900毫秒的平均與標準偏差小於一毫秒。對於更大的測試案例，我得到大約100ms。

啓用優化使用vector包時，因爲它使大量使用流融合，在這種情況下能夠完全消除的數據結構，把你的程序到一個高效，緊湊循環的是特別重要的。

通過使用-fllvm選項來嘗試新的基於LLVM的代碼生成器也是值得的。 It is apparently well-suited for numeric code。

Answer 2

嘗試使用取消裝箱的向量，雖然我不確定它是否會在這種情況下產生明顯的差異。還要注意比較有些不公平，因爲包應該完全優化矢量（這種優化被稱爲流融合）。

Answer 3

你的原始文件，未編譯，然後編譯沒有優化，然後用一個簡單的優化標誌編譯：

$ runhaskell boxed.hs 
3000000 
30000000 
CPU time: 0.35s 

$ ghc --make boxed.hs -o unoptimized 
$ ./unoptimized 
3000000 
30000000 
CPU time: 0.34s 



$ ghc --make -O2 boxed.hs 
$ ./boxed 
3000000 
30000000 
CPU time: 0.09s 

你的文件，而不是import qualified Data.Vector.Unboxed as V的import qualified Data.Vector as V（Int是unboxable型） - 第一沒有優化然後用：

$ ghc --make unboxed.hs -o unoptimized 
$ ./unoptimized 
3000000 
30000000 
CPU time: 0.27s 


$ ghc --make -O2 unboxed.hs 
$ ./unboxed 
3000000 
30000000 
CPU time: 0.04s 

所以，編譯，優化...並在可能情況下使用Data.Vector.Unboxed

Answer 4

如果使用足夠大的矢量，Vector Unboxed可能變得不切實際。對我來說，純（懶惰）名單是更快，如果矢量大小> 5000：

import System.TimeIt 

sumit :: IO() 
sumit = print . sum $ replicate 50000000 10 

main :: IO() 
main = timeIt sumit 

我得到這些時間：

Unboxed Vectors 
CPU time: 1.00s 

List: 
CPU time: 0.70s 

編輯：我已經使用標準，使sumit重複基準純。代碼和結果如下：

代碼：

import Criterion.Main 

sumit :: Int -> Int 
sumit m = sum $ replicate m 10 

main :: IO() 
main = defaultMain [bench "sumit" $ nf sumit 50000000] 

結果：

warming up 
estimating clock resolution... 
mean is 7.248078 us (80001 iterations) 
found 24509 outliers among 79999 samples (30.6%) 
    6044 (7.6%) low severe 
    18465 (23.1%) high severe 
estimating cost of a clock call... 
mean is 68.15917 ns (65 iterations) 
found 7 outliers among 65 samples (10.8%) 
    3 (4.6%) high mild 
    4 (6.2%) high severe 

benchmarking sumit 
collecting 100 samples, 1 iterations each, in estimated 46.07401 s 
mean: 451.0233 ms, lb 450.6641 ms, ub 451.5295 ms, ci 0.950 
std dev: 2.172022 ms, lb 1.674497 ms, ub 2.841110 ms, ci 0.950 

它看起來像print使一個很大的區別，因爲它應該被期待！