Revisiting Knuth's "Premature Optimization" Paper

Summary

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<typename T> struct counting_multiset { int insert(const T & x) { return ++counts[x]; } private: std::map<T, int> 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<typename T> struct knuth_multiset { int insert_1(const T & x) { size_t i = 0; f...