Why does Timing return different times for the same calculation?

Question

I did an experiment in which I calculated the same quantity two different ways to see which method was faster. To my surprise, the kernel time was different in different runs. In fact, which method was faster differed between runs. Why? I expected the kernel time to be exactly the same for the same task. Have I misunderstood something about Timing or about kernel time?

In the code below, I calculated the 0-15th derivatives of g[x,v]. dgdv2 is calculated using the Do loop that Mathematica wizards say to never use, while dgdv3 is calculated the loop-free expert-approved way. The last line just verifies that the results are identical. I did three runs and got inconsistent times.

As a side note, in a different Question I asked, some commentors were confused by the first line of this code, so here is a link about defining derivatives. Also as a side note, the "bad code" seems to have been faster 2 times out of 3.

But my question here is about the Timing inconsistency. If anyone wants to discuss the relevant coding practice, I posted a different Question about that.

Derivative[q_, 1][y][x, v] = 
  D[(D[y[x, v], {x, 2}] + D[y[x, v], x]^2), {x, q}]/2;
ord = 16;
Print[Timing[
   dgdv2 = Flatten[{y[x, v], Table[0, {i, 2, ord}]}];
   Do[dgdv2[[i]] = Expand[D[dgdv2[[i - 1]], v]], {i, 2, ord}];]];
Print[Timing[dgdv3 = NestList[Expand[D[#, v]] &, y[x, v], ord - 1];]];
dgdv2 == dgdv3

Output from 3 runs:

(*
{25.584164,Null}
{25.006960,Null}
True

{24.226955,Null}
{24.336156,Null}
True

{24.211355,Null}
{24.601358,Null}
True
*)

Answer 1

The bottom line is that, given the accuracy with which Timing can measure, there is no difference in the timings you report. Timing has a lot more precision than accuracy. What you are seeing are stochastic fluctuations in the timing process.

Let me try to justify that conclusion.

First, for calibration purposes I need to establish the performance of your Do-loop on my system.

With[{ord = 16}, 
  First @ Timing[
    dgdv2 = Prepend[ConstantArray[0, ord - 1], y[x, v]];
    Do[dgdv2[[i]] = Expand[D[dgdv2[[i - 1]], v]], {i, 2, ord}];]]

30.2179

Somewhat slower than your system, but mine's over five years old, so perhaps that's only to be expected.

Next I get an estimate of the time it takes compute each new element of the list dgdv2.

timings = 
  With[{ord = 16},
    Module[{dgdv2 = Prepend[ConstantArray[0, ord - 1], y[x, v]]},
      Table[
        {i, Timing[dgdv2[[i]] = Expand[D[dgdv2[[i - 1]], v]]][[1]]}, 
        {i, 2, ord}]]];

TableForm[timings]

The table shows that the cost of computing a list element grows exponentially with ord, about $O(2^{ord})$. That means computing the individual elements completely dominates the computation. This is reinforced by comparing the time spent of computing the element to the total time given above.

Total[timings[[All, 2]]]

30.8171

This is essentially the same as the timings for the complete process. I infer that it doesn't matter whether you use Do or NestList -- their contribution to the overall timing is negligible.

The cause of the jitter that blurs your timings is your processor doing things other than running the Mathematica kernel that is evaluating your code. That can be all kinds of things, including running the Mathematica front-end you are using. Just moving the mouse around could affect the timings.