Optimization Tip 1: Make sure you’re measuring what you think you are

Optimization is a subject fraught with witchcraft, voodoo, and superstition. Far too often it is done badly and pseudoscientifically. The first rule of optimization is that you can’t do it without measuring . Almost any guess you make about performance is at best irrelevant and often actively harmful. A common technique is to write a benchmark that runs the piece of code you’re trying to optimize several thousand times, and prints out the time it takes to run. Then tune until the time comes down.

They’re at least ten reasons why this technique fails more often than it succeeds (forgetting to account for HotSpot initialization, optimizing a piece of code in which the program spends a trivial amount of time, etc.) but recently I encountered an 11th: the benchmark may not be exercising the code you think it is. This turns out to be surprisingly common, and the more complex the code is, the more likely this is to occur.

There are two things worth doing before attempting to optimize against a benchmark:

1. Put a breakpoint in the model code you’re testing at the beginning of the section you’re trying to optimize, and run the benchmark in the debugger. If the debugger doesn’t stop there, the benchmark isn’t testing that section of code. It sounds improbable. How could the benchmark not be exercising exactly the piece of code it was written to test? Yet I’ve seen this happen more than once. Setting a breakpoint and running in the debugger only takes a minute or two tops, and even if it only reveals a problem one time out of ten, that one time can save you hours of pointless effort.

2. After you’ve verified that the benchmark at least reaches the code under test, make sure the benchmark is sensitive enough to pick up changes in that code. Usually you run the benchmark with two variants of the code, usually a presumed slow and a presumed fast one; and you claim to be testing whether the one you think is faster really is. (Double blind studies are almost unheard of in this field. Heck, even reproducible results are a newfangled notion.) But how sure are you that random variations in the system under test aren’t swamping your results? One way to tell is to run both at the same time. For example, I might start with a method that uses algorithm A like this:

   public double calculateSomething() {
     // algorithm A
     return x;
   }

   I want to compare that to a method that uses algorithm B:

   public double calculateSomething() {
     // algorithm B
     return x;
   }

   To make sure my benchmark is sensitive enough to detect any difference, I’ll first compare A and B to A+B like this:

   public double calculateSomething() {
     // algorithm A
     // algorithm B
     return x;
   }

   If the benchmark can’t tell the difference between A and A+B or B and A+B, then it probably can’t tell the difference between A and B either. You need a better benchmark. You’d be surprised how often this happens.

This entry was posted on Sunday, February 5th, 2006 at 6:50 am and is filed under Blogroll, Testing. You can follow any responses to this entry through the Atom feed. Both comments and pings are currently closed.