My situation
I am writing a paper presenting a software module I developed and I want to compare its runtime to other modules for the same task. I am aware of the drawbacks of runtime experiments, but please assume as given that there is no way around it in my case. (I can and do deduce some properties theoretically, but it doesn’t suffice for everything.)
The specific scenarios I want to use for benchmarking have two parameters: the complexity $n$ of the problem and a random seed $r$ which determines the detailed problem. Mainly I want to show the dependence on $n$. Going by preliminary investigations and theory, the influence of $r$ on the runtime is minor or negligible. A single task takes at most ten minutes to complete.
Actual question
I am looking for some commonly accepted or published procedure on performing such experiments or at least a list of common pitfalls (ideally published).
What I found so far
Nothing. Internet searches turn up all sorts of unrelated results, but then I may not be using the right terminology. Including the keyword minimum, which I know to be a good standard (see below), didn’t help either.
How I would do it
Run all experiments on the same machine with potentially interfering software such as a GUI disabled as far as possible.
Subject all modules to the same selection of scenarios, i.e., the same $n$ and $r$.
For each scenario, test the different modules directly after each other in random order. With other words, the loop over the different modules is the innermost one. This should avoid bias on the different modules due to slow fluctuations of the machine’s performance (e.g., due to temperature changes). The random order should avoid bias through such effects as caching or one module always being tested after the same one.
For each $n$, take the minimum runtime over several scenarios with different seeds as the benchmark. This should avoid bias on the different modules due to short-time fluctuations of the machine’s performance that make individual runs exceptionally bad.
