Why the performance of list of Timings depend on the order?

Question

It seems that the result of list of Timings and AbsoluteTimings depends on the order, while RepeatedTiming is free from this problem. How to understand this behaviour of timing functions?

The related codes are as follows. (The original aim is to compare the performance of similar functions on different types of data.)

Tested function

types = {"integer", "letter", "symbolLetter", "word", "symbolWord"}
functions = {complementVerbatim, Complement}
argnumber = 2;
(*`argnumber` specifies the number of arguments*)

complementVerbatim[list1_List, list2_List] := 
  DeleteCases[list1, Alternatives @@ Verbatim /@ list2];

Sample space

Choose portion of the samples as test data and save them into downvalues of data.

size = 2 10^4;
portion = 0.6;

sampleSpace["integer"] = RandomInteger[2 size, size];
sampleSpace["letter"] = RandomChoice[Alphabet[], size];
sampleSpace["word"] = RandomWord[size];
sampleSpace["symbolLetter"] = ToExpression /@ sampleSpace["letter"];
sampleSpace["symbolWord"] = ToExpression /@ sampleSpace["word"];

Table[data[type, argnumber] = 
   Table[RandomSample[sampleSpace[type], portion size // Floor], {i, argnumber}],
  {type, types}];

Timing

Now evaluate the functions on data with different order and timing functions.

Table[timing[Sequence @@ exception] := "/", {exception, exceptions}];

timing[function_, type_, argnumber, timingFunction_] :=
First@timingFunction[function @@ data[type, argnumber];]

timing[abs, fun] = 
  Outer[timing[#1, #2, argnumber, AbsoluteTiming] &, functions, types];
timing[abs, type] = 
  Outer[timing[#2, #1, argnumber, AbsoluteTiming] &, types, functions] // Transpose;

timing[re, fun] = 
  Outer[timing[#1, #2, argnumber, RepeatedTiming] &, functions, types];
timing[re, type] = 
  Outer[timing[#2, #1, argnumber, RepeatedTiming] &, types, functions] // Transpose;

timing[fun] = 
  Outer[timing[#1, #2, argnumber, Timing] &, functions, types];
timing[type] = 
  Outer[timing[#2, #1, argnumber, Timing] &, types, functions] // Transpose;

timingShow[x__] := SparseArray`SparseBlockMatrix[{
    {1, 1} -> {{""}},
    {1, 2} -> {types},
    {2, 1} -> List /@ functions,
    {2, 2} -> timing[x]
}] // TableForm

Result

Interestingly the three timing functions give different results.

The results of RepeatedTiming don't depend on the order:

while the results of Timings and AbsoluteTimings do depend, and they are different from single runs like

timing[Complement, "integer", argnumber, Timing]
(*0.011819*)
(*comparing with 0.004266 in the table.*)

hence are untrustable.

Answer 1

I think your table does not show a systematic bias, just random variation. If you run again, then you will get different results. From the documentation:

• "Timing is accurate only down to a granularity of at least $TimeUnit seconds." See here.

• "AbsoluteTiming is always accurate down to a granularity of $TimeUnit seconds, but on many systems is much more accurate." See here.

I just evaluated $TimeUnit on my machine and got $\frac{1}{100}$, hence I should not expect timings of less than a few tens of milliseconds to be accurate when obtained using Timing or AbsoluteTiming. Therefore use RepeatedTiming if you are anywhere close to $TimeUnit.