Parallelize Map and ParallelMap

I did a bit of debugging to find the cause of the problem. After I found it, the problem no longer seems as outrageous as it looked at first sight.

The root cause of the problem is the following property of Plus:

Plus[x]
(* x *)

This means that unlike List, Plus cannot be used as a container that can be split into smaller parts and then put together again.

This works:

Join[Plus[a, b], Plus[c, d]]
(* a + b + c + d *)

This does not:

Join[Plus[a], Plus[c, d]]
(* Join[a, c + d] *)

Partitioning is the first step to parallelization—each partition (or batch) will be sent to a different subkernel. You have precisely two elements to evaluate (f[x] and g[x]), so they get partitioned into two batches of length 1 each. Plus[f[x], g[x]] ends up split into Plus[f[x]] and Plus[g[x]]. At one point these are (incorrectly) allowed to evaluate to f[x] and g[x].

More detailed analysis

The literal expression the system ends up constructing (and submitting for parallel evaluation) is:

HoldComplete[
 (sq /@ # &)[Unevaluated[Plus[f[x]]]], 
 (sq /@ # &)[Unevaluated[Plus[g[x]]]]
]

sq here is #^2&—I am going to use sq from now on to make it easier to follow what is happening. The two elements within HoldComplete are the two size-1 batches, with processing ready to be applied to them.

Now watch carefully what happens if we evaluate one of these elements:

• First, the Unevaluated gets stripped.

• Then we get sq /@ Plus[f[x]]

• Now the Plus evaluates because it has a single argument. If it had at least two, it wouldn't. We get sq /@ f[x]

• And then we get f[sq[x]] and finally f[x^2].

An interesting note is that if we had Map[sq] instead of sq /@ # &, then no further evaluation would take place after the Unevaluated gets stripped, and the problem would be averted (hint: perhaps this could be a good fix).

So if you thought that Map[f] and f /@ #& were the same thing, here's one example that proves them different.

Why is there a difference between ParallelMap[...] and Parallelize[Map[...]]?

ParallelMap[f, arg] effectively translates to

ParallelCombine[
  Function[e, Map[f,Unevaluated[e]]],
  arg
]

^{see Combine.m, line 324}

Parallelize[Map[f, arg]] effectively translates to

 ParallelCombine[
   Map[f, #]&,
   arg
 ]

The latter lacks an Unevaluated, which is the root of the problem.

^{see Evaluate.m, line 137}