Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Optimizing a Program Means Making It Run Faster, Right?

April 10, 2013

Last week and the week before that, I wrote about optimization. Looking back on those writings, I realize that I never said just what I mean by optimization. Thinking about it more carefully, I realize that there isn't a single universal definition.

More Insights

White Papers

More >>

Reports

More >>

Webcasts

More >>

People often use optimization to mean changing a program in ways that they think will make it run faster, but that casual definition is far from complete. For example, is a change to a program an optimization if you don't know whether it helps the program's performance?

This question may seem silly: Why bother optimizing if you don't know whether your optimization makes any difference? But can you truly say that you've never written code the way you did because you thought it would probably be faster — but didn't bother to prove that it actually was faster? For example, at one time or another, most C++ programmers have thought about which of the following styles is most appropriate for a function:

 
               void do_work(Thing t) { /* … */ }
               void do_work(const Thing& t) { /* … */ }
 

The first of these examples copies its argument to its parameter each time you call it; the second uses a reference to avoid copying the argument. Can you truly say that you have never thought about which of these forms runs faster?

In practice, which form is faster depends on the context, and probably does so more than most programmers realize. For example, in the second of these definitions, t is a reference — which means that each time the program uses t, the compiler has to look at the object to which t refers. If t were copied once, as in the first example, that object would probably be on the computer's stack; in the second example, each use of t might be a memory reference. The performance difference, if any, between these two states of affairs is heavily implementation-dependent.

Although it might not be obvious how copying an argument affects a program's performance, copying an object or not can affect a program's behavior in ways that are much more important than mere performance. To see this effect, consider this function:

 
     void scale(vector<double>& v, const double& x)
     {
           for (auto p = v.begin(); p != v.end(); ++p)
                *p /= x;
     }

This function divides every element of a vector by a given scalar. The program's author defines the scalar parameter x as a reference in order to avoid copying it.

Suppose that you have a vector v, and you want to scale it so that element number n becomes 1 and all the other elements are changed proportionally. You might consider writing something such as

 
               scale(v, v[n]);

This call doesn't do what you probably think it does. See if you can figure out why before reading on.

The problem is that the parameter that corresponds to v[n] is a reference. Therefore, calling scale has the same effect as executing

 
     for (auto p = v.begin(); p != v.end(); ++p)
           *p /= v[n];

When this code reaches v[n], it will have the effect of executing

 
     v[n] /= v[n];

thereby setting v[n] to 1. All of v's elements after element n1, leaving their values unchanged. If the scale function had defined x as double rather than as const double&, this problem would not have occurred.

We have just seen two hazards of optimization. When you change a program in ways that you believe will improve an aspect of its performance:

  • you might change its behavior without realizing it; and
  • you might know for sure whether your change was actually an improvement.

We will look at more surprising aspects of optimization next week.

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.
 


Dr. Dobb's TV