5
$\begingroup$

Original Example

Consider function f, a parallelized version fPar, and a coarsest-grained parallelized version fParCG below.

f[l_] := Map[Function[x, x[[#]] & /@ ConstantArray[Range[l], l]],
  Permutations[Range[l]]]

fPar[l_] := ParallelMap[Function[x, x[[#]] & /@ ConstantArray[Range[l], l]],
  Permutations[Range[l]]]

fParCG[l_] := ParallelMap[Function[x, x[[#]] & /@ ConstantArray[Range[l], l]],
  Permutations[Range[l]], Method -> "CoarsestGrained"]

The functions have the same output, which is just a list containing l copies of every permutation on Range[l].

f[3] // Column

(*
{{1,2,3},{1,2,3},{1,2,3}}
{{1,3,2},{1,3,2},{1,3,2}}
{{2,1,3},{2,1,3},{2,1,3}}
{{2,3,1},{2,3,1},{2,3,1}}
{{3,1,2},{3,1,2},{3,1,2}}
{{3,2,1},{3,2,1},{3,2,1}}
*)

I was surprised to see the parallelized versions are both slower.

f[9] // MaxMemoryUsed // AbsoluteTiming
(* {1.38304, 496422488} *)

fPar[9] // MaxMemoryUsed // AbsoluteTiming
(* {2.81347, 504604072} *)

fParCG[9] // MaxMemoryUsed // AbsoluteTiming
(* {2.46533, 561971768} *)

What in particular makes f not well-parallelizable?

There seems to be little overhead and the computations are independent. Function f is of the form Map[A,B] where each application of A to an element of B takes the same amount of time and the computations can be split equally, easily, and independently into different kernels. This is why I was expecting at least the coarsest grained version to perform better.

Notes

  • Yes, I have read Why won't Parallelize speed up my code?. I am wondering what principle from the answer to that question my function f violates such that it is not apt for parallelization.
  • Secondly, I am not looking for a more efficient form of f. Function f is an inane way of generating its output. I am wondering what makes f, as it is, not well-parallelizable.

Another Example

Courtesy of Michael E2 in the comments...

Table[p, {p, Permutations[Range[9]]}]; // AbsoluteTiming
(*{0.056542, Null}*)

ParallelTable[p, {p, Permutations[Range[9]]}]; // AbsoluteTiming
(*{4.74558, Null}*)

This disparity in speed is troubling to me. (As noted in the accepted answer, ParallelTable[] unpacks here, whereas Table[] does not. This still troubles me.)

Improve this question
$\endgroup$
11
  • $\begingroup$ Parallelization always require more memory because each used variable will be duplicated for parallel kernels. So, you pay memory consumption for almost proportional speedup. You have used Map inside Map. It is bad practice.. $\endgroup$
    – Rom38
    Jul 17, 2020 at 6:59
  • 1
    $\begingroup$ The operation you're parallelizing is simply not expensive enough to warrant the expense of shuffling all this data around between the master and slave kernels. I don't think there's more to it than that. Parallelizing to slave kernels is worthwhile mostly for expensive functions that take small inputs and generate small outputs. $\endgroup$
    – Sjoerd Smit
    Jul 17, 2020 at 9:20
  • 2
    $\begingroup$ @JustSomeOldMan Yes, but the inputs/outputs still need to be communicated between the master and slave kernels. There is still overhead even for simple maps like these. Another thing you might notice if you use On["Packing"], is that ParallelMap unpacks the array generated by Permutations, so that definitely counts against efficiency. This probably happens as part of the data transfer process. $\endgroup$
    – Sjoerd Smit
    Jul 17, 2020 at 21:18
  • 1
    $\begingroup$ @MichaelE2 If I understood correctly, sending large amounts of unpacked data is very inefficient (as noted in mathematica.stackexchange.com/questions/48295/…). So the unpacking itself may not be the worst, but it does slow everything that comes after down. $\endgroup$
    – Sjoerd Smit
    Jul 17, 2020 at 22:12
  • 1
    $\begingroup$ Maybe you're right. This seems pretty sorry: ParallelTable[p, {p, Permutations[Range[9]]}]; // AbsoluteTiming. $\endgroup$
    – Michael E2
    Jul 17, 2020 at 22:36

1 Answer 1

Reset to default
6
$\begingroup$

As I noted in a comment, it seems that ParallelMap unpacks packed arrays when sending the data to the slave kernels:

data = Permutations[Range[9]];
Developer`PackedArrayQ[data]

True

This simple Map will not generate any messages about packing:

On["Packing"];
Map[Total, data];

(* No messages *)

ParallelMap[Total, data]

(* generates Developer`FromPackedArray::unpack message *)

Unpacking of arrays is most likely a significant source of slowdown in parallel maps like this one since sending unpacked data is much slower according to this answer

Edit

Actually, item 3.4 in this answer does mention this problem to some degree and also links to a solution for the reverse problem when the values returned by parallel operations are packed arrays. At any rate, it's good advice to track the packing behavior of your computation when using parallel operations.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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