惹巴性能与列表

Question

在数字哈斯克尔惹巴教程Wiki，有一个通道读取（上下文）：

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

惹巴主要取决于阵列的融合实现快速代码。融合是 GHC执行的内联和代码转换的组合，当 它编译您的程序时，它是一个奇特的名字。融合过程将在Repa库中定义的数组填充 循环与您在自己的模块中编写的“工作”函数合并。如果融合过程失败，那么生成的程序将比需要的慢得多，通常使用普通Haskell列表的等效程序的速度要慢10倍。另一方面，如果提供融合工作，则所产生的代码将运行得如同完全写入的C程序一样快。一旦你了解到底发生了什么，制作融合作品并不难 。

，我不明白的部分是这样的：

“如果这种融合过程中出现故障，那么 产生的程序会比实际需要的要慢得多，经常10倍 的慢等价的程序使用普通的Haskell列表。“

我明白为什么它会运行较慢，如果流融合失败，但为什么它比列表慢得多？

谢谢！

Answer 1

编辑：这是不正确的 - 请参阅Don Nelson的评论（和他的回答 - 他知道更多关于图书馆的信息）。

不可变阵列不能共享组件;无视融合，对不可变数组的任何修改都必须重新分配整个数组。相比之下，虽然列表操作是非破坏性的，但它们可以共享部分：例如，通过创建一个新的列表（其中第一个单元格指向原始列表的第二个单元格），以恒定时间替换列表的头部。此外，因为列表可以逐步构建，所以通过重复调用函数来构建列表的生成器的函数仍然可以在O（n）时间内运行，而不带融合的不可变数组上的等价函数将需要重新分配数组每次调用该函数，需要O（n^2）次。

Answer 2

通常，因为列表是懒惰的，并且Repa数组是严格的。

如果您无法融合懒惰列表遍历，例如

map f . map g 

你付出O（1）每值成本留下中间（懒惰）cons单元存在。

如果您未按照严格的顺序对相同的遍历进行融合，您至少需要支付每个值O（n）以分配严格的中间数组。另外，由于融合将你的代码压缩到一个无法识别的数据类型Stream中，为了改善分析，你可以留下代码，这些代码只有太多的构造函数和其他开销。