GHC优化

Question

下面的两个Haskell函数似乎只是根据索引变量是隐式的还是显式的而有所不同，但性能差异是两个数量级。

此功能需要约0.03秒来计算组播转发表30：

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

此功能需要大约3秒，组播转发表30：

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的传统定义非常缓慢。我期待备忘录在第二个函数中工作，并且不理解为什么它不是。

Answer 1

查看脱毛代码时，更容易理解这些差异，因此这里是两个函数的部分脱毛版本。

​​3210

与

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

注意的是，在第二方案中，表达map fib [0..]出现内部\i -> ...，所以它会（通常，没有优化）为i每个值进行评价。请参阅When is memoization automatic in GHC Haskell?

Answer 2

不，这与内联无关。区别在于mfib = (map fib [0..] !!)没有参数。它当然还是一个函数，但是评估该函数并不需要传递任何参数。特别是，评估这个mfib将生成fib列表，以便它可以重复用于所有索引。

OTOH，mfib i = map fib [0..] !! i表示整个where块只会在您实际传递参数i时才会被考虑。

如果您多次重复评估函数，这两者只会有所不同。不幸的是对于第二个版本，函数自己的递归已经一遍又一遍地调用它！所以mfib (x-1) + mfib (x-2)然后需要做的mfib (x-1),，然后整个工作mfib (x-2)的整个工作。所以mfib n花费的时间比的两倍mfib (n-1)计算成本更高，因此mfib∈ø（2 ^Ñ）。

这非常浪费，因为mfib (x-2)中的大多数条款也已经在mfib (x-1)中，并且可以简单地重新使用。那么，这正是你的第一个版本所做的，因为它计算了所有索引的fib列表，因此评估mfib (x-1)已经完成了大部分工作，然后可以简单地重新读取mfib (x-2)，从而将复杂性降低到多项式。