GHC优化

Question

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

此函数计算 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 内联规则有关，并且一直在尝试添加 inline/noinline 编译指示以获得匹配的性能。

编辑：我了解如何使用惰性列表查找来记忆 fib 函数，以及为什么 fib 的传统定义非常慢。我期待记忆化在第二个功能和第一个功能中工作，但不明白为什么不行。

Answer 1

不，这与内联无关。区别在于 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 ∈ O (2ⁿ).

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

Answer 2

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

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 的每个值。参见 When is memoization automatic in GHC Haskell?

GHC优化

GHC optimization

optimization

haskell

ghc