# ParallelTable and Table do not give same result

I have a question regarding the use of Parallelize. In the help one can read that “Parallelize[Table[expr,iter, …]] (which is equivalent to ParallelTable[expr,iter,…]) will give the same results as Table, except for side effects during the computation.”

Ok, here I have an easy code where I use an If-conditional inside my Table:

arrayA=Table[RandomReal[{-1,1}],{i,1,1000}];
arrayToBeFilled=ConstantArray[0,1000];
Parallelize[Table[If[arrayA[[i]]<=0,arrayToBeFilled[[i]]=arrayA[[i]]+5,
arrayToBeFilled[[i]]=arrayA[[i]]-5],{i,1,1000}],Method->Automatic];//Timing


I do not get any useful result except my unaltered initialized array, but if I use the same code without Parallelize, it works fine (and even faster)! Since my real code (in principal the same as above but with more calculations) takes some time for evaluation, I hoped that I could increase the speed by using Parallelize. But it seems that either I am doing/understanding something wrong or that something is wrong with Parallelize by itself. Can somebody tell me what the case is?

I also would be happy if somebody could tell me a better way how I could increase the speed of such code as in my example.

-

### Why the unexpected result?

You quoted the documentation:

Parallelize[Table[expr,iter, …]] (which is equivalent to ParallelTable[expr,iter,…]) will give the same results as Table, except for side effects during the computation.

The explanation why the parallelized version returns an incorrect result is that your code does have side effects: you are using Set (i.e. =) to change the elements of an array.

### What is a side effect?

Let me illustrate using ParallelMap:

If we have a list of values list = {1, 2, 3, 4, 5, 6, 7, 8}, and we wish to evaluate a function for all these values, we can use Map:

f /@ list


This is easily parallelized to two processors by splitting the list into two parts (list1 = {1, 2, 3, 4} and list2 = {5, 6, 7, 8}), sending them to two different Mathematica kernels running on these two processors, and performing the map operation on the two sublists separately:

f /@ list1 (* evaluated on processor 1 *)
f /@ list2 (* evaluated on processor 2 in parallel *)


The reason this works at all is that these two operation are completely independent: the result of one does not depend on the evaluation of the other.

Actually this is only true if f is a function in the mathematical sense: it simply takes an input and produces an output, but computing its value does not change the "outside world" (the Mathematica kernel's user-visible state) in any way. Examples: Sin is a function without side effects in this sense. Print is not without side effect because while its value is being computed (it always returns Null), the outside world changes: something appears on your screen. Set also has side effects because it induces permanent outside changes again: the value of a variable will be different after evaluating Set.

If our function f has side effects then there is no guarantee that {f[1], f[2]} will give the same result as {f[2], f[1]} because evaluating f[1] might change the environment in a way that will affect the outcome of f[2]. The order of evaluation might matter, so parallelization cannot work reliably (the order of evaluation is unpredictable in any kind of parallel evaluation).

You are using Set (i.e. =) in your code, which has side effects. What actually happens is that a copy of arrayToBeFilled is sent to both subkernel 1 and subkernel 2, and different parts of the array are changed on the two subkernels. But the changed arrayToBeFilled is not being sent back to the main kernel (which one should be sent back at all? the one on subkernel 1 or the one on subkernel 2? they are different because different indices have been changed on the two subkernels)

### How to make the code auto-parallelizable?

We just need to write the expression to be computed in a way that avoids side effects:

arrayToBeFilled =
Parallelize[Map[If[# <= 0, # + 5, # - 5] &, arrayA]]; // AbsoluteTiming


This is both much faster and parallelizable. In fact it's so fast that when the array is only 1000 elements long the parallelization overhead will just slow the computation down. (For much larger arrays though it will speed it up.)

-
Thanks for this quick answer! I wasn’t aware that with side effect such effects are meant! I did not expect that Set causes such problems for Parallelize. Do you have any suggestions how I could avoid this side effect in my example code? Or do you have any idea how I could increase the evaluation speed? –  partial81 Feb 15 '12 at 8:26
@partial81 I updated the post. Please see if it answers your question now. –  Szabolcs Feb 15 '12 at 8:34
Dear @Szabolcs, Thanks a lot for the edit of your answer! It answers all of my questions and I am sure that it will enlighten a lot of other people how try to profit of mathematica’s capability of parallel computing. I really learned much of this detailed answer! –  partial81 Feb 15 '12 at 12:35

Your arrayToBeFilled doesn't change in the global kernel but in the parallel kernels. The way you should do your parallel is this:

arrayToBeFilled = Parallelize[Table[If[arrayA[[i]] <= 0, arrayA[[i]] + 5, arrayA[[i]] - 5], {i, 1, 1000}], Method -> Automatic]; // AbsoluteTiming


But of course would be better something like (and better if you define a good function:

arrayToBeFilled = Parallelize[Map[If[# <= 0, # + 5, # - 5] &, arrayA], Method -> Automatic]; // AbsoluteTiming


And use DistributeDefinitions is a good practice always, so you can be sure each kernel has its own copy of the variable (arrayA) you want to use..

-
Dear @FJRA, Thanks a lot for the edit of your answer! Your suggestions are as good as Szabolcs’ but his answer is a bit better because he explains very well how to use Parallelize in the right way. So I accepted his answer and not yours. I hope you are not too mad because of this. –  partial81 Feb 15 '12 at 12:38