An experiment is not considered “barren and negative” when it disproves your conjecture: an experiment fails by being inconclusive.

Successful experiments are partly the product of good experimental designs, as described in Chapter 2; there is also an element of luck (or savvy) in choosing a well-behaved problem to study. Furthermore, computational research on algorithms provides unusual opportunities for “tuning” experiments to yield more successful analyses and stronger conclusions. This chapter surveys techniques for building better experiments along these lines.

We start with a discussion of what makes a data set good or bad in this context. The remainder of this section surveys strategies for tweaking experimental designs to yield more successful outcomes.

If tweaks are not sufficient, stronger measures can be taken; Section 6.1 surveys variance reduction techniques, which modify test programs to generate better data, and Section 6.2 describes simulation shortcuts, which produce more data per unit of computation time.

The key idea is to exploit the fact, pointed out in Section 5.1, that the application program that implements an algorithm for practical use is distinct from the test program that describes algorithm performance. The test program need not resemble the application program at all; it is only required to reproduce faithfully the algorithm properties of interest.

Some questions:

• You are a working programmer given a week to reimplement a data structure that supports client transactions, so that it runs efficiently when scaled up to a much larger client base. Where do you start?

• You are an algorithm engineer, building a code repository to hold fast implementations of dynamic multigraphs. You read papers describing asymptotic bounds for several approaches. Which ones do you implement?

• You are an operations research consultant, hired to solve a highly constrained facility location problem. You could build the solver from scratch or buy optimization software and tune it for the application. How do you decide?

• You are a Ph.D. student who just discovered a new approximation algorithm for graph coloring that will make your career. But you're stuck on the average-case analysis. Is the theorem true? If so, how can you prove it?

• You are the adviser to that Ph.D. student, and you are skeptical that the new algorithm can compete with state-of-the-art graph coloring algorithms. How do you find out?

One good way to answer all these questions is: run experiments to gain insight.

This book is about experimental algorithmics, which is the study of algorithms and their performance by experimental means. We interpret the word algorithm very broadly, to include algorithms and data structures, as well as their implementations in source code and machine code.

This chapter considers an essential question raised by Lady Byron in her famous memoir: How to make it run faster?

This question can be addressed at all levels of the algorithm design hierarchy sketched in Figure 1.1 of Chapter 1, including systems, algorithms, code, and hardware. Here we focus on tuning techniques that lie between the algorithm design and hardware levels. We start with the assumption that the system analysis and abstract algorithm design work has already taken place, and that a basic implementation of an algorithm with good asymptotic performance is in hand. The tuning techniques in this chapter are meant to improve upon the abstract design work, not replace it.

Tuning exploits the gaps between practical experience and the simplifying assumptions necessary to theory, by focusing on constant factors instead of asymptotics, secondary instead of dominant costs, and performance on “typical” inputs rather than theoretical classes. Many of the ideas presented here are known in the folklore under the general rubric of “code tuning.”