在Haskell中考虑性能问题

Question

以下两个Haskell程序用于计算斐波那契数列的第n项，它们具有明显不同的性能特征：

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中你无需考虑语言的性能，而更应该关注编译器的优化，这似乎比我熟悉的任何其他语言都更重要。 我倾向于说编译器的重要性是区分推理懒惰的函数式语言的性能与推理任何其他类型的性能的因素。此外，任何看到此问题的人可能希望查看Johan Tibell的高性能Haskell演讲幻灯片。

- Aidan Cully

Answer 1

在你的斐波那契数列示例中，很容易看出第二个算法为什么应该运行得更快（尽管你没有指定f2是什么）。

这主要是一个算法问题：

- fib1实现了纯递归算法，（就我所知）Haskell没有“隐式记忆化”的机制。 - fib2使用显式记忆化（使用fibArr列表存储先前计算过的值）。

一般来说，对于像Haskell这样的惰性语言，很难做出性能假设，而对于急切语言则更容易。然而，如果您理解底层机制（特别是惰性）并积累一些经验，则可以对性能进行一些“预测”。

引用透明度在（至少）两个方面上增加了潜在的性能：

- 首先，作为程序员，您可以确信对同一函数的两次调用将始终返回相同的结果，因此您可以在各种情况下利用此功能以获得性能优势。 - 其次（更重要的是），Haskell编译器可以确定上述事实，这可能使许多无法在不纯语言中启用的优化变得可行（如果您曾经编写过编译器或具有任何编译器优化经验，则可能已经意识到这一点的重要性）。

如果您想阅读有关Haskell设计选择（惰性、纯度）背后的原因的更多信息，我建议阅读this。

- 3lectrologos

---

f2这个问题是一个bug - 我使用了一台没有安装Haskell的不同电脑来输入问题，给错误留下了空间。 - Aidan Cully

我想这在书中已经有所涉及，但是我认为Haskell或任何纯函数式语言可能具有隐式记忆化。作为编译器编写者，困难的部分在于知道何时使用它。 - Dan

在像Haskell这样的编译语言中，使用动态优化技术非常困难（始终记忆结果显然不是一个选项），因为通常在编译时没有足够的信息（这也是虚拟机流行的原因之一，它们使用动态分析）。 - 3lectrologos

Haskell 可能因编译器提供的广泛优化和悲观化而“特殊”，但这个教训适用于所有编程语言。 - ephemient

列表不是“记忆化”的，它们只是数据结构，因此如果您共享它们（给它们命名），当然它们不会被计算两次。问题只有在您有像 let f x = .... in f 15 + f 15 这样的东西时才会出现。由于您没有给 f 15 命名，它会被计算两次还是一次？答案是“取决于情况”和“可能会计算两次”，因为 GHC 可以检测到这种重复，但它通常无法估计共享结果是否是一个好主意，因为有些情况下这是一个非常糟糕的主意，甚至会将程序从 O(1) 的空间使用更改为 O(n)！ - Jedai

Answer 2

在Haskell和其他惰性语言中，通常很难推断性能，但并非不可能。一些技术在Chris Okasaki的Purely Function Data Structures中有所涉及（之前版本也可以在线阅读）。

确保性能的另一种方法是通过注释或延续传递风格来固定评估顺序。这样，您就可以控制何时评估事物。

在您的示例中，您可以“自下而上”计算数字，并将前两个数字传递给每次迭代：

fib n = fib_iter(1,1,n)
    where
      fib_iter(a,b,0) = a
      fib_iter(a,b,1) = a
      fib_iter(a,b,n) = fib_iter(a+b,a,n-1)

这导致了一种线性时间算法。

每当您使用动态规划算法时，每个结果都依赖于前N个结果，您可以使用此技术。否则，您可能需要使用数组或完全不同的东西。

- Jørgen Fogh

---

