parallel-processing - 为什么我们没有通过 PSeq 获得性能提升？

Question

问题

我们认为并行处理每个“尾排列”会减少该算法的实际运行时间。为什么不呢？我们如何配置 PSeq 来缩短运行时间？

let rec permute (xs:'t list) = 
    if xs.Length = 1 then [xs]
    else ([], permute xs.Tail)
        // Why do we not get a performance 
        // improvement when we use PSeq here
        // relative to using Seq?
        ||> PSeq.fold (fun acc ps -> 
            (insertAtEach xs.Head ps)@acc)

permute ["A";"B";"C"] |> ignore

我们认为排列工作将按如下方式拆分，并且算法的 insertAtEach 阶段将并行工作。

                        [C]

             [BC]                [CB]

[ABC] [BCA] [BCA]                [ACB] [CAB] [CBA]

            CPU01                CPU02

即使我们使用大型初始列表(如 permute [0..9])，它实际上在并行时也更慢。我们还没有弄清楚 withDegreeOfParallelism 和相关的 PSeq 选项是否有帮助。

一边

这是其余的代码 list :

let put a q xs =
    ([], xs)
        ||> Seq.fold (fun acc x ->
            if x = q then a::x::acc
            else x::acc)
        |> List.rev

// Insert x at each possible location in xs
let insertAtEach a xs =
    ([a::xs], xs)
        ||> Seq.fold (fun acc x ->
            (put a x xs)::acc)

Answer 1

PSeq.fold 并不像您想象的那样。 PSeq.fold 实际上根本不是并行的。它是连续的。

---

您不能只是在算法中间的某个地方抛出“并行”一词并希望获得最好的结果。这不是并行化的工作方式。您必须真正了解正在发生的事情、并行发生的事情、顺序发生的事情、原则上可以并行化的事情以及不能并行化的事情。

以fold 为例:它将提供的折叠函数应用到序列的每个元素和上一次调用的结果。由于每个下一个调用在执行之前都必须有上一个调用的结果，很明显 fold 根本不能并行执行。必须是顺序的。事实上，如果您查看其 source code，这就是 PSeq.fold 实际执行的操作。 .因此，每次转换为 ParallelSequence 都会产生一些开销，但没有任何收获。

现在，如果您仔细查看您的算法，您可以梳理出可并行化的部分。你的算法做什么:

1. 递归计算尾部的排列。
2. 对于这些排列中的每一个，通过在每个索引处插入头部来展开它。
3. 连接第 2 步的所有结果。

当你这样说时，很容易看出第 2 步实际上并不依赖于任何东西，只依赖于它本身。每个尾部排列都与所有其他排列完全分开处理。

当然，仅查看您的源代码并不能证明这一点，因为您已将步骤 2 和 3 合并到一个表达式 (insertAtEach xs.Head ps)@acc 中，但它是使用以下一般身份很容易梳理:

xs |> fold (fun a x -> g a (f x))
    ===
xs |> map f |> fold (fun a x -> g a x)

也就是说，在 fold 期间，不是将函数 f 应用于每个元素 x，而是可以“提前”将它应用于每个元素"使用 map。

将这个想法应用到你的算法中，你会得到:

let rec permute (xs:'t list) = 
    if xs.Length = 1 then [xs]
    else permute xs.Tail 
         |> Seq.map (insertAtEach xs.Head)
         |> Seq.fold (fun acc ps -> ps@acc) []

现在很容易看出 Seq.map 步骤是可并行化的步骤:map 独立于其他元素将函数应用于每个元素，因此 原则上可以并行工作。只需将 Seq 替换为 PSeq 即可获得并行版本:

let rec permute (xs:'t list) = 
    if xs.Length = 1 then [xs]
    else permute xs.Tail 
         |> PSeq.map (insertAtEach xs.Head)
         |> PSeq.fold (fun acc ps -> ps@acc) []

PSeq 是否确实并行执行 map 是另一回事，但这应该很容易根据经验进行验证。

事实上，在我的机器上，对于 7 到 10 个元素的列表(11 个元素的列表导致 OOM)，并行版本始终优于顺序版本。

---

附言请记住，在测量时间时，您需要首先强制生成序列(例如，通过将其转换为列表或采用 Seq.last)。否则，您要衡量的只是并行化开销成本。

附言here's a gist with my benchmark code .