为什么编译器不会在集合的元素上优化空的ranged-for循环？

Question

在测试我的代码时,我注意到当for loop删除空的范围时,执行时间显着增加.通常我会认为编译器会注意到for循环没有用处,因此会被忽略.作为编译器标志我正在使用-O3(gcc 5.4).我还使用向量而不是集合来测试它,这似乎可以工作并在两种情况下都给出相同的执行时间.似乎迭代器的增量花费了所有额外的时间.

第一种情况下,ranged for循环仍然存在(慢):

#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";
}

第二种情况,删除了范围for循环(快速):

#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

内部std::set迭代器使用某种指针链.这似乎是个问题.

以下是与您的问题类似的最小设置:

struct S
{
    S* next;
};

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

复杂的集合实现或迭代器的开销不是问题,而是优化器无法优化的指针链模式.

我不知道优化器在这种模式上失败的确切原因.

另请注意,此变体已经过优化:

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

编辑

正如@hvd所建议的那样,这可能与编译器无法证明循环不是无限有关.如果我们像这样编写OP循环:

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

编译器优化了一切.

Answer 2

基于for循环的范围并不像它看起来那么简单.它在编译器内部转换为基于迭代器的循环,如果迭代器足够复杂,标准甚至不允许编译器删除这些迭代器操作.

Answer 3

Range-for是"语法糖",意思是它所做的只是简单地为可以用更冗长的方式表达的东西提供简写符号.例如,range-for转换为类似的东西.

for (Type obj : container) - >

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

现在的问题是begin/end/*iter/++ iter /(obj =)是函数调用.为了优化它们,编译器需要知道它们没有副作用(改变为全局状态).编译器是否可以执行此操作是实现定义的,并且将取决于容器类型.但是我可以说,在大多数情况下你不需要(obj =)函数,所以更喜欢

for (const auto& X: cont) 

要么 ...

for (auto& X: cont)

至 ...

for (auto X : cont)

您可能会发现这样可以简化它以进行优化.

Answer 4

你可以玩clang优化报告.使用已编译的代码编译save-optimization-record,因此优化报告将被转储到main.opt.yaml.

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

你会发现循环有几个问题:

Clang认为,在这个循环中有一个值被修改.

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

此外,编译器无法计算循环迭代次数.

- String: could not determine number of loop iterations

请注意,编译器内联成功begin,end,operator++和operator=.