Sometimes, Making a Program Clearer Makes It Faster
Last week, I mentioned three kinds of optimizations and said I'd discuss the last kind this week:
- Optimizations that are really ways of avoiding needless pessimization;
- Optimizations that make an enormous difference with little effort, and
- 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.