#22 - Premature Optimization Part 1: Math in my Head

If you have spent any time programming professionally you have undoubtedly heard the phrase "premature optimization is the root of all evil." The quote in all likelihood originated with a 1974 paper written by Donald Knuth. But that quote can be somewhat taken out of context, he isn't saying that all optimizations are evil, just 97% of optimizations. And in those remaining 3% of cases, optimization is essential.

Of course that may need to be taken with a grain of salt, because this was a paper in which he was rehabilitating the use of the "go to" statement. While the goto command was a mainstay in 70's and 80's programming languages (all vestiges of earlier work) the command fell out of favor at the expense of the then current fashion called "structured programming," where every operation fit into a neat nested structure. With enough looping control structures like "for," "while," and "do ... while" and the ability to continue or stop loops higher up in the structure there is no demonstrable need for a goto command except for the most pathological cases. And even those cases can be solved without a single goto as long as readability, performance, and maintainability are not concerns.

This, however, does not stop programmers from optimizing their code. For every programmer that dutifully writes clean expressive code there is at least one other programmer who is trying to eek out every possible cycle of performance whenever they are at the keyboard.

To put it in Vegas terms 97% sounds like a surefire bet, as long as you are making only one bet. But if instead we said that 97% of all stove tops are at room temperature you wouldn't go out and habitually put your hand on one every time you see one, because eventually you will be burned.

So the typical difference here between the first and the second programmer is that the second programmer got burned badly by a performance issue.  So their response is that they are always looking to improve performance, and they are implementing those findings immediately. What keeps the first programmer in line is the jarring memory of the time they were served up a plate of spaghetti code that was optimized by the second programmer. This isn't to say that the first programmer never optimizes their code.  The first programmer optimizes where it is needed, which is rarely where you think it is.

When approaching FizzBuzz with an eye for optimizations there are several that you can do, and several that you have to do. The first optimization you need to do is to re-order the consideration of the output, basically in reverse order. You don't want to handle the general case of a problem until you are sure that you do not need to handle any of the special cases. The way the problem is stated, they are all special cases.

- |- -| - +

This implementation of FizzBuzz presents a presumptive optimization, collapsing the two modulus operations for the FizzBuzz case into a single modulus operation.

public class ThreeModuluses {

public static void main(String[] args) {
  for (int i = 1; i <= 100; i++) {
    if (i % 15 == 0) {
      System.out.println("FizzBuzz");
    } else if (i % 5 == 0) {
      System.out.println("Buzz");
    } else if (i % 3 == 0) {
      System.out.println("Fizz");
    } else {
      System.out.println(i);
    }
  }
}

}

If we do a little bit of math in our heads we can reason that any number that is divisible by 3 and 5 at the same time is also divisible by 15, so rather than checking both 3 and 5 twice, we can check them only once by only checking for 15. We still have to check for 3 and 5 later on, but in this case we get some occurrences that only have to do long division once.

Where we were doing possibly four modulus operations in what was considered unoptimized code, we are now doing at most 3 of those operations, so we can say we removed 25% of the wasted CPU cycles.  This isn't the best optimization out there, but it is a start.