10
$\begingroup$

Update

Following a comment of Szabolcs have changed Timing to AbsoluteTiming. The results are virtually the same.

Original post

I have accidentally observed the following surprising result. So, why should I use ParallelTable?

$Version

(* Out[114]= "10.1.0  for Microsoft Windows (64-bit) (March 24, 2015)" *)

p[x_] = x^2;

Measurement with Timing[]

Timing[Table[p[i], {i, 1, 10^5}]][[1]]

(* Out[118]= 0.156001 *)

Timing[ParallelTable[p[i], {i, 1, 10^5}]][[1]]

(* Out[119]= 0.530403 *)

some statistics

t0 := Timing[Table[p[i], {i, 1, 10^5}]][[1]]

tp := Timing[ParallelTable[p[i], {i, 1, 10^5}]][[1]]

rt := tp/t0

tt = Table[rt, {50}];
ms = {Mean[tt], StandardDeviation[tt]}

(* Out[72]= {5.79498, 0.898244} *)

Measurement with AbsoluteTiming[]

AbsoluteTiming[Table[p[i], {i, 1, 10^5}]][[1]]

(* Out[62]= 0.133115 *)

In[63]:= AbsoluteTiming[ParallelTable[p[i], {i, 1, 10^5}]][[1]]

(* Out[63]= 0.903214 *)

some statistics

t0a := AbsoluteTiming[Table[p[i], {i, 1, 10^5}]][[1]]

tpa := AbsoluteTiming[ParallelTable[p[i], {i, 1, 10^5}]][[1]]

rta := tpa/t0a

tta = Table[rta, {50}];
msa = {Mean[tta], StandardDeviation[tta]}

(* Out[68]= {5.94756, 0.933185} *)

Comparison

msa/ms

(* Out[94]= {1.0045, 1.10433} *)

The results for Timing[] and AbsoluteTiming[] are approximately the same.

EDIT: cases of advantageous parallelization

Let us define a function which measures the advantange of taking the parallel function over the normal one, i.e. the "normal" execution time divided by the parallel execution time:

advantageParallel[f_] := 
 AbsoluteTiming[Table[f[n], {n, 1, 10^6}]][[1]]/
  AbsoluteTiming[ParallelTable[f[n], {n, 1, 10^6}]][[1]]

and test some functions

