performance - 推理 Haskell 的性能

Question

以下两个用于计算斐波那契数列第 n 项的 Haskell 程序具有截然不同的性能特征:

fib1 n =
  case n of
    0 -> 1
    1 -> 1
    x -> (fib1 (x-1)) + (fib1 (x-2))

fib2 n = fibArr !! n where
  fibArr = 1:1:[a + b | (a, b) <- zip fibArr (tail fibArr)]

它们在数学上非常接近，但 fib2使用列表符号来内存其中间结果，而 fib1具有显式递归。尽管中间结果可能缓存在 fib1 中，即使对于 fib1 25，执行时间也会成为问题。 ，表明递归步骤总是被评估。引用透明度对 Haskell 的性能有什么贡献吗？我怎么能提前知道它会或不会呢？

这只是我担心的那种事情的一个例子。我想听听关于克服推理延迟执行的函数式编程语言的性能所固有的困难的任何想法。

摘要:我接受了 3lectrologos 的回答，因为在 Haskell 中，您对语言的性能以及编译器的优化没有过多的推理，这点似乎比我熟悉的任何其他语言都重要。我倾向于说，编译器的重要性是将惰性、函数式语言的性能推理与任何其他类型的性能推理区分开来的因素。

附录:遇到此问题的任何人都可能想查看 the slides来自 Johan Tibell的 talk about high performance Haskell .

Answer 1

在您的特定斐波那契示例中，不难看出为什么第二个应该运行得更快(尽管您没有指定 f2 是什么)。

主要是算法问题:

fib1 实现了纯递归算法，并且(据我所知)Haskell 没有“隐式内存”机制。

fib2 使用显式内存(使用 fibArr 列表存储先前计算的值。

一般来说，对像 Haskell 这样的惰性语言做出性能假设要比对渴望的语言做出性能假设要困难得多。不过，如果您了解 底层机制 (尤其是为了懒惰)并收集一些 经验 ，您将能够对性能做出一些“预测”。

引用透明度 以(至少)两种方式(至少)提高(潜在)性能:

首先，您(作为程序员)可以确保对同一个函数的两次调用将始终返回相同的结果，因此您可以在各种情况下利用这一点来提高性能。

其次(也是更重要的)，Haskell 编译器可以确定上述事实，这可能会启用许多在不纯语言中无法启用的优化(如果您曾经编写过编译器或在编译器优化方面有任何经验，那么您就是可能意识到这一点的重要性)。

如果您想了解更多有关 Haskell 设计选择(懒惰、纯粹)背后的原因，我建议您阅读 this .