GHCの最適化

Question

以下の2つのHaskell関数は、インデックス変数が暗黙的であるか明示的であるかによって異なるように見えますが、パフォーマンスの違いは2桁の違いがあります。

この機能は、MFIB 30を計算するために約0.03秒かかる：

let mfib = (map fib [0..] !!) 
    where 
    fib 0 = 0 
    fib 1 = 1 
    fib x = mfib (x-1) + mfib (x-2) 

この関数は、MFIB 30のために約3秒かかります。

let mfib i = map fib [0..] !! i 
    where 
    fib 0 = 0 
    fib 1 = 1 
    fib x = mfib (x-1) + mfib (x-2) 

私はそれがGHCインラ​​インに関係している推測しています一致するパフォーマンスを得るためにインライン/ノーインラインプラグマを追加しようとしていました。

編集：私は怠惰なリストのルックアップを使ってfib関数をメモすることができ、なぜfibの伝統的な定義が非常に遅いのか理解しています。私はmemoizationが第1の機能と同様に第2の機能でも動作することを期待していたが、なぜそうでないのか理解していない。

Answer 1

desugaredコードを見ると、これらの違いを理解するのが簡単です。そのため、ここでは2つの機能の一部を省略しています。それは（通常、最適化せず）iの各値について評価しますので、第2のプログラムにおいて、式map fib [0..]は、\i -> ...内部に表示されていること

let mfib = \i -> 
       let fib 0 = 0 
        fib 1 = 1 
        fib x = mfib (x-1) + mfib (x-2) 
       in map fib [0..] !! i 

注対

​​3210

。 When is memoization automatic in GHC Haskell?

Answer 2

いいえ、これはインライン展開とは関係ありません。違いはmfib = (map fib [0..] !!)に引数がないことです。これはまだ機能していますが、その機能が何らかの議論をパスする必要はないと評価しています。特に、mfibを評価すると、fibリストがすべてのインデックスに対して再利用できるように生成されます。

OTOH、mfib i = map fib [0..] !! iは、実際には引数iを渡したときにブロックwhere全体が考慮されることを意味します。

2つは、何度も何度も何度も関数を評価する場合にのみ異なります。残念なことに、2番目のバージョンでは、関数自身の再帰呼び出しはすでにそれを何度も繰り返し呼び出しています！したがって、mfib (x-1) + mfib (x-2)は、mfib (x-1)、、そしての全体作業をmfib (x-2)の全体で行う必要があります。だから、mfib nは（2 ^N）mfib∈Oので、mfib (n-1)の2倍以上の計算コストを要します。

mfib (x-2)のほとんどの語句は既にmfib (x-1)にあり、単純に再利用できるため、これは非常に無駄です。最初のバージョンではfibのリストを1回だけ計算し、すべてのインデックスについて計算するので、mfib (x-1)を評価すると、すでに多くの作業が完了しています。つまり、単純にmfib (x-2)で再読み込みできます。