¿Qué es la técnica de inversión de bucle?

89

Estaba revisando un documento que habla sobre las técnicas de optimización del compilador Just -In-Time (JIT) para Java. Uno de ellos fue la "inversión de bucle". Y el documento dice:

Reemplaza un whilebucle regular con un do-whilebucle. Y el do-whilebucle se establece dentro de una ifcláusula. Este reemplazo conduce a dos saltos menos.

¿Cómo funciona la inversión de bucle y cómo optimiza nuestra ruta de código?

NB: Sería genial si alguien pudiera explicar con un ejemplo de código Java y cómo JIT lo optimiza al código nativo y por qué es óptimo en los procesadores modernos.

Molesto
fuente
2
No es algo que le haría a su código fuente. Ocurre a nivel de código nativo.
Marko Topolnik
2
@MarkoTopolnik lo sé. Pero quiero saber cómo JIT hace esto en el nivel de código nativo. Gracias.
Probar el
1
oh genial, hay una página de wikipedia sobre esto con muchos ejemplos en.wikipedia.org/wiki/Loop_inversion . El ejemplo de C es igualmente válido en Java.
Benjamin Gruenbaum
Hace algún tiempo, inspirado por una de las preguntas sobre SO, realicé una breve investigación sobre este asunto, tal vez los resultados le sean útiles: stackoverflow.com/questions/16205843/java-loop-efficiency/…
Adam Siemion
¿Es esto lo mismo que donde la condición de bucle generalmente se coloca al final (independientemente de si se realizarán menos saltos), solo para que haya menos instrucciones de salto (1 vs 2 por iteración)?
extremeaxe5

Respuestas:

108
while (condition) { 
  ... 
}

Flujo de trabajo:

  1. comprobar la condición;
  2. si es falso, salta al exterior del bucle;
  3. ejecutar una iteración;
  4. Saltar a la cima.

if (condition) do {
  ...
} while (condition);

Flujo de trabajo:

  1. comprobar la condición;
  2. si es falso, salte más allá del bucle;
  3. ejecutar una iteración;
  4. comprobar la condición;
  5. si es cierto, vaya al paso 3.

Comparando estos dos, puede ver fácilmente que el último puede no hacer ningún salto en absoluto, siempre que haya exactamente un paso a través del bucle, y generalmente el número de saltos será uno menos que el número de iteraciones. El primero tendrá que saltar hacia atrás para verificar la condición, solo para saltar fuera del ciclo cuando la condición sea falsa.

Los saltos en arquitecturas modernas de CPU con canalización pueden ser bastante costosos: como la CPU está terminando la ejecución de las comprobaciones antes del salto, las instrucciones posteriores a ese salto ya están en el medio del proceso. Todo este procesamiento debe descartarse si falla la predicción de la rama. La ejecución adicional se retrasa mientras se vuelve a cebar la tubería.

Explicando la predicción de bifurcación mencionada : para cada tipo de salto condicional, la CPU tiene dos instrucciones, cada una de las cuales incluye una apuesta sobre el resultado. Por ejemplo, colocaría una instrucción que diga " salte si no es cero, apostando a que no sea cero " al final de un ciclo porque el salto tendrá que realizarse en todas las iteraciones excepto en la última. De esa manera, la CPU comienza a bombear su canalización con las instrucciones que siguen al objetivo de salto en lugar de las que siguen la instrucción de salto en sí.

Nota IMPORTANTE

Por favor, no tome esto como un ejemplo de cómo optimizar a nivel de código fuente. Eso sería completamente equivocado ya que, como ya se desprende de su pregunta, la transformación del primer formulario al segundo es algo que el compilador JIT hace como una cuestión de rutina, completamente por sí solo.

Marko Topolnik
fuente
51
Esa nota al final es algo muy, muy importante de hecho.
TJ Crowder
2
@AdamSiemion: El do-whilecódigo de bytes generado para el código fuente dado es irrelevante, porque en realidad no lo escribimos. Escribimos el whilebucle y dejamos que el compilador y JIT conspiren para mejorarlo por nosotros (a través de la inversión del bucle) si es necesario.
TJ Crowder
1
@TJCrowder +1 para lo anterior, más la nota para Adam: nunca considere el código de bytes cuando piense en las optimizaciones del compilador JIT. Bytecode está mucho más cerca del código fuente de Java que del código compilado JIT real que se está ejecutando. De hecho, la tendencia en los lenguajes modernos es que el código de bytes no forme parte de la especificación del lenguaje.
Marko Topolnik
1
Hubiera sido más informativo que la Nota importante se explicara un poco más. ¿Por qué estaría completamente equivocado?
arsaKasra
2
@arsaKasra Es un error porque, en general, la legibilidad y la estabilidad triunfan sobre las optimizaciones en el código fuente. Especialmente con la revelación de que el JIT hace esto por usted, no debería intentar la (muy micro) optimización por su cuenta.
Radiodef
24

