Options for parallelizing functions on F# tree?

Perhaps create a work queue ( MailboxProcessor is a good starting point) and, as the tree is traversed, enqueue additional work for background processing. It doesn't solve the parallel traversal problem (which seems tricky to get right for all cases) but with additional processing relegated to the background, it should go pretty quickly. You can experiment with the number of background workers until you find a good degree of parallelism.

This all assumes the amount of work to be done for each node is non-trivial EDIT Here's some code. I'm sure it can be improved. I had to hammer it out pretty quickly.

But this shows the basic concept. It only has one "background worker," i.e. , the MailboxProcessor I'll leave updating it to use multiple workers to the imagination type Msg = | 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.

Perhaps create a work queue (MailboxProcessor is a good starting point) and, as the tree is traversed, enqueue additional work for background processing. It doesn't solve the parallel traversal problem (which seems tricky to get right for all cases) but with additional processing relegated to the background, it should go pretty quickly. You can experiment with the number of background workers until you find a good degree of parallelism.

This all assumes the amount of work to be done for each node is non-trivial. EDIT Here's some code. I'm sure it can be improved.

I had to hammer it out pretty quickly. But this shows the basic concept.It only has one "background worker," i.e. , the MailboxProcessor.

I'll leave updating it to use multiple workers to the imagination. Type Msg = | 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.

I'm not sure I understand your suggestion. For example, with map function, output of the function is a tree with the same shape as input, only leaf nodes are adjusted. I don't think it is easy to separate between tree traversal and computation.

Can you explain clearer how to use MailboxProcessor in the context of tree algorithms? – pad Mar 16 at 18:20 I updated the question with code. I used a list instead of a tree, but the concept is the same.

– Daniel Mar 16 at 19:03 Nice formulation, Daniel. I still don't see similarity between list and tree here. Because list is flat, you can easily get result from Transformer.

Results which is a ResizedArray. However, tree is recursive, it is not clear to me how I can obtain results; if my input is a tree Node| Leaf 1; Node |Leaf 2; Leaf 3||, how it is gonna return Node| Leaf 2; Node |Leaf 3; Leaf 4|| (with small changes in the code). – pad Mar 17 at 10:40 To use this code with minimal changes, you would need to flatten the tree beforehand and un-flatten afterward.

One way I could imagine doing that is emitting a pair of node and parentNode as you traverse the tree. – Daniel Mar 17 at 14:46.

Array. Parallel uses System.Threading.Parallel.For. When you call that function, it tries to find an optimal schedule for the given task.

However, with a typical recursive tree algorithm, this means a lot of calls to Parallel. For and you probably end up with far too many threads. (Unless Parallel.

For is optimized for that use case which I don't know. ) So I think Daniel's suggestion is a good idea if the workload per node is not too small. An alternative idea is to introduce a threshold with respect to the remaining depth of a tree as described by Stephen Toub at the end of this blog entry.

Thank you for pointing out an interesting article. I've checked released source code of Array. Parallel module, they don't control degree of parallelism so it is possible to spawn too many threads.

One possible way to avoid it is overriding Array. Parallel module using ParallelOptions. MaxDegreeOfParallelism property.

The article has a nice idea of flattening the tree before doing computation, but it is only relevant with fold-like functions. I will definitely check out control parallelism by depth of a tree mentioned there. – pad Mar 16 at 18:52.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.