Loop optimisation techniques in C++

Question

In order to increase the performance of our applications, we have to consider loop optimisation techniques during the development phase.

I'd like to show you some different ways to iterate over a simple std::vector<uint32_t> v:

1. Unoptimized loop with index:

   uint64_t sum = 0;
   for (unsigned int i = 0; i < v.size(); i++)
       sum += v[i];
   

2. Unoptimized loop with iterator:

   uint64_t sum = 0;
   std::vector<uint32_t>::const_iterator it;
   for (it = v.begin(); it != v.end(); it++)
       sum += *it;
   

3. Cached std::vector::end iterator:

   uint64_t sum = 0;
   std::vector<uint32_t>::const_iterator it, end(v.end());
   for (it = v.begin(); it != end; it++)
       sum += *it;
   

4. Pre-increment iterators:

   uint64_t sum = 0;
   std::vector<uint32_t>::const_iterator it, end(v.end());
   for (it = v.begin(); it != end; ++it)
       sum += *it;
   

5. Range-based loop:

   uint64_t sum = 0;
   for (auto const &x : v)
       sum += x;
   

There are also other means to build a loop in C++; for instance by using std::for_each, BOOST_FOREACH, etc...

In your opinion, which is the best approach to increase the performance and why?

Furthermore, in performance-critical applications it could be useful to unroll the loops: again, which approach would you suggest?

Answer 1

There's no hard and fast rule, since it depends on the implementation. If the measures I did some years back are typical, however: about the only thing which makes a difference is caching the end iterator. Pre- or post-fix makes no difference, regardless of the container and iterator type.

At the time, I didn't measure indexing (because I was comparing iterators of different types of container as well, and not all support indexing). But I would guess that if you use indexes, you should cache the results of v.size() as well.

Of course, these measures were for one compiler (g++) on one system, with a specific hardware. The only way you can know for your environment is to measure yourself.

RE your note: are you sure you have full optimization turned on. My measures showed no difference between 3 and 4, and I doubt that commpilers optimize less today.

