Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Sometimes, Making a Program Clearer Makes It Faster

May 02, 2013

Last week, I mentioned three kinds of optimizations and said I'd discuss the last kind this week:

  1. Optimizations that are really ways of avoiding needless pessimization;
  2. Optimizations that make an enormous difference with little effort, and
  3. Optimizations that are really ways of making the code clearer.

One kind of clarifying optimization is something that compilers often do automatically: replacing a subscript with a pointer. For example, suppose we have a vector<int> named v, and we want to compute the sum of its elements. We might write

 
     int sum = 0;
     for (auto n = 0; n != v.size(); ++n)
           sum += v[n];

Some programmers might argue that it is faster to write this code as

 
     int sum = 0;
     for (auto p = v.cbegin(); p != v.cend(); ++p)
           sum += *p;
 

Others might argue that a good compiler will generate pretty much the same machine code for both versions of this code, so the optimization is unnecessary.

However, optimization is not the real reason to prefer the second version of this code. Rather, the second version accesses v's elements only sequentially, which means that the same code will work for containers such as list<int>> that do not support random access. Of course, both of these examples are so simple that there isn't much practical difference between the two forms: Rewriting the first form if necessary takes only a few seconds. However, these examples illustrate a useful principle: You should avoid making assumptions about the data structures you use.

Here is another example of this principle. Suppose we have a function MakeThing that returns a value of type Thing. We want to call this function and save its value somewhere. We might write

 
               Thing t;

and then, later in the code, write

 
               t = MakeThing();

This is not a good strategy, because it initializes t to a default value and then overwrites that value with a copy of the result of calling MakeThing. This initialization is a bad idea — and not just because it is needless work: It assumes implicitly that a default Thing value exists. If, instead, we combine the initial definition with the initialization by writing

 
     Thing t = MakeThing();

then there is no need to assume that a default Thing value exists. Instead, this code will work even if Thing has no default constructor. The fact that it avoids creating and then overwriting a default value is just a bonus. Another bonus is that we don't need to remember the type that MakeThing returns:

 
     auto t = MakeThing();

We can generalize this suggestion: If we create a vector<Thing> with any elements:

 
               vector<Thing> vt(n);

then Thing must have a default constructor in order to supply initial values to the vector's elements. The same restriction applies to constructing arrays of Things. If, in contrast, we construct an empty vector<Thing>:

 
     vector<Thing> vt;

then there is no need for Thing to have a default constructor. Such a constructor might be useful for other reasons, but it is not necessary for this particular context. We can even use push_back to append elements to vt without needing a default constructor for Thing.

We have now seen two examples of how we can "optimize" our code by removing requests for operations that our data structures do not really need to support. I invite discussion of these examples, along with other examples that readers might find interesting.

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