如何以不需要比产生的收益更多的开销的方式实现惰性评估?



我知道有些地方的惰性求值会阻止需要计算。例如,将两个数字相加,然后将它们传递到最终永远不会使用的函数参数中。

但在我看来,存储和加载稍后要使用的操作会产生大量开销,并且这些开销通常会抵消任何收益。

有人可以解决这个问题吗?

你是对的。 惰性评估确实会产生很大的开销,大多数情况下,您不会从中获得实际的性能提升。 惰性求值的主要原因是它很方便——它使 Haskell 的语言语义更清晰,并且(例如)惰性/无限列表有时对程序员来说很方便。

幸运的是,编译器通常可以在内部循环之外优化惰性机制,否则朴素的实现会导致严重的性能损失。

出乎意料的是,事实证明,GHC 的延迟计算实现并没有在类似的严格运行时系统上引入明显的开销。 为惰性计算创建一个混乱(即"存储"稍后使用的操作)并最终强制其评估(即"加载"它)的明显"开销"取代了创建堆栈帧、调用函数和返回的严格评估"开销"。 因此,函数调用的成本会及时转移,但不会显着增加。

的确,严格性(由程序员显式引入或由编译器自动识别)有时对于良好的性能是必要的,但这通常是因为严格性允许拆箱和相关优化,或者在某些情况下,避免代价高昂的内存泄漏,从而导致过多的垃圾收集开销。 惰性评估本身并不比严格评估成本高得多。

在这个答案中,我提供了GHC RTS中的函数调用和典型的Java VM实现的详细比较。 这个答案集中在内存使用上(因为问题是关于垃圾回收的),但大部分讨论都适用于更普遍的性能。

总结相关位,如果您尝试确定调用函数以乘以两个数字的开销:

bar :: Int -> Int -> Int
bar a b = a * b

由其他一些函数调用:

foo :: Int -> Int -> Int -> Int
foo x y z = let u = bar y z in x + u

那么在典型的严格实现中,比如Java JVM,字节码可能看起来像这样:

public static int bar(int, int);
Code:
stack=2, locals=2, args_size=2
0: iload_0   // push a
1: iload_1   // push b
2: imul      // multiply and push result
3: ireturn   // pop result and return it
public static int foo(int, int, int);
Code:
stack=2, locals=4, args_size=3
0: iload_1   // push y
1: iload_2   // push z
2: invokestatic bar   // call bar, pushing result
5: istore_3  // pop and save to "u"
6: iload_0   // push x
7: iload_3   // push u
8: iadd      // add and push result
9: ireturn   // pop result and return it

bar函数调用的开销(即,上述函数调用与bar是否内联之间的差异)看起来像是两个参数推送、调用本身和返回。

对于惰性版本,GHC(无优化)将此代码编译为类似于以下伪代码的内容:

foo [x, y, z] =
u = new THUNK(sat_u)                   // thunk, 32 bytes on heap
jump: (+) x u
sat_u [] =                                 // saturated closure for "bar y z"
push UPDATE(sat_u)                     // update frame, 16 bytes on stack
jump: bar y z
bar [a, b] =
jump: (*) a b

惰性bar函数调用的开销是在凹凸堆上创建一个 thunk(与堆栈一样快),其中包括两个参数和一个指向sat_u的指针(加上返回值的空间,尽管没有"成本"),以及当(+)函数通过跳转到sat_u强制值u时,"调用"(在上面的代码中不可见)。 更新帧或多或少地替换了返回帧。 (在这种情况下,可以对其进行优化。

最重要的是,至少在第一近似值中,GHC中实现的惰性评估与严格评估大致一样快,即使实际评估了所有内容。

它之所以有效,是因为编译器优化会在不必要的情况下尝试删除懒惰。

如果它看到下一次计算将消耗先前计算的结果,它只会生成代码严格代码。

由于Haskell是纯粹的语言,懒惰的评估起着重要作用。这不仅仅是语言的一个功能,它允许程序员以声明性风格编写,而不必担心计算顺序。

让我们举个例子。

`sum $ map (^2) [0..100]`

在严格的语义中会发生什么。首先计算map函数。它将使用整个输入列表并生成(分配,因为Haskell是纯的)输出列表。然后sum将计算结果。

但在惰性语义中,不会构造此示例中的中间列表。因此,不会有不必要的内存工作。意味着垃圾回收器的工作量更少。

因此,对于纯语言,惰性语义是避免构造中间对象的开销的一种方法。

相关内容

最新更新