Parallel and non-Parallel functions return different results?

Question

A friend of mine observed that when running ParallelMap or ParallelTable that he would get different results than when running Map or Table, respectively. This because, according to him, the Parallel were returning matrices that were not respecting the original ordering. According to him, the returned matrices were more dependent on the speed at which the CPUs were finishing their computations. An example would be:

m=Map[f,Range@10]
p=ParallelMap[f,Range@10]
(*that would return, for example:*)
(*m*) {1,2,3,4,5,6,7,8,9,10}
(*p*) {1,2,3,4,9,10,5,6,7,8}

Note that the above is only an example for you to understand the sort of problem that he is facing.

My question is the following: is any of you able to corroborate or deny this sort of behavior?

I am seriously worried that this is happening in my own code because it may be a serious problem for my data. Sorry if I can't give you a real working example, but I couldn't ask him for a snippet of his code.

Answer 1

I cannot reproduce this behavior. With the following code I tested whether two very long series of random numbers when processed serially or in parallel ever yield different results:

c = 0; (* counter to count the number of times the two results differ *)
Do[
 m = RandomInteger[1000, 10^6];
 If[Map[#^2 &, m] =!= ParallelMap[#^2 &, m], c++]
 , {1000}
 ]
c

result: 0. So never in 1000 evaluations did the results arrive out of order.

I assume this may be dependent on the function f. If, for instance, this function uses and changes global variables all bets are off:

f[x_] := (If[x == 1, c = 0]; (c++))

c = 0;
Map[f, Range@10]
ParallelMap[f, Range@10]

(* {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} *)

(* {0, 1, 10, 11, 10, 10, 2, 12, 11, 11} *)

Without knowing any details about f answering this question is impossible. But the above example shows it is pretty easy to make mistakes resulting in the described behavior.

Answer 2

It is important to understand that in Mathematica, semi-automatic parallelization, such as the one provided by ParallelTable or ParallelMap works only if the chunks of code executed in parallel have no side effects.

What does it really mean to say that f has no side effect? Another way to say it is that the output of f depends only on it's input and nothing else. In other words, f has no internal state that influences its result.

Here's a function that does have side effects:

c=0;
f[x_] := x + (c++)

Evaluating f twice with the same input gives different results:

f[2]
(* 2 *)

f[2]
(* 3 *)

The output does not only depend on the input, but also on some (possibly private-to-f) state that is preserved between subsequent calls to f, in this case c.

Functions like f above are simply not suitable for parallelization in Mathematica. Yes, this is a limitation in some sense, but it's also a great advantage in that side-effect-less functions are really easy to parallelize.

---

A comment on the order of evaluations:

As your colleague notes, the order of evaluations may affect the results for functions with side effects:

c = 0;
KeySort@AssociationMap[f, {1, 2, 3}]
(* <|1 -> 1, 2 -> 3, 3 -> 5|> *)

c = 0;
KeySort@AssociationMap[f, {3, 2, 1}]
(* <|1 -> 3, 2 -> 3, 3 -> 3|> *)

It also goes the other way: if the order of evaluations does affect the result, that tells me that his function must have had side effects.

He believed that parallelization fails because the order of evaluations is unpredictable. This is not correct. Parallelization fails much worse than that because f's internal state (the variable c) exists as a separate and independent copy for each parallel thread. The different threads are not al modifying a global c, they're instead modifying their own private local c. To put it plainly: the results will be rubbish.

---

The golden rule to keep in mind: code evaluated in parallel must never have any side effects, i.e. it must not maintain an internal state between subsequent evaluations.

Answer 3

The documentation for ParallelMap and ParallelTable specifically state:

• ParallelMap will give the same results as Map, except for side effects during the computation.

• ParallelTable will give the same results as Table, except for side effects during the computation.

If you actually experience out-of-order results you have encountered a bug. Most of the parallel functionality is implemented in top-level code that can be "spelunked" so it would be possible to bug-check it if sufficiently determined.

Of course the warning about side-effects stand; mutable programming and parallelism don't usually mix well.