Why doesn't the compiler optimize an empty ranged-for loop over the elements of a set?

Question

When testing my code I noticed a significant increase in execution time when the empty ranged-for loop was deleted or not. Normally I would think that the compiler would notice that the for loop serves no purpose and would therefor be ignored. As the compiler flags I am using -O3 (gcc 5.4). I also tested it with a vector instead of a set and that seems to work and give the same execution time in both cases. It seems that the incrementation of the iterator costs all the extra time.

First case with the ranged for loop still present (slow):

#include <iostream>
#include <set>
int main () {
    long result;
    std::set<double> results;
    for (int i = 2; i <= 10000; ++i) {
        results.insert(i);
        for (auto element : results) {
            // no operation
        }
    }
    std::cout << "Result: " << result << "\n";
}

Second case with the ranged for loop deleted (fast):

#include <iostream>
#include <set>
int main () {
    long result;
    std::set<double> results;
    for (int i = 2; i <= 10000; ++i) {
        results.insert(i);
    }
    std::cout << "Result: " << result << "\n";
}

Answer 1

Internally std::set iterator uses some kind of pointer chain. This seems to be the issue.

Here is a minimal setup similar to your issue:

struct S
{
    S* next;
};

void f (S* s) {
    while (s)
        s = s->next;
}

It's not a problem with complex collection implementations or overhead of iterators but simply this pointer chain pattern that the optimizer can't optimize.

I don't know the precise reason why optimizers fail on this pattern though.

Also, note that this variant is optimized away:

void f (S* s) {
    // Copy paste as many times as you wish the following two lines
    if(s)
        s = s->next;
}

Edit

As suggested by @hvd this might have to do with the compiler not being able to prove the loop is not infinite. And if we write the OP loop like so:

void f(std::set<double>& s)
{
    auto it = s.begin();
    for (size_t i = 0; i < s.size() && it != s.end(); ++i, ++it)
    {
        // Do nothing
    }
}

The compiler optimizes everything away.

Answer 2

The range based for loop is not as trivial as it looks. It is translated to an iterator-based loop internally in the compiler and if the iterator is complex enough the compiler may not even be allowed by the standard to remove these iterator operations.

Answer 3

Range-for is "syntactic sugar", meaning what it does is simply provide short-hand notation for something that can be expressed in more verbose manner. For example, range-for transforms into something like this.

for (Type obj : container) ->

auto endpos = container.end();
for ( auto iter=container.begin(); iter != endpos; ++iter)
{
     Type obj(*iter);
     // your code here
}

Now the problem is that begin/end/*iter/++iter/(obj = ) are function-calls. In order to optimize them out, the compiler needs to know that they have no side-effects, (changes to global state). Whether the compiler can do this or not is implementation defined, and will depend on the container type. What I can say though, in most case you do not need the (obj =) function, so prefer

for (const auto& X: cont) 

or ...

for (auto& X: cont)

to ...

for (auto X : cont)

You might find that simplifies it enough for optimizations to kick in.

Answer 4

You could play around with clang optimization report. Compile your code with save-optimization-record enabled, so optimization report will be dumped to main.opt.yaml.

clang++ -std=c++11 main.cpp -O2 -fsave-optimization-record

---

You will see that there are several problems with the loop:

Clang thinks, that there is a value modified in this loop.

- String: value that could not be identified as reduction is used outside the loop

Also, the compiler can't compute the number of loop iterations.

- String: could not determine number of loop iterations

Note, that compiler successfully inlined begin, end, operator++ and operator=.