advantageParallel /@ {EulerPhi, DivisorSigma[1, #] &, PrimeQ,FactorInteger, 
  MoebiusMu, #^2 &, Sin, Tanh, EllipticK[#/(1 + #) &]}

(* Out[60]= {1.46032, 1.30282, 0.153376, 0.213928, 
  0.667186, 0.162014, 0.108339, 0.104784, 0.0136566} *)

Hence for EulerPhi[] (suggested by Quantum_Oli in a comment) and DivisorSigma[] parallel execution is advantegous, for the rest of our selection the converse is true.

$\endgroup$
  • 2
    $\begingroup$ Likely the overhead time cost of distributing the task across cores is longer than it takes for one core to just do the task, in this case. If you try a more complicated p which takes more time to execute you should find a situation where ParallelTable wins. $\endgroup$ – Quantum_Oli Oct 12 '16 at 10:14
  • $\begingroup$ @Quantum_Oli I appreciate any suggestions for a complicated p to perform this test. $\endgroup$ – Dr. Wolfgang Hintze Oct 12 '16 at 13:00
  • $\begingroup$ Try using EulerPhi with a table going up to 10^6 elements. On my system it takes 3.7s using Table and 1.1s using ParallelTable. $\endgroup$ – Quantum_Oli Oct 13 '16 at 9:21
  • $\begingroup$ @Quantum_Oli Thank you for your suggestion, I confirm it. See my EDIT. $\endgroup$ – Dr. Wolfgang Hintze Oct 19 '16 at 14:44
  • $\begingroup$ you should actually do the comparison of Timing and AbsoluteTiming for an example where there is some speed gain by parallelizing. The two will only give the approximately same results in cases where the overhead dominates and there is no speed gain (or more precisely when the time spent in the main kernel with handling overhead is comparable to the total computation time)... $\endgroup$ – Albert Retey May 22 '18 at 9:18
10
$\begingroup$

As @AlbertRetey said, parallelization in Mathematica is not extremely efficient. It is only worth it if the original code took a relatively long time to execute. With a multi-second execution time, it may be worth thinking about parallelization. With sub-second execution times, it probably won't be possible to gain anything.

This is the useful and practical answer to your question. I am still interested in what it is exactly that's slow here, hence my other answer. But that's mostly of theoretical interest.

There are techniques other than parallelization with the parallel tools to speed up things. I'm going to show a few below:

p[x_] = x^2;

Table[p[i], {i, 10^5}]; // AbsoluteTiming
(* {0.075937, Null} *)

The original timing is less than 0.1 s on my computer (M11.0.1), so the parallel tools aren't the right choice for further speedups. What else can we do?

It's good to be aware that Table automatically compiled its argument when it can. Let's help it do this. Let's inline the code:

Table[i^2, {i, 10^5}]; // AbsoluteTiming
(* {0.00322, Null} *)

This is a more than 20x speedup. When the structure of p allows for it (e.g. symbolic expressions), we can simply do

Table[p[i] // Evaluate, {i, 10^5}]; // AbsoluteTiming
(* {0.002974, Null} *)

Another way is vectorization:

Range[10^5]^2; // AbsoluteTiming
(* {0.00082, Null} *)

p[Range[10^5]]; // AbsoluteTiming
(* {0.000837, Null} *)

This is another 3.5x speedup. See here for more info on vectorization.

Vector arithmetic is extremely efficient. It will typically be faster than naive C code because it makes use of SIMD instructions and is often internally parallelized. (It uses a not so naive C implementation internally.)

Finally, there is another way to parallelize in Mathematica: by making listable compiled functions.

cf = Compile[{{x, _Integer}}, x^2, 
  RuntimeAttributes -> {Listable}, 
  Parallelization -> True]

cf[Range[10^5]]; // AbsoluteTiming
(* {0.003539, Null} *)

Since it's Listable, this will do element by element processing (i.e. it won't use vector arithmetic), but it makes use of all the CPU cores in your computer. The Compile documentation page has more examples.

As you can see, it is slower than the other approaches for this particular trivial case. But I assume that you showed this case only as an example. In practice, we will usually have more complex cases, where this approach may be worth it.

In general, here are some ways to try to speed up applying a function to a list:

  • If the function is really simple and can be translated to vector arithmetic, do that first. However, this gets complicated quickly, and is not always possible. The first problem is typically too many branches (functions like If).

  • Next, try to write the function in a way that operations like Map, Table can automatically compile it.

  • Next, Compile it manually. Make use of vector arithmetic inside of compiled functions too. If this is not possible, make a compiled function that operates on single elements, but make it parallelized and listable, then apply it to a list of values in one go.

$\endgroup$
6
$\begingroup$

This is a long comment, not an answer.

I spent some time tracking down where the time is spent. This ParallelTable spends most time in

DistributeDefinitions[p]

Parallel`Developer`ParallelDispatch[
  HoldComplete[Identity[Table[p[i], {i, 1, 25000, 1}]], 
   Identity[Table[p[i], {i, 25001, 50000, 1}]], 
   Identity[Table[p[i], {i, 50001, 75000, 1}]], 
   Identity[Table[p[i], {i, 75001, 100000, 1}]]]
  ];

It is this bit that is slow, not any other code ParallelTable (such as this).

ParallelDispatch uses Send/Receive of which Receive is slow. That can then be tracked further to receive, then to kernelRead, then finally to LinkRead.

Here is evidence that it is reading the data from the link that is slow:

Send evaluations manually:

Inner[Parallel`Developer`Send, HoldComplete @@ Kernels[], 
  HoldComplete[Identity[Table[p[i], {i, 1, 25000, 1}]], 
   Identity[Table[p[i], {i, 25001, 50000, 1}]], 
   Identity[Table[p[i], {i, 50001, 75000, 1}]], 
   Identity[Table[p[i], {i, 75001, 100000, 1}]]], 
  List] // AbsoluteTiming

Get links:

links = LinkObject /@ Parallel`Kernels`Private`subKernel /@ Kernels[]

Read directly from the links:

res = LinkRead /@ links; // AbsoluteTiming
(* {0.186672, Null} *)

This accounts for most of the time spent (on my machine).

But I don't understand why! Because sending this amount of data through a shared memory link is normally much faster.

On kernel 1:

link = LinkCreate["foobar"];

LinkWrite[link, Developer`FromPackedArray[Range[25000]^2]]

On kernel 2:

mylink = LinkConnect["foobar"];

LinkRead[mylink]; // AbsoluteTiming
(* {0.004387, Null} *)

What is happening? Why is reading from a subkernel link much slower than reading from a user-created link?


Notes:

Timing is not the correct way to measure time here. It measures only the main kernel's time and adds up per-core time. AbsoluteTiming is the right way as it measures actual elapsed time.

The two give the same result here.

What this tells us is that the slowdown is entirely due to code being evaluated on the main kernel. It is not due to computation on subkernels. Not sure if the time taken by the MathLink transfer is included in Timing, possibly it's included partially.

$\endgroup$
  • $\begingroup$ Subkernel link is also the subkernel's $ParentLink. I believe extra things are done for this link over and above any auxiliary links, since the input and output is expected to come through here. What those things are, I'm not exactly sure, but at the least it results in various *Packets wrapping what one sends and receives on that link that one doesn't get otherwise. Considering that one can get a syntax error packet in response, there must be some fairly detailed checks on what comes in through that link. $\endgroup$ – Oleksandr R. Oct 18 '16 at 18:03
  • $\begingroup$ @OleksandrR. I should update this, Jakob in chat showed me that the transfer gets slow when we exceed the 32-bit integer limit ... $\endgroup$ – Szabolcs Oct 18 '16 at 18:17
5
$\begingroup$

Your results are not at all surprising, it is a common and well known fact that naive parallelism in many (almost all?) cases is slower than sequential execution. This is due to all kinds of overheads and your example is almost a perfect worst case for parallel execution: it does a very cheap calculation and will transfer quite a lot of data between the kernels and with default settings will send that data in many small chunks.

That said, of course Mathematicas implementation of parallelism is at a very high level and tries to do many things automatically, which makes these overheads much larger than really necessary, so there might be several places where it could be optimized.

It is also a known fact that it is far from trivial to make parallel code give good speedup on different computers/architectures, as it does depend even more on specific hardware capabilities as sequential code. There are some useful options which are a must to know and understand when you expect to gain real speedup from your code and will usually need some fine tuning to make best use of your specific hardware. The most prominent is the Method option which most parallel functions understand, the following setting can guide you in the right direction, even for your simple example:

Timing[ParallelTable[p[i], {i, 1, 10^5}, 
  Method -> "CoarsestGrained"]][[1]]

Note that it most probably still is slower then sequential code, but at least not that much. With a larger number of iterations and more kernels it might become faster than the sequential code at some point on some hardware, but of course it still stays a problem which is too simple to expect any relevant speedup, at least with such a high level approach. (For most real problems, "CoarsestGrained" is of course not the best Method setting).

Another thing which I realized when testing is that the initial overhead of launching the kernels will of course make it difficult to see any speedup if not for very long running problems, so you probably want to do a

LaunchKernels[]

once befor making any such tests. Choosing the right number of kernels for your specific problem and hardware can also make a big difference. Of course you can also argue that this is part of the inavoidable overhead and not do it, but then you should remember to make all tests with a fresh kernel for comparability...

Here is a problem where you see that parallelism in fact can speed things up quite a bit (at least on my machine):

q[x_] := NIntegrate[Sin[200.*y], {y, 1, x}]
AbsoluteTiming[Table[q[i], {i, 1, 10^3}]][[1]]
AbsoluteTiming[ParallelTable[q[i], {i, 1, 10^3}]][[1]]

I usually would only consider parallel execution as a choice for runtime optimization when the problem is well suited to parallelism (luckily there are plenty of problems which are trivial to parallelize, especially in scientific work) and when the inevitable effort for gaining good speedup is worth it (e.g. very long total computation time, many repetitions of similar computations, ...)

$\endgroup$

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.