matrices - pildorasinformaticas java array

¿Cuál es la técnica de inversión de bucle?

Question

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 "inversión de bucle". Y el documento dice:

Reemplaza un ciclo while normal con un ciclo do-while while. Y el ciclo do-while while se establece dentro de una cláusula if . Este reemplazo lleva a dos saltos menos.

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

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

Answer 1

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

Un ciclo while regular siempre volverá al inicio al menos una vez y saltará al final una vez al final. Un ejemplo de bucle simple que se ejecuta una vez:

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

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

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

Answer 2

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 para la inversión de bucle. En algunas arquitecturas donde la reducción y la comparación se implementan como un solo conjunto de instrucciones, tiene sentido convertir un bucle for a while con decremento y operación de comparación.

Wikipedia tiene un muy buen ejemplo y lo estoy explicando aquí de nuevo.

 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.

Answer 3

Vamos a caminar a través de ellos:

La versión while :

void foo(int n) {
    while (n < 10) {
       use(n);
       ++n;
    }
    done();
}

1. Primero probamos n y 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 versión do-while :

(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 n y 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 n comienza siendo 9 , nunca saltamos en absoluto en la versión do-while , mientras que en la versión while tenemos que volver al principio, hacer la prueba y luego saltar al final cuando ver que no es verdad

Answer 4

while (condition) { 
  ... 
}

Flujo de trabajo:

1. condición de verificación;
2. si es falso, salta fuera del ciclo;
3. ejecutar una iteración;
4. saltar a la cima

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

Flujo de trabajo:

1. condición de verificación;
2. si es falso, salta al más allá del círculo;
3. ejecutar una iteración;
4. condición de verificación;
5. si es verdadero, salta al paso 3.

Comparando estos dos, puede ver fácilmente que este último no puede hacer ningún salto, siempre que haya exactamente un paso en el ciclo, y generalmente el número de saltos será uno menos que el número de iteraciones. El primero tendrá que retroceder para verificar la condición, solo para saltar fuera del circuito cuando la condición es falsa.

Los saltos en las arquitecturas de CPU con tuberías modernas pueden ser bastante caros: como la CPU está terminando la ejecución de las comprobaciones antes del salto, las instrucciones más allá de ese salto ya están en el medio de la tubería. Todo este procesamiento debe descartarse si la predicción de bifurcación falla. Se retrasa la ejecución adicional mientras se reprime 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 al resultado. Por ejemplo, pondría una instrucción que diga " saltar si no es cero, apostando a no cero " al final de un ciclo porque el salto tendrá que hacerse en todas las iteraciones, excepto en la última. De esta forma, la CPU comienza a bombear su tubería con las instrucciones que siguen al objetivo de salto en lugar de seguir la instrucción de salto en sí.

Nota IMPORTANTE

Por favor, no tome esto como un ejemplo de cómo optimizar en el nivel del código fuente. Eso sería totalmente erróneo ya que, como ya se desprende de su pregunta, la transformación de la primera forma a la segunda es algo que el compilador JIT hace como una cuestión de rutina, completamente por sí mismo.