Failing Forward

The STL (Standard Template Library) is an indispensable part of any C++ developers toolkit.  Their table of contents is practically burned into my URL bar.  Lists, vectors, maps, sets – all are such rudimentary data structures that I find it difficult to write an application without any of them.  One of the penalties of the STL though (after you master the gag reflex over its sometimes brutish syntax) are the iterators.

I love the iterators, don’t get me wrong, they are a very handy construct.  But if you’re not careful, they can chew the efficiency right out of your application.  The simplest example is this (supposing you have a vector of unsigned ints called “numbers”):

std::vector::iterator it;
for ( it = numbers.begin(); it != numbers.end(); ++it ) {
  // Do stuff with *it
}

In the above code, you’ll see a highly unexceptional for loop.  What’s wrong with it?  Potentially nothing.  So long as the vector isn’t too big.  Here’s an alternative:

std::vector::iterator it;
std::vector::iterator end = numbers.end();
for ( it = numbers.begin(); it != end; ++it ) {
  // Do stuff with *it
}

The difference is obvious, but it can really be a deal breaker if your containers are large enough.  I think back to this past summer.  I have an application for work that really needs to run as lean as possible.  It was doing okay, but I knew there were bottlenecks.  After consulting gprof, I realized that std::map::end() was chewing up billions of cycles.  Unnecessarily.  After applying the above logic throughout my code, I saw a significant performance increase.

How many cycles are you wasting in your loop control statements?

Update: Sorry for the odd behavior of the arrow brackets in some feed readers. Should be fixed now.