Repa性能与列表

Question

在数字Haskell教程维基中，有一段内容为(用于上下文)：

10.1融合，以及你为什么需要它 Repa依赖于阵列融合来实现快速编码。融合是GHC在编译您的程序时所执行的内联和代码转换组合的一个很好的名称。融合过程将Repa库中定义的数组填充循环与您在自己模块中编写的"worker“函数合并。如果融合过程失败，则生成的程序将比需要的慢得多，通常是使用普通Haskell列表的等效程序慢10倍。另一方面，如果融合有效，则生成的代码将运行得与一个等效的干净编写的C程序一样快。一旦你了解了发生了什么，让核聚变发挥作用并不难。

我不明白的是：

“如果融合过程失败，则生成的程序将比所需的慢很多，通常比使用普通Haskell列表的等效程序慢10倍。”

我理解为什么如果流融合失败，它会运行得更慢，但是为什么它运行的速度比列表慢得多呢？

谢谢!

Answer 1

编辑:这是不对的--参见唐·纳尔逊的评论(以及他的回答--他对图书馆的了解比我多)。

不可变数组不能共享组件；不考虑融合，对不可变数组的任何修改都必须重新分配整个数组。相比之下，虽然列表操作是非破坏性的，但它们可以共享部分:例如，f i (h:t) = i:t通过创建一个新列表来替换列表的头，在该列表中，第一个单元格指向原始列表的第二个单元格。此外，由于列表可以逐步构建，通过重复调用函数构建列表的生成器等函数仍然可以在O(n)时间内运行，而不融合的不变数组上的等效函数将需要在每次调用函数时重新分配数组，占用O(n^2)时间。

Answer 2

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

如果你不能融合一个懒惰的列表遍历，例如。

map f . map g

您需要支付O(1)每个值的成本，以便将中间(惰性) cons单元格留在那里。

如果不能在严格的序列上融合相同的遍历，则为分配严格的中间数组，至少要为每个值支付O(n)。

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