关于Haskell性能的推理-Java 学习之路

以下两个用于计算Fibonacci序列第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 's performance? How can I know ahead of time if it will or won' t有贡献？

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

Summary: 我'm accepting 3lectrologos'的答案，因为你要表现得很好，至于你熟悉的编译器's optimization, seems to be extremely important in Haskell - more so than in any other language I' . 我倾向于说编译器的重要性是区分懒惰，功能语言中的性能推理的因素，而不是任何其他类型的性能推理 .

Addendum: 在这个问题上发生的任何人都可以查看Johan Tibell的talk about high performance Haskell中的the slides .

5 回答

11
在你特定的Fibonacci例子中，不难看出为什么第二个应该运行得更快（尽管你没有指定f2是什么） .

它主要是一个算法问题：
- fib1 实现了纯粹的递归算法（据我所知）Haskell没有"implicit memoization"的机制 .
- fib2 使用显式memoization（使用fibArr列表存储以前计算的值 .
一般来说，对于像Haskell这样的惰性语言而言，要比那些热切的语言做出性能假设要困难得多 . 尽管如此，如果你理解 underlying mechanisms （尤其是懒惰）并收集一些 experience ，你将能够做出一些关于性能的"predictions" .

Referential transparency 以（至少）两种方式增加（潜在）性能：
- 首先，您（作为程序员）可以确保对同一函数的两次调用始终返回相同，因此您可以在各种情况下利用它来提高性能 .
- 第二个（也是更重要的），Haskell编译器可以确定上述事实，这可以启用许多优化，这些优化可以编写编译器或者在编译器优化方面有任何经验，您可能已经意识到这一点的重要性） .
如果你想了解更多关于Haskell的设计选择（懒惰，纯粹）背后的原因，我建议阅读this .
回复于 2024-04-27T11:59:03+08:00
6
在Haskell和懒惰语言中，关于性能的推理通常很难，尽管并非不可能 . Chris Okasaki的Purely Function Data Structures（在之前的版本中也可用online）中介绍了一些技巧 .

确保性能的另一种方法是使用注释或continuation passing style来修复评估顺序 . 这样你就可以控制什么时候进行评估 .

在您的示例中，您可以计算“自下而上”的数字，并将前两个数字传递给每次迭代：
```
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个结果，您就可以使用此技术 . 否则，您可能必须使用数组或完全不同的内容 .
回复于 2024-04-27T11:59:03+08:00
5
你的fib2实现使用memoization，但每次调用fib2时它都会重建“整体”结果 . 打开ghci时间和大小分析：
```
Prelude> :set +s
```
如果它在“之间”调用进行记忆，则后续调用将更快并且不使用内存 . 两次调用fib2 20000并亲自看看 .

通过比较一个更惯用的版本，您可以在其中定义确切的数学标识：
```
-- the infinite list of all fibs numbers.
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

memoFib n = fibs !! n
```
实际上确实使用了memoisation，如你所见，显式 . 如果你运行memoFib 20000两次，你将看到第一次采取的时间和空间，然后第二次调用是瞬时的，不占用内存 . 没有任何魔法，也没有像评论那样隐含的记忆可能暗示过 .

现在谈谈你原来的问题：优化和推理Haskell中的性能......

我不会称自己是Haskell的专家，我只使用它3年，其中2个在我的工作场所，但我确实必须优化并理解如何在某种程度上推断其性能 .

正如其他帖子中提到的那样懒惰是你的朋友，可以帮助你获得表现，但是你必须控制懒惰的评价和严格评价的内容 .

检查foldl vs foldr的比较

foldl实际上存储了“如何”来计算该值，即它是懒惰的 . 在某些情况下，你可以节省时间和空间，就像“无限”的纤维一样 . 无限的“纤维”不会产生所有这些但是知道如何 . 当你知道你需要 Value 时，你也可以“严格地”说出来......这就是严格注释有用的地方，让你重新掌控 .

我记得曾多次读过，在口齿不清中，你必须“尽量减少” .

理解什么是严格评估以及如何强制它是很重要的，但理解你对记忆的作用是多少 . 记住Haskell是不可变的，这意味着更新"variable"实际上是在创建一个带有修改的副本 . 前缀为（:)比附加（）更有效，因为（:)不会将内存复制到（） . 每当更新一个大的 atomic 块时（即使是单个字符），需要复制整个块以表示"updated"版本 . 构建数据和更新数据的方式会对性能产生很大影响 . ghc profiler是你的朋友，可以帮助你发现这些 . 当然垃圾收集器很快但没有做任何事情更快！

干杯
回复于 2024-04-27T11:59:03+08:00
1

除了memoization问题，fib1还使用非tailcall递归 . Tailcall递归可以自动重新计算到一个简单的goto中并且执行得很好，但是fib1中的递归不能以这种方式优化，因为你需要来自fib1的每个实例的堆栈帧以便计算结果 . 如果你重写了fib1以传递一个运行总数作为参数，从而允许尾调用而不是需要保留最后添加的堆栈帧，性能将会极大地提高 . 但不像备忘的例子那么多，当然:)

回复于 2024-04-27T11:59:03+08:00
2

由于分配是任何功能语言的主要成本，理解性能的一个重要部分是了解何时分配对象，它们存活多长时间，何时死亡以及何时被回收 . 要获取此信息，您需要 heap profiler . 这是一个必不可少的工具，幸运的是GHC配备了一个很好的工具 .

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

回复于 2024-04-27T11:59:03+08:00

关于Haskell性能的推理

5 回答

相关问题