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.