GHC优化

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

此功能需要大约0.03秒来计算mfib 30：

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

---

在查看代码时，理解这些差异会更容易，所以这里是两个函数的部分解除版本。

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

与

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每个值进行评估。 在GHC Haskell中查看何时自动记忆？

---

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

OTOH， mfib i = map fib [0..] !! i mfib i = map fib [0..] !! i意味着当你实际上通过一个论点i时，整个where区块才会被考虑。

如果你一次又一次地评估一个函数多次，这两者只会有所不同。 不幸的是对于第二个版本，函数自己的递归已经一遍又一遍地调用它！ 所以mfib (x-1) + mfib (x-2)需要完成mfib (x-1)的整个工作，然后再做mfib (x-2)的整个工作。 所以mfib n需要两倍于mfib (n-1)的计算成本，因此mfib （2n）。

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

链接地址: http://www.djcxy.com/p/7475.html

上一篇: GHC optimization

下一篇: How can I get at the cleverest optimizations that GHC makes?