fib_iter(1,1,n) 翻译成中文为 fib_iter 1 1 n （我猜使用额外的元组操作也可以实现，但这样做没有意义，而且不符合惯用写法）。 - Michał Marczyk

我一直打算读Okasaki的书。我不知道a)那是他的论文，b)它在网上。它看起来很有前途（“分摊的概念也提供了分析非平凡惰性程序时间要求的第一批实用技术”）。谢谢！ - Aidan Cully

@MichałMarczyk 不是无意义的。实际上，Richard Bird建议（关于“partition”函数效率的某个地方，但我不记得具体在哪里了，抱歉）将所有时间同步的参数打包成元组（我的措辞），即在同一时间计算，作为一个状态的一部分，特别是用于Bang Patterns。单独的参数可以在不同的时间进行规定，即函数可以被柯里化。这会影响代码的编译方式。 - Will Ness

Answer 3

您的fib2实现使用了记忆化技术，但每次调用fib2时都会重新构建整个结果。请打开ghci时间和大小分析功能：

Prelude> :set +s

如果进行备忘录技术来优化调用，后续的调用将会更快且不占用额外内存。您可以试着连续调用20000次fib2函数，体验效果。

相比之下，为确保数学公式的精准性而编写的代码更为常见：

-- the infinite list of all fibs numbers.
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

memoFib n = fibs !! n

实际上确实使用了备忘录，就像您所看到的那样明确。如果您两次运行memoFib 20000，则会看到第一次需要时间和空间，然后第二次调用立即完成且不占用内存。没有魔法，也没有隐含的备忘录，就像注释可能暗示的那样。

现在关于您最初的问题：如何优化并理解Haskell的性能...

我不认为自己是Haskell方面的专家，我只使用它3年，其中有2年在我的工作场所，但我确实必须优化并了解如何相对地推理性能。

如其他帖子中提到的那样，惰性是您的朋友，并且可以帮助您获得更好的性能，但是您必须控制什么是惰性评估和什么是严格评估。

请查看foldl与foldr的比较

foldl实际上存储了计算值的“方式”，即它是惰性的。在某些情况下，您可以通过采用惰性方式来节省时间和空间，例如采用“无限”斐波那契数列。这个无限的“斐波那契”数列并不生成所有数字，但知道如何生成这些数字。当您知道需要该值时，最好是严格地获取它...这就是严格性注释的用途，以使您重新获得控制。

我记得很多次都说过，在Lisp中，您必须“最小化”构造新列表。

了解哪些是严格评估以及如何强制执行它非常重要，但对内存产生的“垃圾”量也同样重要。请记住，Haskell是不可变的，这意味着更新一个“变量”实际上是创建具有修改的副本。与（++）相比，以（:)开头的前置更加高效，因为（:)不会复制内存。每当更新大的原子块（即使只有一个字符）时，整个块都需要被复制以表示“更新后的”版本。您构造数据并对其进行更新的方式可能会对性能产生很大影响。 GHC分析器是您的朋友，将帮助您发现这些问题。当然，垃圾收集器很快，但是让它不做任何事情会更快！

干杯

- JFT

Answer 4

除了备忘录问题外，fib1还使用了非尾调用递归。尾调用递归可以自动重构为简单的goto并且性能很好，但是fib1中的递归不能以这种方式进行优化，因为您需要来自每个fib1实例的堆栈帧才能计算结果。如果将fib1重写为传递运行总数作为参数，从而允许尾调用而不需要保留堆栈帧进行最终添加，则性能将大大提高。但当然不如备忘录示例那么快 :)

- Justin Smith

Answer 5

由于在任何函数式语言中，分配都是主要成本，因此了解性能的重要部分是了解对象何时分配、存活多长时间、何时死亡以及何时被回收。为了获得这些信息，您需要一个堆分析器。它是一种必不可少的工具，幸运的是 GHC 配备了一个很好的工具。

有关更多信息，请阅读Colin Runciman的论文。

- Norman Ramsey