修复绩效与列表

Question

在Numeric Haskell Repa Tutorial Wiki中,有一段读取(用于上下文):

10.1融合,以及为什么需要它

修复主要取决于阵列融合以实现快速编码.Fusion是编译程序时GHC执行的内联和代码转换组合的一个奇特名称.融合过程将Repa库中定义的数组填充循环与您在自己的模块中编写的"worker"函数合并.如果融合过程失败,那么生成的程序将比它需要的慢得多,通常比使用普通Haskell列表的等效程序慢10倍.另一方面,如果提供融合工作,生成的代码将与等效的干净编写的C程序一样快.一旦了解了正在发生的事情,融合工作并不难.

我不明白的部分是:

"如果融合过程失败,那么生成的程序将比它需要的速度慢得多,通常比使用普通Haskell列表的等效程序慢10倍."

我理解为什么如果流融合失败会运行得慢,但为什么它比列表运行慢得多呢？

谢谢!

Answer 1

通常,因为列表是惰性的,并且Repa数组是严格的.

如果你没有融合懒惰列表遍历,例如

map f . map g

你需要支付O(1)每个值的成本,以便在那里留下中间(懒惰)cons单元格.

如果您未能通过严格的序列融合相同的遍历,则每个值至少支付O(n)来分配严格的中间数组.

此外,由于融合将您的代码破坏为无法识别的Stream数据类型,为了改进分析,您可能会留下具有太多构造函数和其他开销的代码.