Optimization Unit Test

An optimization is also a feature of your system. As with any other feature, and probably more than most, it may cause bugs as further features are added.

An optimization reflects performance characteristics of the hardware your system is running on; these characteristics will change over time. It reflects performance characteristics of the system's architecture; these characteristics might change over time.

Lastly, an optimization is a trade-off. It has a cost; the optimization works if this cost is more than compensated by the savings it brings. The optimization will no longer work if its own cost goes up, if the savings go down. Cost and savings might change, not only over time, but across different contexts where the optimization is used.

Therefore,

Ensure that the optimization can be turned off by client code.
Write a UnitTest demonstrating that the optimization does work.

I was cleaning up the second iteration of an ExtremeProgrammingForOne project (slated to become a fully Extreme project as soon as there's at least one programmer besides me on the team). My UnitTests had suceeded in keeping all functionality working and any bugs short-lived (save for some code that interfaces with the JRun application server, which can't be unit tested until I have time to code up a ServletUnit framework of some sort), but some of that functionality was so dog-slow that it was becoming hard to work with.

I did exactly the Wrong Thing at first - I guess that should be expected when you're not PairProgramming - and made some optimizations I didn't need, as I found out to my chagrin when the code stubbornly refused to go any faster.

Finally, I turned to my UnitTests for help. I wrote something like this :

 public void testOptimization() {
  myWidget = new Widget();

  long unoptimizedStart = System.currentTimeMillis();
  myWidget.doSomeUnoptimizedStuff();
  long unoptimizedTime = System.currentTimeMillis() - unoptimizedStart;

  long optimizedStart = System.currentTimeMillis();
  myWidget.doSomeOptimizedStuff();
  long optimizedTime = System.currentTimeMillis() - optimizedStart;

  assert(unoptimizedTime > (optimizedTime * 10));
 }

(Actually I'm simplifying a bit, and giving myself more credit than I deserve; this form emerged after some more mucking about, partially writing the optimization, tearing out some hair, and so on; but for narrative purposes, let our character have come up with the scheme in one flash of insight.)

That was it! I could consider an optimization as just another bit of functionality, that could be UnitTested with all the rest. The important principles that emerged from the tests were a) it should be possible to turn optimizations on and off; b) having your code simple enough and reasonably well factored helps with a); and c) the real test is how much your optimization saves. One order of magnitude is a minimum for "early" optimizations, IMHO.

I maintain what is effectively a large amount of library code. Because the whole code which uses that library is only half a million lines of source, I am able to change the interface to the library to stop people using methods that are known to be slow. However, to make sure they don't put the slow calls back in, I then delete them. Your method of preserving the slow code to prove that it is slower than the new code seems to be fraught with danger, in that Murphy (who is a coder on my project) will still call the wrong one. (see MurphysLaw). -- JohnFarrell

The comparison is IMHO essential. It happened twice during the project that after a seemingly unrelated change, the performance unit test suddenly failed. This pointed out a significant design problem in both cases. If not for the test and the comparison, the flaws would have gone unnoticed.

Note that you can wrap both methods - doSomeOptimizedStuff and doSomeUnoptimizedStuff - in a single method doSomeStuff (and possibly mark the original methods private), and have the optimization controlled by a settable flag with a default of "optimized". This should keep Murphy at bay.

Also note the pattern's comments above. The "optimized" version has a cost - if only that it is slightly more complex than the simple slow version. Keeping the simpler version around is insurance, should conditions change such that the "optimized" version no longer performs significantly better than the simple version (or turns out not to be necessary, because the hotspots are elsewhere). If we are applying OnceAndOnlyOnce diligently, they aren't even strictly speaking "versions" - possibly the optimization can be factored out to a single locus in the code.

When optimizing "foo", why wouldn't we just rename the old slow method for doing Foo to "oldSlowFoo" and the new fast one to "foo"?

It is a good idea to compare two algorithms when optimizing. Unit testing them is iffy, but a sometimes a good idea. Keeping the old code around in the actual production code is bad. It just gets in the way. Consider that you do have a versioning system at your disposal, preferably one with a command line. You also have some nice scripting languages to AlternateHardAndSoftLayers of test code. Fetch the old code, run the performance tests. Fetch the new code, run the performance tests. Compare. (Perl is Light.)

Nonetheless, you will still die from interface changes. Another option is to copy and paste the old algorithm and put it inside the test code. This way, the actual code is not cluttered, but you have something to compare against.

<slaps forehead> Aye. The old, slow method goes off to live in a test class, it shouldn't stay around and clutter production code. (A similar tactic was discussed, on the mailing list IIRC, for dealing with code capable of writing old version of file formats.) Thanks for reminding me. -- lb

Really, you don't need to keep old algorithms around indefinitely if they are clearly worse than the new ones. Only for optimizations that make assumptions about other (lower) layers that may or may not be true do you need to have unit tests, such as the size of the data bus or instruction pipelining. Still, it may just be easier to just test for those assumptions (if you happen to know all of them ;). -- SunirShah