Choosing the fastest code between two equivalent codes

I want to learn how to use statistics to help me choose between two equivalent code. I want to choose the "fastest", the one that would take the less time to execute.

How should I collect data? And what test should I use to help me decide?

Let's take a concrete example, you have two ways to compute the double of a number n:

f(n) = n + n
g(n) = n * 2


How would you collect data? Should you:

1. Take a random number n, compute f(n) et g(n) 1000 times, recording each time the amount of time it took.
2. Take 1000 random numbers, compute f(n) and g(n) for each of those numbers one time.
3. Take 1000 random numbers, compute 1000 times f(n) and g(n) for each of those numbers.

(I wrote 1000, but I don't know how many samples would be reasonable)

Now, for that set of data, what test should I choose?

I wrote "fastest" with quotes before, because I don't really know what it means in mathematical terms. Do we want to compare the fastest time between the f set and the g set? Do we want to get the fastest on average? What about errors in the dataset?

With some google search, I saw that the Student T-Test would be reasonable. But I would not know which one to choose, since I don't quite understand the concept of a dependent/independent variable, paired/not paired.

saying that: "You should not use Student's T-test as it has a lot of assumptions which you can easily and unknowingly violate. It is much better so use some nonparametric tests."

(What are the assumptions that can easily be violated? What nonparametric test to choose?)

I've chosen f and g to understand more about the statistical method to choose the fastest one (so I can apply that with more complex codes/problems). I'm not really interested by programming tips.

• Packages such as microbenchmark in R seem to do a lot of what you are after. – Christoph Hanck Jan 2 at 15:54
• 1. What you might want to compare depends on the circumstances. If its a small piece of code people will use many many times, comparing means makes sense. If it's something a person will only run once in their lives but it takes a long time, they may find the mode much more relevant ("how long am I most likely to wait?") or indeed the median might be more relevant (or in some cases some other location-measure, such as some upper quantile). ... ctd – Glen_b Jan 3 at 5:21
• ctd... 2. There's very likely no need to test; presumably you can generate as much data as required to accurately estimate the expected ratio of times (or whatever else you care to know) under any particular set of conditions, so hypothesis testing would be beside the point. The exception would be where the runs are expensive (in some sense, such as time) and you'd only be able to collect a relatively small sample. – Glen_b Jan 3 at 5:21

You can certainly use a $$t$$-test since you can (presumably) accumulate as much data as you want, and so the central limit theorem will have had enough time to kick in. As far as the amount of data that you need, that depends on how much of a difference in runtime you're trying to detect, and how much the runtime varies across independent executions. You can see this by looking at the definition of the $$t$$ statistic for two independent samples:
$$\frac{\bar{x}_1 - \bar{x}_2}{\sqrt{s^2_1 / n_1 + s^2_2 / n_2}} .$$
The smaller the difference you want to detect ($$|\bar{x}_1 - \bar{x}_2|$$), or the greater the variability in runtime ($$s_1$$ and $$s_2$$), the more data you need ($$n_1$$ and $$n_2$$). Again since you're generating the data yourself, you can probably simulate enough to alleviate these concerns.
$$T_1(n) = n \\ T_2(n) = 0.001 \cdot n^2 .$$