haskell - 管道管道的执行时间很奇怪

Question

我正在测试这个递归 Haskell 函数的性能，它重复地对无限列表的前 100000000 个整数求和(使用 Conduit 管道)并打印每次执行的耗时:

import Conduit
import Data.Time.Clock

evaluate_listC 0 = return ()
evaluate_listC i = do
    startTime <- getCurrentTime
    print $ runConduitPure $ yieldMany [1..] .| takeC 100000000 .| sumC
    endTime <- getCurrentTime
    print $ diffUTCTime endTime startTime
    evaluate_listC (i-1)

编译(使用 -O 标志)并运行代码，并迭代函数 10 次，我获得以下执行时间:

38.2066878s
4.3696857s
1.3367605s
0.9950032s
0.9399968s
0.9039936s
0.9079987s
0.9119587s
0.9090151s
0.8749654s

为什么第一次迭代(以及第二次)需要更多时间，而接下来的迭代速度快得难以置信？

Answer 1

正如我在评论中提到的，我无法复制这些缓慢的性能数字，但我很确定我知道发生了什么。如果您提供一些额外的细节，让我可以复制问题，我可以更新答案。

最有可能的列表 [1..] (或者可能是涉及此列表的一些更大的表达式)作为常量应用形式(CAF)被“提升”到顶级。由于列表是在第一次迭代期间生成的，因此它被保留为“永久”堆对象以供将来迭代使用。

第一次迭代耗时较长 零件 因为它正在分配和生成列表，尽管由于 GHC 的“凹凸分配器”，分配非常快，实际上生成列表可能只需要几秒钟。大部分时间可能花在垃圾收集上。 GC 时间与需要从凹凸分配器中拯救(复制)的“重要”内容的大小成比例，并且您正在此处构建一个大的、永久的列表。

以后的迭代要快得多，因为它们可以对现有列表运行管道求和。这可能涉及对中间结果的一些分配，但其中大多数不会留下来，因此 GC 少得多，迭代也很快。

第二次和第三次迭代比后面的迭代慢一点的原因与 GHC 的分代垃圾收集器有关。最初，永久大列表和其他半永久(例如，只需要短时间或当前迭代)堆对象都从凹凸分配器中复制出来。进一步的垃圾收集涉及重新复制相同的永久列表，同时允许收集过期的半永久对象。最终，列表被提升到下一代，而所有非列表对象都留在第一代。

一旦永久列表和半永久“其他对象”完全分离到不同的代，在第一代的 GC 期间不再需要重新复制列表，迭代时间稳定在大约一秒。