1
$\begingroup$

I'm building benchmarking experiments by timing the execution of C++ functions (in the past I've even put bounties to such questions). What I want to know is whether there's a standard method to tell me when to stop sampling this benchmarking process (now I'm setting the number of counts to heuristically high enough value) ?

To give a more concrete example, suppose I have a function f and by running it 5 times (I assume I'll be giving a lower bound for the sample size as input, e.g. "run at least 5 times") I get the following results:

| Exp. No  | Runtime (s) |
|----------|-------------|
|    1     |       11    |
|    2     |       12    |
|    3     |       17    |
|    4     |       22    |
|    5     |       15    |

How should I determine whether to stop or continue sampling? (preferably a method that'd be easy to code please)

$\endgroup$
1
  • $\begingroup$ A lot of times you just pick some target "delta" (say 0.1 sec) and keep running until the change in output is less than delta for, say, X runs. $\endgroup$
    – user237392
    Commented Apr 1, 2016 at 14:43

1 Answer 1

1
$\begingroup$

The comment from @Bey makes sense. Here are details how to implement this idea. I assume you want a 'fairly accurate' estimate of the true population mean running time $\mu$, which is estimated by the sample mean $\bar X$ of the observations collected so far. Assuming the running times are roughly normally distributed, a 95% confidence interval for $\mu$ is

$$\bar X \pm t^*s/\sqrt{n},$$

where $s$ is the sample variance and $t^*$ cuts 2.5% from the upper tail of Student's t distribution with $n - 1$ degrees of freedom. For the data in your example, this interval is $15.6 \pm 2.776(4.393)/\sqrt{5}$ or $(10.5,21.05).$ In particular, the margin of error is $\pm 5.45.$

Crucially then, you have to decide the maximum margin of error $\Delta = t^*s/\sqrt{n}$ that you are willing to tolerate. Suppose that is $\Delta = 3.$ Then a trial computation is $n \approx (t^* s/\Delta)^2 = (2.776(4.393)/3)^2 = 16.5.$

At that point, it might be sensible to try another five runs, for $n = 10,$ and see what the next estimate of $n$ is. Notice that the new value of $t^* = 2.262.$ A reason for not going directly to $n = 17$ runs is that $s$ is a major source of noise in this scheme. It may fluctuate considerably from one value of $n$ to the next, particularly when $n$ is small.

Notes: (1) If the process continues beyond $n = 30,$ then you can use $t^* = 2.$

(2) I don't know exactly what kind of 'time' $t$ you are capturing. If it can be influenced by 'garbage collection' or similar factors, you should ignore occasional large values, because outliers among the $t$'s will greatly inflate $s$.

(3) There are many sequential decision schemes in statistics. It is possible that some of them might fit your situation better than what I have proposed. But you asked for something simple to implement.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .