Pourquoi le compilateur n'optimise-t-il pas une boucle vide sur les éléments d'un ensemble ?

Question

En testant mon code, j'ai remarqué une augmentation significative du temps d'exécution lorsque le rang vide- for loop a été supprimé ou non. Normalement, j'aurais pensé que le compilateur aurait remarqué que la boucle for ne sert à rien et qu'elle serait donc ignorée. Comme les drapeaux du compilateur que j'utilise -O3 ( gcc 5.4 ). Je l'ai également testé avec un vecteur au lieu d'un ensemble et cela semble fonctionner et donner le même temps d'exécution dans les deux cas. Il semble que l'incrémentation de l'itérateur coûte tout le temps supplémentaire.

Premier cas avec la boucle for rangée toujours présente (lente) :

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

Deuxième cas avec la boucle for rangée supprimée (rapide) :

#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

En interne std::set L'itérateur utilise une sorte de chaîne de pointeurs. Cela semble être le problème.

Voici une configuration minimale similaire à votre problème :

struct S
{
    S* next;
};

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

Il ne s'agit pas d'un problème d'implémentation complexe de collections ou de surcharge des itérateurs, mais simplement de ce modèle de chaîne de pointeurs que l'optimiseur ne peut pas optimiser.

Je ne connais pas la raison précise pour laquelle les optimiseurs échouent sur ce modèle.

Notez également que cette variante est optimisée :

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

Modifier

Comme suggéré par @hvd, cela pourrait être dû au fait que le compilateur n'est pas capable de prouver que la boucle n'est pas infinie. Et si nous écrivons la boucle OP comme ceci :

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

Le compilateur optimise tout.

Answer 2

La boucle for basée sur l'intervalle n'est pas aussi triviale qu'il n'y paraît. Elle est traduite en une boucle basée sur un itérateur en interne dans le compilateur et si l'itérateur est suffisamment complexe, le compilateur peut même ne pas être autorisé par la norme à supprimer ces opérations sur l'itérateur.

Answer 3

Range-for est un "sucre syntaxique", ce qui signifie qu'il fournit simplement une notation abrégée pour quelque chose qui peut être exprimé de manière plus verbeuse. Par exemple, range-for se transforme en quelque chose comme ceci.

for (Type obj : container) ->

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

Le problème est que begin/end/*iter/++iter/(obj = ) sont des appels de fonction. Afin de les optimiser, le compilateur doit savoir qu'ils n'ont pas d'effets secondaires (changements de l'état global). Le fait que le compilateur puisse le faire ou non est défini par l'implémentation, et dépendra du type de conteneur. Ce que je peux dire, c'est que dans la plupart des cas, vous n'avez pas besoin de la fonction (obj =).

for (const auto& X: cont) 

ou ...

for (auto& X: cont)

à ...

for (auto X : cont)

Vous constaterez peut-être que cela simplifie suffisamment les choses pour que les optimisations se mettent en place.

Answer 4

Vous pouvez jouer avec clang rapport d'optimisation. Compilez votre code avec save-optimization-record activé, de sorte que le rapport d'optimisation sera transféré dans le fichier main.opt.yaml .

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

---

Vous verrez qu'il y a plusieurs problèmes avec la boucle :

Clang pense, qu'il y a une valeur modifiée dans cette boucle.

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

De plus, le compilateur ne peut pas calculer le nombre d'itérations de la boucle.

- String: could not determine number of loop iterations

Notez, que le compilateur a réussi à inliner begin , end , operator++ et operator= .