¿Qué configuración de bucle tardará más tiempo en ejecutarse?

Question

Código I:

for(i=0; i<100; i++){ 
    for(j=0; j<1000; j++){ 
    x = y; 
    } 
} 

Código II:

for(i=0; i<1000; i++){ 
    for(j=0; j<100; j++){ 
    x = y; 
    } 
} 

Puede explicar por qué una de estas configuraciones del bucle tendrá más tiempo para ejecutar que el otro?

Answer 1

Esto realmente depende de múltiples factores, todos fuera de su control directo.

Como dice user David V en los comentarios, ambos serán eliminados por un buen compilador. Entonces, si no lo son, se traducirán en un código de máquina con instrucciones de bifurcación. Cuando un procesador ejecuta código con bifurcación, utiliza la llamada predicción de bifurcación especulativa que se comporta de manera diferente según las instrucciones exactas en las que se traduce el código. Pueden aparecer otros factores, como por ejemplo, falta de código de caché. Realmente no se puede decir hasta que mida cuidadosamente y analice a fondo los resultados.

Answer 2

Una buena respuesta es probablemente: ambas son maneras ineficaces de encontrar algo en una matriz bidimensional, y usted debe intentar algún tipo de indexación para eliminarlo.

Esta fue una pregunta de la entrevista, ¿verdad? Bueno, espere una respuesta de entrevista :)

Answer 3

En general, el bucle interno tiene grandes posibilidades de caber completamente en la memoria caché, por lo que el 100 de 1000 debe ser más rápido. Sin embargo, los compiladores son tan inteligentes ...

Answer 4

Debo señalar que cualquier buen compilador, pero no tan bueno como se mencionó anteriormente por David, compilará esto a varias instrucciones de la CPU, y tendrá hay necesidad de ramificación, o cualquiera de esa lógica de predicción de sucursal que ayuda a evitar los puestos de tuberías.

De hecho, hay una construcción de nivel de CPU trivial (la instrucción de bucle) que hará lo anterior utilizando una emulación de software mínima. Como tal, la multiplicación es conmutativa, por lo que 100x1000 o 1000x100 es lo mismo.

Answer 5

Si bien todas las respuestas son generalmente correctas, en mi opinión. A saber, se optimizaría y dependería del código de máquina, etc. Creo que en el caso más simplista, suponiendo que no hay optimización y no hay ramificaciones especulativas (que pueden no ser realistas), el Código 1 sería más rápido porque allí es una cierta cantidad de sobrecarga en la configuración de los bucles. A saber, debe declarar las variables i y J. Como la sobrecarga del bucle externo siempre ocurre una sola vez, el bucle interno es el factor real aquí. Dado que en el Código 1, el bucle interno solo se configura 100 veces y en el Código 2, el bucle interno se configura 1000 veces, el Código 1 debería ser más rápido. Una vez más, este es el caso más simple, que es probablemente lo que la pregunta de la entrevista o pregunta del cuestionario estaba buscando.