Why is Timing so irregular? How should I measure efficiency?

*To*: mathgroup at smc.vnet.net*Subject*: [mg23364] Why is Timing so irregular? How should I measure efficiency?*From*: Wijnand Schepens <Wijnand.Schepens at rug.ac.be>*Date*: Thu, 4 May 2000 02:59:31 -0400 (EDT)*Organization*: RUG*Sender*: owner-wri-mathgroup at wolfram.com

Hi everybody, If I want to compare some functions (or procedures, or programming constructs, whatever) (which do the same thing) to find out which one is the fastest, I use Timing. But if I repeat Timing of the same expression, I get a (totally) different time (usually much less). Subsequent timing experiments normally yield the same (low) duration (asumptotic behaviour), but sometimes the timings are irregular and jumpy. Why is this? Are some initialisations necessary? Is it because Mathematica tries to compile? If so, does Mathematica remember the compiled form and try it if you redo the same thing? Does Mathematica store intermediate results? Has it got to do with memory (page swapping...)? If I do other things in Windows at the same time, does that affect the timing? What is the real duration of some calculation? The one returned by the first Timing? Or the asymptotic value of multiple timings? Or the mean value of a few timings excluding the first one? I see that most people on the newsgroup who want to compare efficiency of alternative functions do just 1 Timing. Is that the correct thing to do? What is the best way of determining the efficiency of a calculation? Example: In[1]:= divpairs2[lst_List] := Table[Sequence @@ Table[lst [[{j, i}]], {j, 1, i - 1}], {i, 2, Length[lst]}] In[2]:= testeff[f_, n_] := Table[{Timing[f;] // First}, {n}]; SetAttributes[testeff, HoldAll]; In[3]:= n = 200; t = Table[Random[], {n}]; In[4]:= testeff[divpairs2[t], 10] Out[4]= {{40.92 Second}, {3.84 Second}, {0.82 Second}, {0.88 Second}, {0.83 Second}, \ {0.82 Second}, {0.88 Second}, {0.82 Second}, {0.83 Second}, {0.88 Second}} The first duration is very long, the second less, and then it drops to a low value These are some durations I got on another calculation (10 times the same calculation!!): {{9.01 Second}, {111.77 Second}, {76.12 Second}, {62.17 Second}, {38.06 \ Second}, {10.99 Second}, {8.95 Second}, {4.34 Second}, {4.62 Second}, {3.9 \ Second}} Very strange. Maybe this is due to the fact that this calculation took a lot of memory and there was a lot of memory-swapping. I don't know.