Can modern compilers unroll `for` loops expressed using begin and end iterators

Question

Consider the following code

 vector<double> v;
 // fill v
 const vector<double>::iterator end =v.end();
 for(vector<double>::iterator i = v.bgin(); i != end; ++i) {
   // do stuff
 }

Are compilers like g++, clang++, icc able to unroll loops like this. Unfortunately I do not know assembly to be able verify from the output whether the loop gets unrolled or not. (and I only have access to g++.)

To me it seems that this will require more smartness than usual on behalf of the compiler, first to deduce that the iterator is a random access iterator, and then figure out the number of times the loop is executed. Can compilers do this when optimization is enabled ?

Thanks for your replies, and before some of you start lecturing about premature optimization, this is an excercise in curiosity.

Answer 1

I would propose that whether or not the compiler CAN unroll the loop, with modern pipelined architectures and caches, unless your "do stuff" is trivial, there is little benefit in doing so, and in many cases doing so would be a performance HIT instead of a boon. If your "do stuff" is nontrivial, unrolling the loop will create multiple copies of this nontrivial code, which will take extra time to load into the cache, significantly slowing down the first iteration through the unrolled loop. At the same time, it will evict more code from the cache, which may have been necessary for performing the "do stuff" if it makes any function calls, which would then need to be reloaded into the cache again. The purpose for unrolling loops made a lot of sense before cacheless pipelined non-branch-predictive architectures, with the goal being to reduce the overhead associated with the loop logic. Nowadays with cache-based pipelined branch-predictive hardware, your cpu will be pipelined well into the next loop iteration, speculatively executing the loop code again, by the time you detect the i==end exit condition, at which point the processor will throw out that final speculatively-executed set of results. In such an architecture, loop unrolling makes very little sense. It would further bloat code for virtually no benefit.

Answer 2

To me it seems that this will require more smartness than usual on behalf of the compiler, first to deduce that the iterator is a random access iterator, and then figure out the number of times the loop is executed.

The STL, being comprised entirely of templates, has all the code inline. So, random access iterators reduce to pointers already when the compiler begins to apply optimizations. One of the reasons the STL was created was so that there would be less need for a programmer to outwit the compiler. You should rely on the STL to do the right thing until proven otherwise.

Of course, it is still up to you to choose the proper tool from the STL to use...

Edit: There was discussion about whether g++ does any loop unrolling. On the versions that I am using, loop unrolling is not part of -O, -O2, or -O3, and I get identical assembly for the latter two levels with the following code:

void foo (std::vector<int> &v) {
    volatile int c = 0;
    const std::vector<int>::const_iterator end = v.end();
    for (std::vector<int>::iterator i = v.begin(); i != end; ++i) {
        *i = c++;
    }
}

With the corresponding assembly -O2 assembly:

_Z3fooRSt6vectorIiSaIiEE:
.LFB435:
        movq    8(%rdi), %rcx
        movq    (%rdi), %rax
        movl    $0, -4(%rsp)
        cmpq    %rax, %rcx
        je      .L4
        .p2align 4,,10
        .p2align 3
.L3:
        movl    -4(%rsp), %edx
        movl    %edx, (%rax)
        addq    $4, %rax
        addl    $1, %edx
        cmpq    %rax, %rcx
        movl    %edx, -4(%rsp)
        jne     .L3
.L4:
        rep
        ret

With the -funroll-loops option added, the function expands into something much much larger. But, the documentation warns about this option:

Unroll loops whose number of iterations can be determined at compile time or upon entry to the loop. -funroll-loops implies -frerun-cse-after-loop. It also turns on complete loop peeling (i.e. complete removal of loops with small constant number of iterations). This option makes code larger, and may or may not make it run faster.

As a further argument to dissuade you from unrolling loops yourself, I'll finish this answer with an illustration of applying Duff's Device to the foo function above:

void foo_duff (std::vector<int> &v) {
    volatile int c = 0;
    const std::vector<int>::const_iterator end = v.end();
    std::vector<int>::iterator i = v.begin();
    switch ((end - i) % 4) do {
    case 0: *i++ = c++;
    case 3: *i++ = c++;
    case 2: *i++ = c++;
    case 1: *i++ = c++;
    } while (i != end);
}

---

GCC has another loop optimization flag:

-ftree-loop-optimize
Perform loop optimizations on trees. This flag is enabled by default at -O and higher.

So, the -O option enables simple loop optimizations for the innermost loops, including complete loop unrolling (peeling) for loops with a fixed number of iterations. (Thanks to doc for pointing this out to me.)