现代编译器能否展开使用begin和end迭代器表示的`for`循环

Question

请考虑以下代码

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

像g ++,clang ++,icc这样的编译器是否能够像这样展开循环.不幸的是,我不知道汇编能够从输出验证循环是否展开.(我只能访问g ++.)

对我来说,这似乎需要代表编译器比平常更聪明,首先推断迭代器是一个随机访问迭代器,然后计算循环执行的次数.编译器可以在启用优化时执行此操作吗？

感谢您的回复,在您开始讲授过早优化之前,这是一个好奇心的练习.

Answer 1

我建议无论编译器是否能够使用现代流水线架构和缓存来展开循环,除非你的"做的东西"是微不足道的,否则这样做几乎没有什么好处,并且在很多情况下这样做会改为性能HIT而不是恩惠 如果你的"做东西"不重要,展开循环将创建这个非平凡代码的多个副本,这将花费额外的时间加载到缓存中,从而显着减慢通过展开循环的第一次迭代.同时,它将从缓存中驱逐更多代码,如果它进行任何函数调用,这可能是执行"do stuff"所必需的,然后需要再次将其重新加载到缓存中.在无缓存流水线非分支预测体系结构之前,展开循环的目的非常有意义,其目标是减少与循环逻辑相关的开销.现在使用基于缓存的流水线分支预测硬件,当你检测到i == end退出条件时,你的cpu将被流水线化到下一个循环迭代,再次推测性地执行循环代码,此时处理器将抛出最后推测执行的结果集.在这样的架构中,循环展开很有意义.这将进一步膨胀代码几乎没有任何好处.

Answer 2

对我来说,这似乎需要代表编译器比平常更聪明,首先推断迭代器是一个随机访问迭代器,然后计算循环执行的次数.

STL完全由模板组成,具有所有代码inline.因此,当编译器开始应用优化时,随机访问迭代器已经减少为指针.创建STL的原因之一是程序员不需要智胜编译器.你应该依靠STL来做正确的事情,直到证明不是这样.

当然,你仍然需要从STL中选择合适的工具来使用......

编辑:有关于是否g++有任何循环展开的讨论.在我使用的版本,循环展开不是的一部分-O,-O2或者-O3,我也得到相同的组件,后者的水平用下面的代码:

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++;
    }
}

使用相应的装配-O2组件:

_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

随着-funroll-loops选项添加的功能扩展到很多东西要大得多.但是,文档警告这个选项:

展开循环,其迭代次数可在编译时或进入循环时确定.-funroll-loops意味着-frerun-cse-after-loop.它还打开完全循环剥离(即完全去除具有小的恒定迭代次数的循环).此选项使代码变大,可能会也可能不会使代码运行得更快.

作为阻止你自己展开循环的另一个论点,我将完成这个答案,并附上将Duff设备应用于上述foo函数的说明:

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还有另一个循环优化标志:

-ftree-loop-optimize
在树上执行循环优化.默认情况下,此标志启用为-O更高.

此选项为最内层循环启用简单循环优化,包括具有固定迭代次数的循环的完整循环展开(剥离).(感谢doc向我指出这一点.)