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.

  • $\begingroup$ It might help to explain your reasoning why you think "there is no way around it in my case". But of course, probably as a separate question and link there because this question is focused well enough as it is. $\endgroup$ Oct 30, 2017 at 12:46
  • $\begingroup$ @Billiska: I am not exactly sure what you want me to do. Why should I explain my reasoning for an experimental approach in a separate question? I have no question regarding this. $\endgroup$
    – Wrzlprmft
    Oct 30, 2017 at 12:49
  • $\begingroup$ I have to disagree with you taking the minimum runtime of repeated experiment. You seems to think there might be outliner upwards only. Might it be possible to also have outliner downwards? It is more typical to examine multiple statistics at the same time, e.g., mean, median, max. Who knows they may show something you didn't expect. It's an empirical experiment after all. $\endgroup$ Oct 30, 2017 at 12:53
  • 2
    $\begingroup$ This is very broad; books can be written about the topic, e.g. McGeoch's "A Guide to Experimental Algorithmics". One might even say you're asking, "Is there any standard for doing science?". So I'm not sure that this is reasonably scoped. Do you have more specific questions? $\endgroup$
    – Raphael
    Nov 1, 2017 at 21:50
  • 2
    $\begingroup$ Loosely related: cs.stackexchange.com/q/39597/755, cs.stackexchange.com/q/29854/755, cs.stackexchange.com/q/74178/755. $\endgroup$
    – D.W.
    Nov 5, 2017 at 17:47

2 Answers 2


C.C. McGeoch's "A Guide to Experimental Algorithmics" is a good reference for

  • how to set up experiments on algorithms,
  • how to interpret and use results, and
  • how to iterate towards more meaningful results if necessary.

In addition to elapsed time for each run, report seconds of user & system mode, and total IP packets, and total disk I/Os, if only to verify that some numbers are consistently "low" and have negligible impact on elapsed time.

On https://wiki.freebsd.org/BenchmarkAdvice PHK and others offer good advice, including

Use ministat to see if your numbers are significant. Consider buying "Cartoon guide to statistics"


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.