Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Optimizations Can Have Side Effects

February 15, 2012

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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video