performance - "Call by name"会减慢 Haskell 的速度吗?

标签 performance haskell implementation callbyname

我认为它不会。

我的理由是 Haskell 是纯函数式编程(没有 I/O Monad),如果“名称”相同,他们本可以让每个“按名称调用”使用相同的评估值。

我对实现细节一无所知,但我真的很感兴趣。
详细解释将不胜感激:)

顺便说一句,我试过谷歌,很难找到有用的东西。

最佳答案

首先,Haskell是一个规范,而不是一个实现;该报告实际上并不需要使用按名称调用评估,或就此进行惰性评估。 Haskell 实现只需要是非严格的,这确实排除了按值调用和类似策略。

所以,严格来说(哈哈),求值策略不会减慢 Haskell 的速度。我不确定是什么可以减慢 Haskell 的速度,尽管显然有些东西已经减慢了 Haskell 的速度,否则它不会花费 12 年的时间才能在 Haskell 98 之后发布下一版本的报告。我的猜测是以某种方式涉及委员会。


总之,“惰性求值”指的是一种“按需调用”的策略,这是Haskell最常见的实现选择。这与 call-by-name 的不同之处在于,如果一个子表达式在多个地方使用,它最多被计算一次。

关于什么可以作为共享的子表达式的细节有点微妙,可能有点依赖于实现,但是使用 GHC Haskell 的例子:考虑函数 cycle,它重复一个无限输入列表。一个简单的实现可能是:

cycle xs = xs ++ cycle xs

这最终导致效率低下,因为没有可以共享的单个 cycle xs 表达式,因此结果列表必须在遍历时不断构建,每次分配更多内存并进行更多计算.

相比之下,actual implementation看起来像这样:

cycle xs = xs' where xs' = xs ++ xs'

这里名称 xs' 被递归定义为附加到输入列表的末尾。这次 xs' 是共享的,并且只计算一次;生成的无限列表实际上是内存中的有限循环链表,一旦整个循环被评估,就不需要进一步的工作。


一般来说,GHC 不会为你memoize 函数:给定fx,每次使用f x 将被重新评估,除非您为结果命名并使用它。在这两种情况下,结果值都相同,但性能可能会有很大差异。这主要是为了避免悲观化——GHC 很容易为您内存事物,但在许多情况下,这将花费大量内存来获得微小或根本不存在的速度。

不利的一面是,共享的值(value)观得以保留;如果您有一个计算成本非常高的数据结构,命名构造它的结果并将其传递给使用它的函数可确保没有重复的工作——即使它被不同的线程同时使用。

您也可以用这种方式自己悲观——如果一个数据结构的计算成本低且使用大量内存,您可能应该避免共享对完整结构的引用,因为这将使整个事情都活在内存中,只要以后有可能用到它。

关于performance - "Call by name"会减慢 Haskell 的速度吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14001541/

相关文章:

Haskell 与 ContT、callCC 的混淆,当

algorithm - 压缩/加密算法输出保证

.net - 正则表达式的多线程使用

javascript - 在 angular6 模板中使用 getter 方法或类变量?

javascript - iOS 浏览器上的 Webkit 滚动性能

haskell - 变量不在嵌套 where 的范围内

database - IMDB(内存数据库)与 Java 集合

haskell - 模拟全局变量

c - 是否可以使用泛型而不是仅使用整数在 C 中实现 StackADT?

java - java类的类图的实现