What factors make iterators so slow in debug mode (VC++ 2012)

Question

I've got a vector of 10000 random numbers (mod 100) and I'd like to count how many pairs of two of those numbers sum to 100. I've written the following:

auto noPairsSumTo100 = 0;
const auto itEnd = end(myNums);
for (auto it1 = begin(myNums); it1 != itEnd ; ++it1) {
  for (auto it2 = it1; it2 != itEnd ; ++it2) {
    if (*it1 + *it2 == 100) {
      noPairsSumTo100 ++;
    }
  }
}

On my machine this takes about 21.6 seconds to run in debug mode. If I set _ITERATOR_DEBUG_LEVEL=0 (which sets both _SECURE_SCL and _HAS_ITERATOR_DEBUGGING to 0) the execution time is reduced to ~9.5 seconds. Replacing the != comparisons with < reduces the time further to ~8.5 seconds.

If I implement the same algorithm by indexing the vectors like this:

auto noPairsSumTo100 = 0;
const auto itEnd = end(myNums);
for (auto index1 = 0; index1 < noTerms; ++index1) {
  for (auto index2 = index1; index2 < noTerms; ++index2) {
    if (myNums[index1] + myNums[index2] == 100) {
      noPairsSumTo100 ++;
    }
  }
}

It takes about 2.1 seconds to run in debug mode. I think this is as close as I can make the algorithms aside from iterator usage. My question is, what makes the first implementation take ~4 times longer than the second?

Note, both versions of the algorithm take about 34 milli-seconds to run in release mode, so the difference is optimised out.

Answer 1

Bounds checking aside, debug builds of STL code produces an insane amount of function calls. Some innocent lines like:

if (a.empty())

can produce as much as 8 (or more) function calls. Some (all?) STL implementations are not optimized for debug builds at all.

A common performance issue with STL is that devs think that function inlining always works. It doesn't. If too many inline functions are called the bottom ones do not get inlined and you have a massive performance hit just by the function calls overhead. This is very common when having containers of containers:

map< string, map< int, string>>

operations on the outer map can cause inline functions to stay as normal functions.