How to best report code benchmarking results

Question

Let's suppose that we run a experiment consistent on the time it takes to execute a fixed piece of code. We know that the environment in which this code will be executed (the machine) will fluctuate due to a high number of different factors that we will assume are impossible to directly control. So we define the result of each experiment as the average of $n$ repetitions of the code execution. To gather statistical data, we perform $r$ different experiments so we end with a collection of $r$ data points. The question is:

Which is the best way to report the result of this experiments so we can extract the most information out of the report?

Notice that a possible approach like "give the mean and the standard deviation" has the downside of the fact that the distribution of errors has always negative skewness due to the fact that perturbations can only add to the final execution times and therefore $min(r_i)$ is the best measure on how much time the "code instructions" will take to execute in the abscence of perturbations.

As a second question:

What is the best number of repetitions ($r$) to have a statistically significat report for a given experiment?

This question was based on this discussion about how to propperly report microbenchmarking results in the CPython interpreter.

Answer 1

I assume what you are saying is true and that perturbations can only add to the execution time. When we are talking about execution time we are talking about $n_i$ not $r_i$. What we are doing is performing $n$ executions and taking the mean of these results to obtain $r_i$. Now that we have defined our problem, a good probability distribution which fits your profile is the exponential distribution. Lets define a random variable $X$ which is the execution time of a fixed piece of code.

PDF: $$P(X=x)=\begin{cases} \lambda e^{-\lambda(x-a)} &, x\geq a \\ 0 &, Otherwise \end{cases}$$

We perform $n$ executions of the code and average these results. Hence, let's define another random variable $Y$ which is the mean execution time.

$$Y = \frac{1}{n}(X_1+X_2+...+X_n)$$

By the central limit theorem we know that,

$$P(Y=y) \sim N(\mu,\sigma^2)$$

This is a profound result, and therefore you do not need to worry about the "left skewness" of each execution. Regardless of the probability distribution of $X$ averaging these results, $Y$ results in a Normal Distribution.

Hence, to answer your first question. With enough data for $r_i$, the mean and standard deviation of $r$ is enough. Obtaining the correct value of mean and standard deviation leads to your second question on "how many observations of $r_i$ do we need to report a statistically significant values?"

This question unfortunatly has no straight answer, you can read this page which showcases the information required such significance level and standard deviation. If you dont have this information, I always say, more data never hurts and only time will be a limitation.