Esto puede optimizar un bucle que siempre se ejecuta al menos una vez.

Un whilebucle regular siempre saltará al principio al menos una vez y saltará al final una vez al final. Un ejemplo de un bucle simple que se ejecuta una vez:

int i = 0;
while (i++ < 1) {
    //do something
}  

Por do-whileotro lado, un bucle saltará el primer y último salto. Aquí hay un ciclo equivalente al anterior, que se ejecutará sin saltos:

int i = 0;
if (i++ < 1) {
    do {
        //do something
    } while (i++ < 1); 
}
Keppil
fuente
+1 por ser correcto y primero, considere agregar un ejemplo de código. Algo así como boolean b = true; while(b){ b = maybeTrue();}que boolean b;do{ b = maybeTrue();}while(b);debería ser suficiente.
Benjamin Gruenbaum
Sin preocupaciones. En cierto modo invalida la línea de apertura de la respuesta, fwiw. :-)
TJ Crowder
@TJ Bueno, todavía no optimizará un bucle que no se ingrese, habrá un salto en ambos casos.
Keppil
Ah, sí. Lo siento, estaba leyendo eso para significar que no se podía aplicar a bucles que no se repitieran al menos una vez (en lugar de que no los ayude). Contigo ahora. :-)
TJ Crowder
@Keppil Probablemente debería dejar explícito que en el caso de que tengamos una gran cantidad de iteraciones X, entonces solo guardaremos un solo salto entre las X.
Manuel Selva
3

Caminemos por ellos:

La whileversión:

void foo(int n) {
    while (n < 10) {
       use(n);
       ++n;
    }
    done();
}
  1. Primero probamos ny saltamos a done();si la condición no es verdadera.
  2. Luego usamos e incrementamos n.
  3. Ahora volvemos a la condición.
  4. Enjuague, repita.
  5. Cuando la condición ya no es cierta, saltamos a done().

La do-whileversión:

(Recuerde, en realidad no hacemos esto en el código fuente [que introduciría problemas de mantenimiento], el compilador / JIT lo hace por nosotros).

void foo(int n) {
    if (n < 10) {
        do {
            use(n);
            ++n;
        }
        while (n < 10);
    }
    done();
}
  1. Primero probamos ny saltamos a done();si la condición no es verdadera.
  2. Luego usamos e incrementamos n.
  3. Ahora probamos la condición y retrocedemos si es verdad.
  4. Enjuague, repita.
  5. Cuando la condición ya no es cierta, fluimos (no saltamos) a done().

Entonces, por ejemplo, si ncomienza siendo 9, nunca saltamos en la do-whileversión, mientras que en la whileversión tenemos que volver al principio, hacer la prueba y luego saltar al final cuando vemos que no es cierto. .

TJ Crowder
fuente
3

La inversión de bucle es una técnica de optimización del rendimiento que mejora el rendimiento ya que el procesador puede lograr el mismo resultado con menos instrucciones. Esto debería mejorar principalmente el rendimiento en condiciones de contorno.

Este enlace proporciona otro ejemplo de inversión de bucle. En algunas arquitecturas donde decrementar y comparar se implementan como un solo conjunto de instrucciones, tiene sentido convertir un bucle for a un tiempo con la operación de decremento y comparación.

Wikipedia tiene un muy buen ejemplo y lo vuelvo a explicar aquí.

 int i, a[100];
  i = 0;
  while (i < 100) {
    a[i] = 0;
    i++;
  }

será convertido por el compilador a

  int i, a[100];
  i = 0;
  if (i < 100) {
    do {
      a[i] = 0;
      i++;
    } while (i < 100);
  }

¿Cómo se traduce esto en rendimiento? Cuando el valor de i es 99, el procesador no necesita realizar un GOTO (que se requiere en el primer caso). Esto mejora el rendimiento.

Anirudhan J
fuente