ハスケルの効率的な数値計算

Question

ハスケルで提案した（ベクトルから数百万の数を合計した）問題を見て、彼の結果と比較するために、この投稿に触発されました。

私はハスケル初心者ですので、正しく時間を設定する方法やこれを効率的に行う方法がわかりません。この問題の最初の試みは次のとおりです。私は良い方法でやり方がわからないので、私はベクトルに乱数を使用していないことに注意してください。私は完全な評価を確実にするために物を印刷しています。

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を実行しているが、それは300万番号3000万の番号の2.69sのために実行するのに約0.22sを取ったことを私に伝えます。

Lushの0.02秒と0.18秒のブログ作成者の結果と比較すると、これはかなり悪くなります。これは、これがより良い方法で実行できると信じています。

注：上記のコードでは、実行するにはTimeItパッケージが必要です。 cabal install timeitが手に入れます。

Answer 1

まず、GHCiは通訳者であり、非常に高速に設計されているわけではありません。より有用な結果を得るには、最適化を有効にしてコードをコンパイルする必要があります。これは大きな違いを生み出すことができます。

また、深刻なHaskellコードのベンチマークでは、criterionを使用することをお勧めします。これは、信頼性の高い測定を確実にするために、さまざまな統計的手法を使用します。

基準を使用するようにコードを修正し、I/Oタイミングを調整しないように印刷ステートメントを削除しました。 -O2でこれをコンパイルする

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] 

、私はかなり遅いネットブック上で、この結果を得る：

$ 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 

だから私は、ミリ秒未満の標準偏差がわずか9ミリの平均を取得しています。大規模なテストケースでは、私は約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は非実用的になる可能性があります。私にとっては、純粋な（遅延）リストは、迅速であるかのベクトルの大きさ> 50000000：

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] 

結果：それは予想されるべきであるprintは、大きな違いを作るよう

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 

に見えます！