关于Haskell性能的推理

Question

以下两个用于计算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的性能有贡献？我怎么能提前知道它是否会？

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

---

简介: 我接受3lectrologos的答案,因为关于语言的性能,关于编译器的优化,你没有那么多理由这一点似乎在Haskell中非常重要 - 比我熟悉的任何其他语言更重要用.我倾向于说编译器的重要性是区分懒惰,功能语言中的性能推理的因素,而不是任何其他类型的性能推理.

---

附录:任何人都发生在这个问题上可能想看看幻灯片从约翰Tibell的谈高性能哈斯克尔.

Answer 1

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

它主要是一个算法问题:

• fib1实现了纯粹的递归算法(据我所知)Haskell没有"隐式记忆"的机制.
• fib2使用显式memoization(使用fibArr列表存储以前计算的值.

一般来说,对于像Haskell这样的惰性语言而言,要比那些热切的语言做出性能假设要困难得多.然而,如果您了解潜在的机制(特别是懒惰)并收集一些经验,您将能够对性能做出一些"预测".

参考透明度(至少)以两种方式增加(潜在)性能:

• 首先,您(作为程序员)可以确保对同一函数的两次调用始终返回相同,因此您可以在各种情况下利用它来获得性能.
• 第二个(也是更重要的),Haskell编译器可以确定上述事实,这可能会启用许多无法在不纯的语言中启用的优化(如果您曾编写过编译器或者在编译器优化方面有任何经验,那么可能意识到这个的重要性).

如果你想更多地了解Haskell的设计选择背后的原因(懒惰,纯粹),我建议你阅读这篇文章.

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个结果,您就可以使用此技术.否则,您可能必须使用数组或完全不同的内容.

Answer 3

你的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与foldr的比较

foldl actually stores "how" to compute the value i.e. it is lazy. In some case you saves time and space beeing lazy, like the "infinite" fibs. The infinite "fibs" doesn't generate all of them but knows how. When you know you will need the value you might as well just get it "strictly" speaking... That's where strictness annotation are usefull, to give you back control.

I recall reading many times that in lisp you have to "minimize" consing.

Understanding what is stricly evaluated and how to force it is important but so is understanding how much "trashing" you do to the memory. Remember Haskell is immutable, that means that updating a "variable" is actually creating a copy with the modification. Prepending with (:) is vastly more efficient than appending with (++) because (:) does not copy memory contrarily to (++). Whenever a big atomic block is updated (even for a single char) the whole block needs to be copied to represent the "updated" version. The way you structure data and update it can have a big impact on performance. The ghc profiler is your friend and will help you spot these. Sure the garbage collector is fast but not having it do anything is faster!

Cheers