When you find ways to make your code faster, those optimizations can cause trouble for people who use your code.

I first encountered this problem in 1968, when I was in college. We had just taken delivery on an IBM System/360 Model 91, which was the fastest general-purpose computer commercially available at the time.

I had been reading about the computer's architecture, and wrote a program that multiplied two 256x256 matrices in order to test my understanding. To my surprise, the program took several times as long to run as I expected. Not only that, but when I increased the matrix size to 257x257, the program ran faster — in fact, it was every bit as fast as I had expected.

After experimenting, I figured out the reason. Like most computers, even today, the processor was much faster than memory. Unlike modern computers, however, this one did not have a cache. Instead, it divided memory into 16 segments, and had hardware to allow data to be fetched from or stored in each segment in parallel with the others. Moreover, as it executed instructions, the processor looked ahead to see what memory locations it would need, and sent out commands to fetch the data from those locations far enough in advance to take the memory cycle time into account.

Programs often access memory sequentially: They look at location n, then n+1, and so on. Accordingly, memory locations were allocated in segments by putting 8 bytes in one segment, the next 8 bytes in the next segment, and so on. To figure out which segment contained a particular address, the hardware would discard the low-order three bits (i.e., divide by 8), then look at the next four bits (i.e., divide the quotient by 16 and look at the remainder).

Multiplying two matrices involves looking at successive elements of a row of one matrix in parallel with elements of a column of the other matrix. If both matrices are stored in the same way, then either the rows or the columns of a 256x256-element matrix will have their consecutive elements 256 positions apart. By implication, these consecutive elements will all wind up in the same memory segment.

Accordingly, when my program fetched the matrix elements in order to multiply them, all of the elements that it fetched from one of those matrices were in the same memory segment. As a result, the machine had to wait for that one memory segment to cycle each time it processed a matrix element, and the program ran more slowly. When I changed the matrices to 257x257, the problem went away.

This example indicates a general problem. One of the more common ways of speeding up programs is to figure out what operations those programs do particularly often, and find fast ways of doing them. This strategy creates an artificial breakpoint: If what you're doing fits the definition of a common operation, it's much faster than if it doesn't. Such breakpoints encourage people to program in ways that stay within the definition of "common," causing system designers to spend even less time on the uncommon cases, and so on.

This phenomenon makes program performance harder to predict than it would be otherwise. Even if an algorithm runs in, say, linear time, you cannot blithely assume that doubling the size of the input will only double the program's execution time. It might be that the larger size exceeds a breakpoint, which in turn causes the program to run much more slowly than expected.

Such breakpoints and side effects are yet another reason that you should take the trouble to measure your programs if you care about how long they take to run.