c++ - unitario - ¿Por qué el compilador no optimiza un bucle de rangos vacío sobre los elementos de un conjunto?

subconjunto

Question

Al probar mi código, noté un aumento significativo en el tiempo de ejecución cuando se eliminó o no el for loop vacío de rango. Normalmente, creo que el compilador se daría cuenta de que el bucle for no sirve para nada y por lo tanto sería ignorado. Como el compilador señala, estoy usando -O3 ( gcc 5.4 ). También lo probé con un vector en lugar de un conjunto y parece que funciona y da el mismo tiempo de ejecución en ambos casos. Parece que el incremento del iterador cuesta todo el tiempo extra.

Primer caso con el rango para el bucle todavía presente (lento):

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

Segundo caso con el rango de bucle eliminado (rápido):

#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

El rango basado en bucle no es tan trivial como parece. Se traduce internamente en un bucle basado en iterador en el compilador y, si el iterador es lo suficientemente complejo, es posible que el estándar ni siquiera permita que el compilador elimine estas operaciones de iterador.

Answer 2

Internamente std::set iterator usa algún tipo de cadena de punteros. Este parece ser el problema.

Aquí hay una configuración mínima similar a su problema:

struct S
{
    S* next;
};

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

No es un problema con implementaciones de recopilación complejas o sobrecarga de iteradores, sino simplemente este patrón de cadena de punteros que el optimizador no puede optimizar.

Sin embargo, no sé la razón precisa por la que los optimizadores fallan en este patrón.

Además, tenga en cuenta que esta variante está optimizada de distancia:

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

Editar

Como lo sugiere @hvd, esto podría tener que ver con que el compilador no pueda probar que el bucle no es infinito. Y si escribimos el bucle OP así:

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

El compilador optimiza todo lo lejos.

Answer 3

Range-for es "azúcar sintáctica", es decir, lo que hace es simplemente proporcionar una notación corta para algo que puede expresarse de manera más detallada. Por ejemplo, rango-para se transforma en algo como esto.

for (Type obj : container) ->

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

Ahora el problema es que begin / end / * iter / ++ iter / (obj =) son llamadas de función. Para poder optimizarlos, el compilador debe saber que no tienen efectos secundarios (cambios en el estado global). Si el compilador puede hacer esto o no, la implementación está definida y dependerá del tipo de contenedor. Sin embargo, lo que puedo decir es que en la mayoría de los casos no necesita la función (obj =), así que prefiera

for (const auto& X: cont) 

o ...

for (auto& X: cont)

a ...

for (auto X : cont)

Podría encontrar que eso lo simplifica lo suficiente como para que las optimizaciones se activen.

Answer 4

Usted podría jugar con el informe de optimización de Clang . Compile su código con el save-optimization-record habilitado, por lo que el informe de optimización se main.opt.yaml a main.opt.yaml .

clang++ -std=c++11 main.cpp -O2 -fsave-optimization-record Verás que hay varios problemas con el bucle:

Clang piensa que hay un valor modificado en este bucle.

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

Además, el compilador no puede calcular el número de iteraciones de bucle.

- String: could not determine number of loop iterations

Tenga en cuenta que el compilador con éxito en línea begin , end , operator++ y operator= .