F# 树上并行化函数的选项

Question

在我的项目中，我有一个如下表示的数据结构：

type 'a Tree =
| Leaf of 'a
| Node of 'a Tree array

由于遍历大树的成本，我必须在此数据结构上并行化以下一些函数：

• 存在映射
• 折叠
• （存在满足 谓词）
• 减少/转换（可选）

由于我正在处理的问题的性质，每个节点的分支数量各不相同，并且叶级别的工作负载非常小。 第一个问题是我应该考虑在树上并行执行什么选项。但是，我尝试在每个节点上使用 Array.Parallel 模块中的函数，因为并行度太大，并行版本甚至比顺序版本慢。如果有必要，我可以将数组表示更改为 List 或 PSeq。

第二个问题是如何控制这些函数的并行度。我正在考虑通过树的深度、每个节点的分支数量、叶级的工作负载复杂性以及叶级的叶数进行控制。然而，将它们组合在一起似乎是复杂且不可预测的。

Answer 1

将遍历与其他处理分开怎么样？也许创建一个工作队列（MailboxProcessor 是一个很好的起点），并在遍历树时将其他工作排入队列以进行后台处理。它不能解决并行遍历问题（这似乎很难适应所有情况），但由于附加处理被降级到后台，它应该会很快。您可以尝试后台工作人员的数量，直到找到良好的并行度。这一切都假设每个节点要完成的工作量并不小。

编辑

这是一些代码。我确信它可以改进。我必须很快地把它敲出来。但这显示了基本概念。它只有一个“后台工作者”，即MailboxProcessor。我将保留更新它以使用多个工作人员的想象力。

type Msg<'a, 'b> =
    | Work of 'a
    | Done of 'b

type MapTransformer(f) =
    let results = ResizeArray()
    let m = MailboxProcessor.Start(fun payload ->
        let rec loop() =
            async {
                let! msg = payload.Receive()
                match msg with
                | Work work -> 
                    results.Add(f work)
                    return! loop()                
                | Done (channel : AsyncReplyChannel<_>) -> 
                    channel.Reply(results :> seq<_>)
            }
        loop())
    member this.Enqueue(item) = m.Post(Work item)
    member this.Results = m.PostAndReply(fun c -> Done c)

let uberMap tree =
    let m = MapTransformer(fun x -> x + 1)
    tree |> List.iter (fun x -> m.Enqueue(x))
    m.Results

uberMap [1; 2; 3]
//outputs [2; 3; 4]

Answer 2

Array.Parallel 使用System.Threading.Parallel.For。当您调用该函数时，它会尝试为给定任务找到最佳计划。然而，对于典型的递归树算法，这意味着对 Parallel.For 的大量调用，并且您最终可能会得到太多的线程。 （除非 Parallel.For 针对我不知道的用例进行了优化。）
所以我认为如果每个节点的工作负载不是太小的话，丹尼尔的建议是一个好主意。另一种想法是引入相对于树的剩余深度的阈值，如 Stephen Toub 在 此博客条目。