Почему компилятор не оптимизирует пустой цикл диапазона для элементов набора?

При тестировании моего кода я заметил значительное увеличение времени выполнения, когда пустой ranged- for loop был удален или нет. Обычно я бы подумал, что компилятор заметил бы, что цикл for не имеет никакой цели, и поэтому его следует игнорировать. В качестве флагов компилятора я использую -O3 (gcc 5.4). Я также тестировал его с помощью вектора вместо набора и, похоже, работал и дал одинаковое время выполнения в обоих случаях. Похоже, что инкремент итератора стоит все дополнительное время.

Первый случай с диапазоном для цикла все еще присутствует (медленный):

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

Второй случай с удаленным диапазоном для цикла (быстрый):

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

Ответ 1

Внутренний std::set iterator использует некоторую цепочку указателей. Кажется, это проблема.

Ниже приведена минимальная настройка, аналогичная вашей проблеме:

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

Компилятор оптимизирует все.

Ответ 2

Диапазон, основанный на цикле, не такой тривиальный, как кажется. Он транслируется внутри цикла, основанного на итераторе, внутри компилятора, и если итератор достаточно сложный, компилятор может даже не разрешаться стандартом для удаления этих операций итератора.

Ответ 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)

Вы можете обнаружить, что это упрощает его для оптимизации.

Ответ 4

Вы можете поиграть с докладом о оптимизации кланов. Скомпилируйте свой код с save-optimization-record, поэтому отчет по оптимизации будет сбрасываться на main.opt.yaml.

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

Вы увидите, что в цикле есть несколько проблем:

Кланг считает, что в этом цикле есть значение.

- 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=.