Abstraction Penalties Are No Laughing Matter

Democracy is the theory that the common people know what they want, and deserve to get it good and hard.

—H.L. Mencken

Because this is the April issue, we start out this article as satire. We wanted to poke fun at programmers who try to avoid the "abstraction penalty" — the price you pay for abstract, general programs rather than specific ones — by optimizing parts of their programs that don't matter. We even came up with an appropriately satirical line of argument in favor of micro-efficiency, whether or not it makes sense.

The argument goes like this: People use computers because they want to get things done quickly. After all, if they didn't care about speed, they could always do the same computations themselves, by hand, without using a computer at all. Therefore, performance is the sine qua non — the raison d'être of programming. Without it, you might as well be using a slide rule, abacus, or pencil and paper. (It's like the story of the two hikers who had taken off their shoes and were resting, when they saw a bear. One of them slowly started putting his shoes back on. The other said, "Why are you putting your shoes on? If that bear sees us, you can't outrun it." The first one replied, "I don't have to outrun the bear; I just have to outrun you.") A program that is too slow will have no users and might as well not exist.

Of course, there is the possibility that careless optimization will make the program stop working. We might have answered, tongue in cheek, that if you optimize carelessly, you deserve what you get: All you need to do to ensure that your programs continue to work is to avoid making any mistakes in your optimizations. Surely, any good programmer should be able to stick to correct optimizations, right?

Of course, in practice, every optimization carries the risk of breaking something. However, continuing in a satirical vein, we might have noted that it's not always that important to avoid breaking code. If a nonworking program is fast enough, people will use it despite its problems. Then you can charge extra to fix the problems, or promise to fix them in the next version, thereby putting pressure on users to upgrade. People who are unaccountably fond of "old-world craftsmanship" may ask rhetorically: "Why is there never time to do it right, but always time to do it over?" Our answer was going to be that if you take the time to do it right, someone else will beat you to the market; but once you've locked in enough customers, they'll pay you to do it over for the rest of your career.

When we got to this point, we realized that we were in trouble. Our arguments were too convincing to stand as satire: People might be tempted to take them seriously. Part of the trouble comes from the fact that even small performance improvements can make a big difference in the right circumstances. The author of a commercial C++ compiler once told us that a difference of only 7 percent in how fast his compiler ran a widely known benchmark program was enough to swing prospective purchasers toward or away from his compiler. We have trouble measuring a program's execution time reliably to within 7 percent, but nevertheless we believe his experience.

So where does this realization leave us? If we were to write an article advocating optimizations that we think are absurd, why is there the risk that people might take our absurdities seriously? To put it another way, why do so many programmers spend time on optimizations that we think are absurd? The reason, we think, is that the abstraction penalty can be anywhere from trivial to overwhelming, and it is sometimes very difficult to tell in advance which it will be. As a result, when you write a program for which performance is likely to matter, there is great temptation to take every optimization opportunity that comes along — even those that a little extra thought would prove to be pointless.

A Pointless Optimization

As an example of a superficially appealing but pointless optimization, suppose you are writing a program that computes a filename from information that a user supplies, and then opens the corresponding file. Your first inclination might be to do it this way:

std::string filename = /* whatever */;
std::ifstream file(filename.c_str());

This technique is nice and general: It imposes no limits on the length of the filename (aside from the amount of memory available), and the Standard Library takes care of all memory-allocation problems for the user.

However, this generality comes at a cost. In most implementations, every std::string object has dynamic memory associated with it, and allocating and freeing this dynamic memory isn't free. Moreover, if you use an std::string object as a filename, you must first convert it temporarily to a const char* by calling its c_str member, a call that might involve copying all of the string's characters.

If you decree that no file can have more than, say, 1000 characters in its name, you can make your program faster:

char filename[1001];
// Put appropriate characters into filename, and then
std::ifstream file(filename);

In this example, we have allocated a 1001-character array (1000 characters for the filename, plus a null character at the end) on the stack, so that we don't have to go through the overhead of dynamic memory allocation. Because this array is on the stack, its storage will be freed automatically at the end of its scope. Of course, when we are putting characters into this array, we should be sure to check that we don't exceed our 1000-character limit.

Is this optimization worthwhile? Even without measuring it, we can say fairly confidently that it is pointless. The reason is that the amount of time we save will surely be trivial in comparison to the amount of time it will take to read even a small file from disk.

We see optimizations of this kind all the time, and it was such optimizations that we originally intended to use as our satirical subject. However, further reflection convinced us that there are optimizations that look silly at first glance that turn out to have a surprisingly large effect.

A Surprisingly Important Optimization

As an example of an optimization that looks pointless but actually makes a big difference, consider this piece of code, which creates a string of 100,000 asterisks:

std::string s;
for (int i = 0; i != 100000; ++i)
   s = s + '*';

Suppose you replace the last line of this code fragment by:

s += '*';

What effect do you think this replacement will have on the program's execution time?

Unless you have a good feel for algorithms, especially in the context of the C++ Standard Library — or you suspect a trick question — you are likely to be surprised: On our (fairly fast) desktop computer, the first version takes nearly two seconds to run, and the second version runs too quickly to measure. Whence the discrepancy?

The discrepancy comes from two properties of the C++ Standard Library:

• The std::string class allocates memory in a way that makes repeated append operations efficient.
• The compiler does not recognize s = s + '*'; as an append operation.

Consider what happens when s is a long string and the implementation tries to execute:

s = s + '*';

The first step is to form a new string that contains the value of s + '*'. Doing so requires making a copy of all of the characters in s — an operation that obviously must have an execution time that grows linearly with the number of characters in s. Once that copy is made, its value can be assigned to s, which may well require copying all of those characters again. Whether or not it does so, the time it takes to evaluate s + '*' is at best proportional to the length of s.

Now consider the apparently equivalent:

s += '*';

The += operation knows that it is appending to the object on its left, so the only reason it might need to copy the characters in that object is if there is not enough free memory adjacent to those characters to hold the final result. To avoid having to reallocate too often, the += operator deliberately allocates more memory than it needs when it allocates memory at all. This strategy means that += typically doesn't need to allocate more memory, because there is already room for the character(s) being appended. Therefore, most of the time, executing:

s += '*';

requires only copying the single * character to the appropriate place in memory and updating a little bookkeeping information. Only occasionally is it necessary to reallocate s and copy the characters that constitute it.

Of course, there are better ways of creating long strings of asterisks. For example, if we define

std::string asterisks(100000, '*');

we will get a string with 100,000 asterisks much more easily than if we were to write an appropriate loop ourselves. However, the efficiency advantage of writing append operations as such applies equally well to problems that don't happen to have a specific language feature that solves them.

Suppose, for instance, that you want to concatenate several strings:

std::string s = a + b + c + d + e;

Because + is left-associative, this example concatenates a and b, then concatenates the result and c, and so on. To obtain the value of s, then, the program must copy every character in a five times, every character in b four times, every character in c three times, every character in d twice, and every character in e once. If, instead, you write it this way:

     std::string s = a;
     s += b;
     s += c;
     s += d;
     s += e;

then you might be able to get away with copying far fewer characters. You can change that "might" to "shall" by doing the following:

std::string s;
s.reserve(a.size() + b.size() +    c.size() + d.size() + e.size());
     s += a;
     s += b;
     s += c;
     s += d;
     s += e;

Before putting any data into s, we use the reserve member function to force s to allocate enough memory to hold its eventual value. Only then do we copy the characters of that value into s. The effect is to copy the characters of a, b, c, d, and e only once.

Discussion

We have seen that seemingly similar operations can vary dramatically in execution time — an observation that convinced us not to poke fun at people who optimize their programs apparently blindly. And yet, we do not wish to advocate uniformly that people replace straightforward usages such as string concatenations with multiple statements, merely to avoid having to copy characters a few extra times.

Even the small examples that we have examined so far suggest three distinct kinds of optimization:

• Optimizations that are certain (or nearly certain) to have no noticeable effect, such as trying to construct a string that represents the name of a file more quickly.
• Optimizations that might or might not be significant, depending on circumstances, such as avoiding copying the characters of a potentially long string multiple times.

• Optimizations that are certain (or nearly certain) to be significant in some realistic cases, such as replacing a quadratic algorithm by a linear one.

It is not always easy to tell which category a particular optimization falls into. What we need is a constructive way of deciding which optimizations are worth considering. In our next few columns, we shall investigate these issues more closely.