8
$\begingroup$

I have a question about the performance of Reap and Sow with Parallelize. I am aware of the following questions

and the Wolfram tips

but the following code shows (at least for this simple evaluation on my computer), that parallelization using Reap and Sow is somehow slow for this case

n = 10^3*2;
(*AppendTo*)
data1 = {};
Do[AppendTo[data1, x], {x, 0, n}]; // AbsoluteTiming
(*Reap and Sow, no parallelization*)
data2 = Reap[Do[Sow[x], {x, 0, n}]][[2, 1]]; // AbsoluteTiming
data2 == data1
(*Reap and Sow, with parallelization*)
SetSharedFunction[ParallelSow];
ParallelSow[expr_] := Sow[expr];
data3 = Reap[Parallelize[Do[ParallelSow[x], {x, 0, n}]]][[2,1]]; // AbsoluteTiming
Sort[data3] == data1

Here is the output

{0.015600, Null}
{0., Null}
True
{7.784414, Null}
True

Of course, all data are identical. For n=10^3*2 AppendTo is ok (not as fast as Reap and Sow, just increase n) but the parallelized version is horrible.

Question1: Why?

Question2: How would you parallelize this instead? I need to evaluate a huge program several times and I am interested only in saving the results (with Reap and Sow). Each run of the program is independent of all others (simple evaluations) so it can be parallelized. But now ParallelSow seems to be the bottle neck and I cannot think of another way.

$\endgroup$
  • $\begingroup$ Do you mean the same as the answer of Mr.Wizard? $\endgroup$ – Mauricio Fernández May 29 '15 at 17:40
  • $\begingroup$ Not exactly, but more or less. Sorry, I had your question open in my browser for a couple of days since I meant to make a comment, but I didn't reload it to see that there was an answer. I suppose I'll delete my comment now since it seems to add nothing important to what you already know. $\endgroup$ – Oleksandr R. May 30 '15 at 18:39
10
$\begingroup$

In Mathematica every inter-Kernel communication comes with significant overhead. Your simple Do loop with a shared Sow on every value is about the worst possible situation. Instead (for performance) you want to gather results within each Kernel and only pass them back to the master in a single call. (Or at least a limited number of calls.)

Using linked lists e.g. {{{n1}, n2}, n3} followed by Flatten will prevent the slow-down of AppendTo on long lists.

n = 1*^5;

(*AppendTo*)
data1 = {};
Do[AppendTo[data1, x], {x, 0, n}]; // AbsoluteTiming

(*Reap and Sow, no parallelization*)
data2 = Reap[Do[Sow[x], {x, 0, n}]][[2, 1]]; // AbsoluteTiming
data2 == data1

(*linked list*)
ParallelEvaluate[foo = {}];
sow[x_] := (foo = {foo, x};)
ParallelDo[sow[x], {x, 0, n}]; // AbsoluteTiming
(data3 = Join @@ ParallelEvaluate[Flatten@foo];) // AbsoluteTiming
data1 === Sort[data3]

{17.288, Null}

{0.0431217, Null}

True

{0.0527825, Null}

{0.0282877, Null}

True

The example chosen is probably overly simplistic and other measures may be needed for real-world problems.

$\endgroup$
  • $\begingroup$ Awesome, thank you very much! $\endgroup$ – Mauricio Fernández May 28 '15 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.