It's very important for the optimizations here that the functions are actually inlined. If they're not, post-incrementation does require some extra copying, and typically will require an extra function call (to the copy constructor of the iterator) as well. Once the functions are inlined, however, the compiler can easily see that all this is a unessential, and (at least when I tried it) generate exactly the same code in both cases. (I'd use pre-incrementation anyway. Not because it makes a difference, but because if you don't, some idiots will come along claiming it will, despite your measures. Or maybe they're not idiots, but are just using a particularly stupid compiler.)

To tell the truth, when I did the measurements, I was surprised that caching the end iterator made a difference, even for vector, where as there was no difference between pre- and post-incrementation, even for a reverse iterator into a map. After all, end() was inlined as well; in fact, every single function used in my tests was inlined.

As to unrolling the loops: I'd probably do something like this:

std::vector<uint32_t>::const_iterator current = v.begin();
std::vector<uint32_t>::const_iterator end = v.end();
switch ( (end - current) % 4 ) {
case 3:
    sum += *current ++;
case 2:
    sum += *current ++;
case 1:
    sum += *current ++;
case 0:
}
while ( current != end ) {
    sum += current[0] + current[1] + current[2] + current[3];
    current += 4;
}

(This is a factor of 4. You can easily increase it if necessary.)

Answer 2

I'm going on the assumption that you are well aware of the evils of premature micro-optimization, and that you have identified hotspots in your code by profiling and all the rest. I'm also going on the assumption that you're only concerned about performance with respect to speed. That is, you don't care deeply about the size of the resulting code or memory use.

The code snippets you have provided will yield largely the same results, with the exception of the cached end() iterator. Aside from caching and inlining as much as you can, there is not much you can do to tweak structure of the loops above to realize significant gains in performance.

Writing performant code in critical paths relies first and foremost on selecting the best algorithm for the job. If you have a performance problem, look first and hard at the algorithm. The compiler will generally do a much better job at micro-optimizing the code you wrote than you could ever hope to.

All that being said, there are a few things you can do to give your compiler a little help.

• Cache everything you can
• Keep small allocations to a minimum, especially within a loop
• Make as many things const as you can. This gives the compiler additional opportunities to micro-optimize.
• Learn your toolchain well and leverage that knowledge
• Learn your architecture well and leverage that knowledge
• Learn to read assembly code and examine the assembly output from your compiler

Learning your toolchain and architecture are going to yield the most benefits. For example, GCC has many options you can enable to increase performance, including loop unrolling. See here. When iterating datasets, it is often beneficial to keep each item aligned to the size of a cache line. In modern architecture this often means 64 bytes, but learn your architecture.

Here is an excellent guide to writing performant C++ in an Intel environment.

Once you have learned your architecture and toolchain, you might find that the algorithm you originally selected is not optimal in your real world. Be open to change in the face of new data.

Answer 3

It's very likely that modern compilers will produce the same assembly for the approaches you give above. You should look at the actual assembly (after enabling optimizations) to see.

When you're down to worrying about the speed of your loops, you should really think about whether your algorithm is truly optimal. If you're convinced it is, then you need to think about (and make use of) the underlying implementation of the data structures. std::vector uses an array underneath, and, depending on the compiler and the other code in the function, pointer aliasing may prevent the compiler from fully optimizing your code.

There's a fair amount of information out there on pointer aliasing (including What is the strict aliasing rule?), but Mike Acton has some wonderful information about pointer aliasing.

The restrict keyword (see What does the restrict keyword mean in C++? or, again, Mike Acton), available through compiler extensions for many years and codified in C99 (currently only available as a compiler extension in C++), is meant to deal with this. The way to use this in your code is far more C-like, but may allow the compiler to better optimize your loop, at least for the examples you've given:

uint64_t sum = 0;
uint32_t *restrict velt = &v[0];
uint32_t *restrict vend = velt + v.size();
while(velt < vend) {
  sum += *velt;
  velt++;
}

However, to see whether this provides a difference, you really need to profile different approaches for your actual, real-life problem, and possibly look at the underlying assembly produced. If you're summing simple data types, this may help you. If you're doing anything more complicated, including calling a function that cannot be inlined in the loop, it's unlikely to make any different at all.

Answer 4

If you're using clang, then pass it these flags:

  -Rpass-missed=loop-vectorize
  -Rpass-analysis=loop-vectorize

In Visual C++ add this to the build:

  /Qvec-report:2

These flags will tell you if a loop fails to vectorise (and give you an often cryptic message explaining why).

In general though, prefer options 4 and 5 (or std::for_each). Whilst clang and gcc will typically do a decent job in most cases, Visual C++ tends to err on the side of caution sadly. If the scope of the variable is unknown (e.g. a reference or pointer passed into a function, or this pointer), then vectorisation often fails (containers in the local scope will almost always vectorise).

#include <vector>
#include <cmath>

// fails to vectorise in Visual C++ and /O2
void func1(std::vector<float>& v)
{
  for(size_t i = 0; i < v.size(); ++i)
  {
    v[i] = std::sqrt(v[i]);
  }
}

// this will vectorise with sqrtps
void func2(std::vector<float>& v)
{
  for(std::vector<float>::iterator it = v.begin(), e = v.end(); it != e; ++it)
  {
    *it = std::sqrt(*it);
  }
}

Clang and gcc aren't immune to these issues either. If you always take a copy of begin/end, then it cannot be a problem.

Here's another classic that affects many compilers sadly (clang 3.5.0 fails this trivial test, but it's fixed in clang 4.0). It crops up a LOT!

struct Foo
{
  void func3();
  void func4();
  std::vector<float> v;
  float f;
};

// will not vectorise
void Foo::func3()
{
  // this->v.end() !!
  for(std::vector<float>::iterator it = v.begin(); it != v.end(); ++it)
  {
    *it *= f;  // this->f !!
  }
}

void Foo::func4()
{
  // you need to take a local copy of v.end(), and 'f'.
  const float temp = f;
  for(std::vector<float>::iterator it = v.begin(), e = v.end(); it != e; ++it)
  {
    *it *= temp;
  }
}

In the end, if it's something you care about, use the vectorisation reports from the compiler to fix up your code. As mentioned above, this is basically an issue of pointer aliasing. You can use the restrict keyword to help fix some of these issues (but I've found that applying restrict to 'this' is often not that useful).

Answer 5

Use range based for by default as it will give the compiler the most direct information to optimize (compiler knows it can cache the end iterator for example). Then profile and only optimize further if you identify a significant bottleneck. There will be very few real world situations where these different loop variants make a meaningful performance difference. Compilers are pretty good at loop optimization and it is far more likely that you should focus your optimization effort elsewhere (like choosing a better algorithm or focusing on optimizing the loop body).