Micro-optimization is stupid

I tend to frequent the website stackoverflow.com. It’s a fantastic website. It allows knowledge to be shared in a unique way. The only problem is, some people have no idea what they are talking about. If there are enough people who agree with these misguided notions, well then these incorrect answers get up-votes. And the cycle of misinformation repeats. It isn’t too dissimilar from the various types of incorrect information regarding 32-bit machines and 4GB of RAM.

This isn’t a problem with stackoverflow.com, it’s a problem with people who claim things to be the case without actually testing if what they are saying is true. It happens time and time again. You may be wondering why the title of this blog entry is “Micro-optimization is stupid” when I haven’t even mentioned that yet, well wait no more, here it is. Someone had asked a question that had a simple answer on SO. He was trying to insert a pointer to an object into a list that contained actual objects. I am guessing he is usually a java programmer (this isn’t an attack on Java programmers, just that Java’s syntax for creating references to objects looks very much like the broken c++ he was trying to use). Someone took it upon themselves to not only give advice on how to correct this trivial error but also gave some optimization advice for iterating over the list. He recommended something like this:

for(std::list<Point>::iterator it = l.begin(), end = l.end(); it != end; ++i) {
    /* whatever */
}

as opposed to this:

for(std::list<Point>::iterator it = l.begin(); it != l.end(); ++i) {
    /* whatever */
}

The reality is that there isn’t a huge amount of difference between the two. The goal of the posters code is to avoid std::list::end() from being called after every iteration of the loop. I felt compelled to point out to the poster that the optimization recommendation was misguided as any sane compiler will nicely optimize that loop so the std::list::end() is only called once. In addition to that std::list::end() is typically an O(1), so even if it were called multiple times, it wouldn’t make a difference. You’re trading one memory fetch for another, with no real difference.

Of course, he argued, people who don’t know what they are talking about usually do :-P. He started claiming that since the compiler doesn’t know that the size is constant, it has to recalculate the size each time and that this extra function call would cause cache misses and such. See the problem here? There is enough techno-babble to sound convincing! But don’t worry folks, I was determined to demonstrate my point. So I responded with a few corrections. Most importantly, size() != end(), so even if it did need to recalculate size() each time, the size has nothing to do with it. In addition, if the loop only uses member functions that are const it certainly can know that the list hasn’t changed. (he of course retorted that while the end()/size() function is const, its result is not, which is just silliness, since end() won’t change the list, if all other functions don’t change the list, well then end() will be the same next iteration!). Finally, I sent him a link to some code that looks like this:

// program 1
#include <list>
#include <iostream>

int main() {
    std::list<int> l1;

    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_back(4);

    std::list<int>::iterator end = l1.end();
    for(std::list<int>::iterator it = l1.begin(); it != end; ++it) {
        printf("%d\n", *it);
    }
}

// program 2
#include <list>
#include <iostream>

int main() {
    std::list<int> l1;

    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_back(4);

    for(std::list<int>::iterator it = l1.begin(); it != l1.end(); ++it) {
        printf("%d\n", *it);
    }
}

And asked that he compile them both with g++ -O3 and look at the results. Not just assume what some other jackass told him was correct. I had already done this and knew that the result on the latest g++ is identical. At this point I had a good feeling, knowing I had prevailed… until he responded with this:

GCC 4.01 with g++ -O3 -S produces different assembly outputs and different binaries with vectors and lists. GCC 4.2 produces identical output for lists but different output for vectors. The OP uses a vector, my comment stands.

Seriously?! This guy just couldn’t admit being even slightly wrong. To be clear, the OP used a list, not a vector. So at this point, he was just making things up without taking the time to read. In addition, I checked and the “difference” between the two was more or less cosmetic. Doing the same work in a slightly different order (but not repeatedly calling end(), which was the original concern).

Finally, justice came and people started to down-vote his answer. He edited his post to remove the incorrect advice he gave and the downvotes were removed. None of this would have happened if he hadn’t gotten fixated on silly little micro-optimizations. When will people learn?

Tricks like this may have made a difference in the early days of c++, but modern compilers are surprisingly good at optimization. Let them do their job so that you can do your job!

At this point in time, every competent developer should know that it is best to do things in the simplest, most obvious way first. This is better in many ways, most importantly in maintainability. Everyone can agree that simple and obvious code is easier to understand. Then if after profiling you find that a particular segment of code is not performant enough, feel free to go bananas with optimizing the little things in that particular section.