Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Sometimes Optimizations Cancel Each Other

April 17, 2013

In 1906, O. Henry wrote a short story called The Gift of the Magi about a poor couple, each of whom had one prized possession. They sold these possessions in secret to buy gifts for each other — and each gift was rendered worthless by the other's sale.

More Insights

White Papers

More >>

Reports

More >>

Webcasts

More >>

Two rights can make a wrong in the software-design world, too. The most common case is when a language implementer sees that users tend to solve a particular program in a particular way, and go out of the way to make the implementation work efficiently when that solution appears. Meanwhile, some programmers think the obvious strategy is inefficient, so they choose what looks like a better alternative that winds up being slower.

One classic example is the technique of strength reduction, in which an optimizing compiler replaces an intrinsically slow operation such as multiplication a faster operation such as addition. For example:

 
     for (int i = 0; i != n; ++i)
           a[i] = 0;

In principle, evaluating a subexpression such as a[i] requires multiplying i by the length of an element of a. Even if the compiler is clever enough to realize that the multiplication can be replaced by a shift instruction, many computers take substantially longer to execute such an instruction than they would take to execute an addition.

An optimizing compiler will realize that a[i] is being evaluated in a loop with the value of i each time through the loop that is one greater than its previous value. It will therefore rewrite the loop to be something like this:

 
int* p = a;
for (int i = 0; i != n; ++i) {
     *p = 0;
     ++p;
}

Here, the compiler has replaced a[i], which requires a multiplication, with *p, which does not. In exchange for that gain, it has had to insert extra code to increment p each time through the loop. In effect, it has replaced a multiplication by an addition.

Suppose that a is an array, and that the programmer decides to make this optimization explicit; that is, to code the second of these examples in place of the first. If the compiler is clever enough to have rewritten the code automatically if the programmer did not do so, the hand optimization is a waste of effort. In fact, the hand optimization might even be worse than just a waste of effort, because when the compiler sees

 
*p = 0;

in user-written code, it is entirely possible that for all the compiler knows, p might be pointing to i at this point. Therefore, after executing this statement, there is the possibility from the compiler's point of view that the value of i might just have been reset to zero. This possibility means, for example, that the compiler cannot cache the value of i in a register, but must store it in memory and fetch it each time through the loop — just because of the possibility that the programmer might have reset i during the loop.

Of course, if the compiler, rather than the programmer, does the optimization, it knows that each time through the loop, p is pointing at an element of a, and therefore cannot be pointing at the local variable i. More precisely, whoever wrote the part of the compiler that does this particular optimization knows that there is no need for that optimization to take into account the possibility that p might be pointing at i. As a result, it is entirely possible that the compiler might do a better job of optimizing this loop than it is possible for the programmer to do.

This is one example of a common phenomenon: When you rewrite code to make it faster, it is often possible that you are conflicting with a compiler's effort to accomplish the same end. Sometimes the result of this conflict is that the hand optimization is wasted; other times, the hand optimization might even make matters worse.

Next week, we'll look at some cases in which optimizations that look similar on the surface to this one are different enough from it that they actually are worth doing as you write a program for the first time.

Related Reading






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