programming - Reap, Sow with Parallelize: bad performance, why?

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.

Answer

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.