37
$\begingroup$

Bug introduced in 8.0 and fixed in 11.2


It is stated in the documentation that

Parallelize[Map[f, expr]] is equivalent to ParallelMap[f, expr].

But what about these examples?

ParallelMap[#^2 &, f[x] + g[y]]
(* f[x]^2 + g[y]^2 *)

Parallelize[Map[#^2 &, f[x] + g[y]]]
(* f[x^2] + g[y^2] *)
$\endgroup$
  • 1
    $\begingroup$ I would report this to Wolfram Support. The workaround is to always use a list as the second argument of Map when parallelizing. $\endgroup$ – Szabolcs Feb 23 '17 at 16:23
  • 1
    $\begingroup$ Can reproduce -- I would report this as well. $\endgroup$ – user6014 Feb 23 '17 at 16:52
  • 1
    $\begingroup$ I would like to know in which versions of Mathematica this bug has been observed. Currently, I use M 7.0.1, and in it the two inputs produce identical outputs, the same as in the first one above. $\endgroup$ – innaiz Feb 24 '17 at 7:22
  • 1
    $\begingroup$ @innaiz I'm running mma 10.4 $\endgroup$ – Mher Feb 24 '17 at 11:27
  • 3
    $\begingroup$ With versions 8.0.4, 10.4.1 and 11.0.1 on Windows 7 x64 I get outputs as shown in the question. Considering the above comment by @innaiz, the bug was introduced in version 8.0. $\endgroup$ – Alexey Popkov Feb 25 '17 at 20:16
31
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @AlexeyPopkov That's actually a relief. What happened was that I typed HoldAllComplete instead of HoldComlete when I tried it. Thanks for pointing it out. $\endgroup$ – Szabolcs Feb 23 '17 at 19:34
  • $\begingroup$ @Nat Read the explanation and make your own judgement. Consider the rest of the post an opinion. $\endgroup$ – Szabolcs Feb 23 '17 at 20:25
  • $\begingroup$ @Nat OK, I removed that section since I agree that it would be good to have this fixed. When I first saw the problem, it seemed outrageous and a terrible bug. But after I looked at why it happens, it's hard for me to blame the developer because I would probably have fallen into the same trap. I don't want to argue about what to call it, but yes: it is confusing, a bad user experience, and the fact that ParallelMap does not do this proves that it can be fixed. However, after looking at the implementation, I strongly suspect that it wouldn't be hard to construct an example ... $\endgroup$ – Szabolcs Feb 23 '17 at 20:47
  • $\begingroup$ @Nat that also breaks ParallelMap. And I am a bit annoyed with Mathematica because it seems to difficult to robustly handle such cases :) $\endgroup$ – Szabolcs Feb 23 '17 at 20:48
  • 2
    $\begingroup$ Hah yeah, I'm a bit annoyed with Mathematica for its general lack of extensibility. I'm guessing that Wolfram got so caught up in CA because the whole Turing completeness of Rule 110 seemed like a good primitive ontology for a future system, but then he hit the same incompleteness barrier that screwed Hilbert's program, reducing Mathematica from what he'd dreamed to a CISC-like API engine for relatively short scripts. Then, whenever stuff gets stacked too far, it does... well, like the bug in this question. $\endgroup$ – Nat Feb 23 '17 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.