Why is ParallelTable slower than Table?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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, ...)

Answer 4

It depends on amount of data. You can use 1 weel constructor for a light wheigt. It will be faster to assembly than 4 weels. BUT if you have a bigger weight you will bring it faster then 1 weel constructor. Time of assembly + time of delivery

For Example

THIS IS FASTER AbsoluteTiming[Table[Length[Solve[x^i == 5 y, x]], {i, 1, 5, 1}];]

THAN THIS AbsoluteTiming[ParallelTable[Length[Solve[x^i == 5 y, x]], {i, 1, 5, 1}];]

BUT!

This is SLOWER AbsoluteTiming[Table[Length[Solve[x^i == 5 y, x]], {i, 1, 100, 1}];]

THAN THIS AbsoluteTiming[ParallelTable[Length[Solve[x^i == 5 y, x]], {i, 1, 100, 1}];]

Hastings 2015 Hands on Wolfram... "Note that increasing the number of CPU cores might not result in an exact linear speedup, since some extra time can be spent for scheduling the calculation and putting the results together."