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定义非常慢.我期待memoization在第二个函数以及第一个函数中工作,并且不理解为什么它不是.

1> Reid Barton..：

---

在查看desugared代码时,更容易理解这些差异,因此这里有两个函数的部分脱落版本.

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中何时自动记忆？

2> leftaroundab..：

---

不,这与内联无关.不同之处在于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),从而降低了多项式的复杂性.

---

对_why_的一个额外的解释`where`块被重新评估:这是因为`i`在`where`块的闭包中.如果你把它写成`let mfib =\i - > map fib [0 ..] !! 我在哪里......"它和eta签约的版本一样快.也就是说,我很惊讶GHC没有发现应用完全懒惰转换的机会,并在粘合剂之外浮动`fib`.