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.
 

Comments:

ubm_techweb_disqus_sso_-c802d7303e9b34fe631dfb02f0d8d993
2013-05-14T15:39:25

Using auto is future-proof as it doesn't cause slicing if someone returns a subclass of Thing. In current IDEs you will also see the type that the compiler thinks it is using when you mouse over an auto variable.

I don't think the "first line of defines" is type checking. I think the first line is code review and making code easier to read by reducing noise helps review. (I work in an environment where every line of code is reviewed.)


Permalink
ubm_techweb_disqus_sso_-f52b56a959d1f98bd9036f52b8f80338
2013-05-08T12:14:04

I would also not use the construct:
auto t = MakeThing();
What is really lost here is the first line of defense: type check. Is the return value of MakeThing really what is expected, or is it working by accident? auto is great if there are other clues indicating the real type in use, as e.g. in case of an iterator in a loop.
All that is important if you consider a junior programmer who is likely to take the advice and use it whenever possible.
But the point is this: sometimes we _need_ to remember…


Permalink
rudmerriam
2013-05-07T18:17:22

I was in a hacking contest which involved processing lists of 100,000s of items. Speed was of primary importance. I started with the classic for loop to get the implementation right. Then went to for_each to see how it fared and it was much faster. I then looked at the for_each code to see if I could optimize it. First I tried it without any change and it was slower than the for_each.

My final conclusion was that the compiler was smarter than myself. Remember "Computers are dumber than people but smarter than programmers."


Permalink
mttd
2013-05-02T17:32:01

This doesn't seem like a good idea ("n" should have type "std::size_t", this will make it an "int", with rather undesirable consequences):

auto n = 0


Permalink
ubm_techweb_disqus_sso_-bf2e3ae739be165c46e1320ba16c2b3b
2013-05-02T17:31:36

for (auto p = v.cbegin(); p += v.cend(); ++p)
should be
for (auto p = v.cbegin(); p != v.cend(); ++p)


Permalink
ubm_techweb_disqus_sso_-26be4e708c84c817e84abd2af4fd4ba2
2013-05-02T11:26:04

Someone please pull the plug!


Permalink
ubm_techweb_disqus_sso_-68ecb85aa1875c06e3512027f8534d97
2013-05-02T10:00:28

for (auto& e : v)

sum += e;


Permalink


Video