如何减少Haskell的并行化开销？

Question

我正在尝试了解 Haskell 的并行化性能。

我有一个很长的列表（长度 >1000），我正在使用并行的 parMap.

并行评估

这是单个线程使用 +RTS -s 的完整统计输出（编辑：完整统计输出）：

        54,248,802,288 bytes allocated in the heap
           324,451,424 bytes copied during GC
             2,970,272 bytes maximum residency (4 sample(s))
                52,064 bytes maximum slop
                   217 MB total memory in use (1 MB lost due to fragmentation)

                                          Tot time (elapsed)  Avg pause  Max pause
        Gen  0       251 colls,     0 par    1.45s    1.49s     0.0059s    0.0290s
        Gen  1         4 colls,     0 par    0.03s    0.05s     0.0125s    0.0319s

        TASKS: 4 (1 bound, 3 peak workers (3 total), using -N1)

        SPARKS: 6688 (0 converted, 0 overflowed, 0 dud, 1439 GC'd, 5249 fizzled)

        INIT    time    0.00s  (  0.03s elapsed)
        MUT     time   19.76s  ( 20.20s elapsed)
        GC      time    1.48s  (  1.54s elapsed)
        EXIT    time    0.00s  (  0.00s elapsed)
        Total   time   21.25s  ( 21.78s elapsed)

        Alloc rate    2,745,509,084 bytes per MUT second

        Productivity  93.0% of total user, 90.8% of total elapsed

      gc_alloc_block_sync: 0
      whitehole_spin: 0
      gen[0].sync: 0
      gen[1].sync: 0

如果我在两个线程上运行，使用 +RTS -N2，我得到：

        54,336,738,680 bytes allocated in the heap
           346,562,320 bytes copied during GC
             5,437,368 bytes maximum residency (5 sample(s))
               120,000 bytes maximum slop
                   432 MB total memory in use (0 MB lost due to fragmentation)

                                          Tot time (elapsed)  Avg pause  Max pause
        Gen  0       127 colls,   127 par    2.07s    0.99s     0.0078s    0.0265s
        Gen  1         5 colls,     4 par    0.08s    0.04s     0.0080s    0.0118s

        Parallel GC work balance: 41.39% (serial 0%, perfect 100%)

        TASKS: 6 (1 bound, 5 peak workers (5 total), using -N2)

        SPARKS: 6688 (6628 converted, 0 overflowed, 0 dud, 0 GC'd, 60 fizzled)

        INIT    time    0.00s  (  0.01s elapsed)
        MUT     time   25.31s  ( 13.35s elapsed)
        GC      time    2.15s  (  1.03s elapsed)
        EXIT    time    0.01s  (  0.01s elapsed)
        Total   time   27.48s  ( 14.40s elapsed)

        Alloc rate    2,146,509,982 bytes per MUT second

        Productivity  92.2% of total user, 175.9% of total elapsed

      gc_alloc_block_sync: 19922
      whitehole_spin: 0
      gen[0].sync: 1
      gen[1].sync: 0

在四个线程上：

        54,307,370,096 bytes allocated in the heap
           367,282,056 bytes copied during GC
             8,561,960 bytes maximum residency (6 sample(s))
             3,885,784 bytes maximum slop
                   860 MB total memory in use (0 MB lost due to fragmentation)

                                          Tot time (elapsed)  Avg pause  Max pause
        Gen  0        62 colls,    62 par    2.45s    0.70s     0.0113s    0.0179s
        Gen  1         6 colls,     5 par    0.20s    0.07s     0.0112s    0.0146s

        Parallel GC work balance: 40.57% (serial 0%, perfect 100%)

        TASKS: 10 (1 bound, 9 peak workers (9 total), using -N4)

        SPARKS: 6688 (6621 converted, 0 overflowed, 0 dud, 3 GC'd, 64 fizzled)

        INIT    time    0.01s  (  0.01s elapsed)
        MUT     time   37.26s  ( 10.95s elapsed)
        GC      time    2.65s  (  0.77s elapsed)
        EXIT    time    0.01s  (  0.01s elapsed)
        Total   time   39.94s  ( 11.76s elapsed)

        Alloc rate    1,457,427,453 bytes per MUT second

        Productivity  93.4% of total user, 317.2% of total elapsed

      gc_alloc_block_sync: 23494
      whitehole_spin: 0
      gen[0].sync: 10527
      gen[1].sync: 38

因此根据运行时间（每个输出中的最后一个数字），两个内核的程序占用单线程版本的 66%，而四个内核占用 54% 的时间。这种加速还算不错，但比理论上预期的内核数量线性改进要差得多，这将导致 25% 运行四核时间。

现在，当查看以上统计输出时，我可以看到程序的实际工作 CPU 时间（以 MUT 开头的行）随着使用更多内核而显着增加。使用 1、2 和 4 核时，我得到的 CPU 时间分别为 19.76 秒、25.31 秒和 37.26 秒，我相信这种增加会耗尽我的并行化性能。

我想到的这种 CPU 运行多核时间开销的典型原因是：

工作负载分布的粒度太细。但是，我使用 parallel 包中的 parListChunked 尝试了相同的程序，块大小为 10。但结果非常相似，所以我目前不认为开销是由于粒度太细了。
垃圾收集：这在过去对我的代码来说是一个很大的性能杀手，但自从我将 GC 大小增加到 100Mb 后，GC 花费的总时间非常少，如上面的统计数据所示。

造成如此高开销的其他原因是什么？我该如何减轻它们？

Answer 1

我看到人们投票关闭问题，因为没有足够的细节，但我相信可以使用已经提供的信息找到答案（尽管总是欢迎提供更多细节。）

我的鼻子告诉我，你受内存吞吐量的限制。我将尝试描述为什么我这么认为，但我不是硬件专家，所以我可能部分或完全错误。毕竟是基于我个人的一套硬件架构神话

让我们假设限制在每秒 50-100Gb 之间（我不确定它是否正确，如果你有更好的请纠正我。）

您将在 10 秒内分配 54Gb（-N4 情况），因此您的吞吐量为 5Gb/秒。是挺高的，不过一般情况下它本身不是问题。

大多数分配通常都是短期的，一旦 gen0 分配区域（苗圃）填满，它们就会被 GC。默认情况下，托儿所大小为 512 Kb，因此所有分配都发生在 L2 缓存中。所以短暂的生命数据永远不会进入主内存，这就是为什么它几乎是免费的。

但是您将 Nursery 大小增加到了 100Mb。它不适合二级缓存，将被转移到主存中。这已经是一个坏兆头了。

好吧，5Gb/秒离极限还很远。但是你增加苗圃规模是有原因的——你的数据不是短暂的。一段时间后，它将在其他地方使用。这意味着这 54Gb 迟早会从主内存加载回缓存。所以你至少有 10Gb/秒的吞吐量。

距离限制还很远，但请注意，这是最佳情况——顺序内存访问模式。实际上，您是以随机顺序访问内存的，因此相同的缓存行会被加载和卸载多次，您很容易达到 100Gb/秒。

要解决此问题，您应该确定为什么我们的数据不会短暂存在并尝试解决它。如果这不可能，您可以尝试增加数据局部性并更改内存访问模式以使其顺序。

我想知道硬件专家对我幼稚的解释有何看法:)

如何减少Haskell的并行化开销？

How to reduce Haskell's parallelization overhead?

parallel-processing

performance

haskell