5

大規模なデータ セットを取得し、それにさまざまな操作を適用するように設計されたライブラリを最適化しようとしています。ライブラリが機能するようになったので、最適化したいと思います。

非厳密な評価により、GHC は操作を組み合わせて、whnf 削減を容易にするために引数が順序付けられるように、すべての関数が記述されたときにデータが 1 回だけ反復されるようになるという印象を受けています。(そして、各データムで実行される操作の数を減らす可能性があります)

これをテストするために、次のコードを書きました。

import Criterion.Main

main = defaultMain
       [ bench "warmup (whnf)" $ whnf putStrLn "HelloWorld",
         bench "single (whnf)" $ whnf single [1..10000000],
         bench "single (nf)"   $ nf   single [1..10000000],
         bench "double (whnf)" $ whnf double [1..10000000],
         bench "double (nf)"   $ nf   double [1..10000000]]

single :: [Int] -> [Int]
single lst = fmap (* 2) lst

double :: [Int] -> [Int]             
double lst =  fmap (* 3) $ fmap (* 2) lst

Criterion ライブラリを使用したベンチマークでは、次の結果が得られます。

benchmarking warmup (whnf)
mean: 13.72408 ns, lb 13.63687 ns, ub 13.81438 ns, ci 0.950
std dev: 455.7039 ps, lb 409.6489 ps, ub 510.8538 ps, ci 0.950

benchmarking single (whnf)
mean: 15.88809 ns, lb 15.79157 ns, ub 15.99774 ns, ci 0.950
std dev: 527.8374 ps, lb 458.6027 ps, ub 644.3497 ps, ci 0.950

benchmarking single (nf)
collecting 100 samples, 1 iterations each, in estimated 107.0255 s
mean: 195.4457 ms, lb 195.0313 ms, ub 195.9297 ms, ci 0.950
std dev: 2.299726 ms, lb 2.006414 ms, ub 2.681129 ms, ci 0.950

benchmarking double (whnf)
mean: 15.24267 ns, lb 15.17950 ns, ub 15.33299 ns, ci 0.950
std dev: 384.3045 ps, lb 288.1722 ps, ub 507.9676 ps, ci 0.950

benchmarking double (nf)
collecting 100 samples, 1 iterations each, in estimated 20.56069 s
mean: 205.3217 ms, lb 204.9625 ms, ub 205.8897 ms, ci 0.950
std dev: 2.256761 ms, lb 1.590083 ms, ub 3.324734 ms, ci 0.950

リストが（* 6）によって一度だけ操作されるように、GHCは「ダブル」機能を最適化しますか？nf の結果は、そうでなければ「double」の平均計算時間が「single」の 2 倍になるため、これが当てはまることを示しています。

whnf バージョンの実行速度が非常に速い理由は何ですか? 実際には何も実行されていないと想定することしかできません (または削減の最初の反復のみ)

正しい用語を使用していますか?

4

1 に答える 1

4

オプションを使用して GHC によって生成されたコア (中間コード) を見ると、-ddump-simplGHC が実際に の 2 つのアプリケーションmapを 1 つに融合していることを確認できます ( を使用-O2)。ダンプの関連部分は次のとおりです。

Main.main10 :: GHC.Types.Int -> GHC.Types.Int
GblId
[Arity 1
 NoCafRefs]
Main.main10 =
  \ (x_a1Ru :: GHC.Types.Int) ->
    case x_a1Ru of _ { GHC.Types.I# x1_a1vc ->
    GHC.Types.I# (GHC.Prim.*# (GHC.Prim.+# x1_a1vc 2) 3)
    }

Main.double :: [GHC.Types.Int] -> [GHC.Types.Int]
GblId
[Arity 1
 NoCafRefs
 Str: DmdType S]
Main.double =
  \ (lst_a1gF :: [GHC.Types.Int]) ->
    GHC.Base.map @ GHC.Types.Int @ GHC.Types.Int Main.main10 lst_a1gF

GHC.Base.mapinの使用方法が 1 つしかないことに注意してください。これは、2 を加算して 3 を乗算するMain.double結合関数を参照しています。これは、GHC が最初にリストのインスタンスをインライン展開して になり、次に2 を許可する書き換え規則を適用した結果である可能性があります。融合するアプリケーションに加えて、さらにインライン化やその他の最適化を行います。Main.main10Functorfmapmapmap

WHNF は、式が「最も外側の」データ コンストラクターまたはラムダに対してのみ評価されることを意味します。この場合、それは最初の(:)コンストラクターを意味します。ほとんど作業が行われていないため、これが非常に高速な理由です。What is Weak Head Normal Form?に対する私の回答を参照してください。詳細については。

于 2011-10-20T04:33:14.750 に答える