haskell - Repa 性能与列表

Question

在数值 Haskell Repa 教程中 Wiki ，有一段文字如下(用于上下文):

10.1 Fusion, and why you need it

Repa depends critically on array fusion to achieve fast code. Fusion is a fancy name for thecombination of inlining and code transformations performed by GHC whenit compiles your program. The fusion process merges the array fillingloops defined in the Repa library, with the "worker" functions thatyou write in your own module. If the fusion process fails, then theresulting program will be much slower than it needs to be, often 10xslower an equivalent program using plain Haskell lists. On the otherhand, provided fusion works, the resulting code will run as fast as anequivalent cleanly written C program. Making fusion work is not hardonce you understand what's going on.

我不明白的部分是:

"If the fusion process fails, then theresulting program will be much slower than it needs to be, often 10xslower an equivalent program using plain Haskell lists."

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

谢谢!

Answer 1

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

如果你未能融合惰性列表遍历，例如

map f . map g

将中间(惰性)cons 单元留在那里，您将为每个值支付 O(1) 成本。

如果您无法在严格序列上融合相同的遍历，则为分配严格的中间数组，每个值至少要花费O(n)。

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