ParallelTable and Table do not give same result

Question

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.

Answer 1

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.)

Answer 2

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..