Revisiting Knuth's “Premature Optimization” Paper

The most famous quote from Knuth’s paper “Structured Programming with go to Statements” is this:

There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

People always use this quote wrong, and to get a feeling for that we just have to look at the original paper, and the context in which it was written. The paper isn’t actually about optimization. It’s about when we have to use goto statements because structured programming couldn’t express certain things at the time. Or at least it couldn’t do so efficiently, requiring extra checks, and that’s why Knuth has to talk about performance: The topic he is addressing is “Can we get rid of goto statements without sacrificing performance?”

The famous quote occurs just after Knuth talks about the problem of writing what C++ oxymoronically calls a multiset. (he obviously doesn’t call it that, but that’s what it is called in C++) Imagine you want to store a set of items, and the items can occur multiple times. Instead of actually storing them multiple times, you might as well just keep a count for each item. In C++ you might write it like this:

template struct counting_multiset { int insert(const T & x) { return ++counts[x]; } private: std::map counts; };

I’ll leave the other methods like ‘find’ and ‘erase’ as an exercise to the reader.

Knuth builds this set using two arrays: One for the elements, one for the counts. And, for the purposes of the paper, he always assumes that there is enough space in the array. So an insert might look like this, using goto:

template struct knuth_multiset { int insert_1(const T & x) { size_t i = 0; for (; i < size; ++i) { if (elems[i] == x) goto found; } ++size; elems[i] = x; counts[i] = 0; found: return ++counts[i]; } private: std::unique_ptr elems; std::unique_ptr counts; size_t size = 0; };

So just iterate through the array until we find the element. If we don’t find it, insert it at the end.

How does this compare in performance to the map-based approach? This is O(n), the map-based approach is O(log n), but arrays are fast. Arrays win until the set has more than ~300 elements in it:

... continue reading