Geek asks and answers

Options for parallelizing functions on the F # tree

In my project, I have a data structure represented as follows:

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

Due to the cost of going through large trees, I have to parallelize some of the following functions in this data structure:

  • Map
  • collapse
  • exists (there is a node satisfying the predicate condition)
  • reduce / convert (optional)

Due to the nature of the problem I'm working on, the number of branches in each node varies, and the workloads at the leaf level are pretty small. First question: what parameters should be considered for parallel execution on the tree. I am trying to use the functions from the module Array.Parallelon each node, however, since the parallelism service messages are also large, the parallel version is even slower than the serial version. I can change the representation of the array to Listor PSeq, if necessary.

, parallelism . , node, , .

+3
2

? , (MailboxProcessor ) , , . ( , ), , , . , parallelism. , , node, .

. , . . . " ", .. 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]
+4

Array.Parallel System.Threading.Parallel.For. , . Parallel.For, , , . ( Parallel.For , ).
, Daniel - , node . , , .

+3

More articles:


All Articles