Estamos acostumbrados a hacer los bucles en forma ascendente, lo cual es conveniente en muchos casos.
En otros en cambio, podemos recorrerlos de mayor a menor. Pero, ¿qué ventaja nos daría hacerlo así?
Muy sencillo, de eficiencia. Los bucles descendentes, suelen ser más eficientes que los ascendentes. En particular lo son en estos dos casos:
1) La expresión de inicio es más sencilla que la de fin.
Es el caso más habitual, reescribiéndolo para que vaya de fin hasta inicio, se evita tener que reevaluar una condición complicada en cada iteración.
Es mejor:
for (i=strlen(a); i>0; i–)
que
for (i=0; i<strlen(a); i++)
Ya que nos ahorramos tener que llamar a strlen(a) 100 veces.
2) El comienzo del bucle es 0.
Las arquitecturas x86 y x64, permiten averiguar si un registro vale cero al decrementarlo, sin necesidad de compararlo, ya que se ha activado el flag ZF (zero flag).
El siguiente bucle:
unsigned int i;
for (i=0; i<100; i++)
{
}
Se transformaría a:
xor esi, esi
$L9621:
inc esi
cmp esi, 100
jb SHORT $L9621
En cambio, reescrito descendentemente, el código C:
unsigned int i;
for (i=100; i>0; i–)
{
}
Se compilaría a:
mov esi, 100
$L9621:
dec esi
jne SHORT $L9621
Como podemos ver, hemos evitado tener que ejecutar la instrucción cmp. Por lo que los beneficios crecen en progresión aritmética con el tamaño del bucle.
Estas ventajas son válidas para cualquier lenguaje de programación, siendo más eficaces cuanto más cercano esté el lenguaje a la máquina.
muy buena, he interesante puntualizacion… la tendre encuenta a partir de ahora 🙂
Hmmm… nunca había pensado lo delos bucles inversos para evitar llamar a la strlen(a) x veces.
Lo que se me ocurre es crear una variable para guardar el valor de strlen(a), me gustaría pensar que esto es más eficiente que llamar a strlen(a) x veces.
muy bueno el post, sabía lo de no usar funciones en los for{} pero no tenia idea de la importancia del uso de los decrementos .
for (i=0; i<strlen(a); i++)Mmmmmm… Horroroso. Evaluar en cada bucle strlen es una aberración salvaje. En ese caso se debería utilizar una variable temporal (aunque es previsible que el compilador lo haga automáticamente cuando se compile de forma optimizada).
Otro motivo para los bucles descendentes: utilizar uno de los parámetros recibidos en la función como variable de bucle:
void hazAlgo(char *p,int count)
{
for(;count!=0;count–)
{
//haz algo
}
}
O mejor aún:
void hazAlgo(char *p,int count)
{
while(count–)
{
//haz algo
}
}
En este último caso, un compilador usará count y la decrementará en la llave de cierre del bucle, pero si no lo hace, pues un bucle do…while.
En efecto crear una variable temporal, solventaría el problema en este caso concreto, aunque a poco decente que sea el compilador, el mismo lo haría (common subexpressions).
En algunos lenguajes como Pascal hay palabras reservadas para estos menesteres…
for i:=0 to 10 do …
for i:=10 downto 0 do …
Aunque lo de comparar cada vez con strlen(a) es una aberración 🙂
Como ya han dicho por aquí arriba, el problema del strlen() se solventaría con guardar el valor en una variable. Además de cualquier compilador decente lo hará por el mismo en las optimizaciones. Ya que el resultado de la llamada quedará en una variable temporal del compilador (terceto, cuarteto, da igual) y se hará referencia a la variable y no se volverá a llamar.
En cuanto a los bucles descendentes, creo que por ahorrar una comparación como dices con el flag ZF, estás provocando muchos más fallos de caché. Puesto que el "prefetch" de la cache se hace hacia delante y no hacia atrás. Como con este método se recorre la memoria en posiciones negativas los bloques que se hayan pillado por adelantado no van a servir de nada. Y por tanto se tendrán que cargar de nuevo. Mucho más lento que hacer una comprobación que se hace en un ciclo de reloj.
Pero todo es hacer un pequeño programita para comprobar si es cierto o no. 😉
Alguna vez he tenido conversaciones con los profesores a efecto de esto, y siempre me han dicho lo mismo:
«Cuando programes en ensamblador, tenlo en cuenta, pero si lo haces en alto nivel ni lo intentes. El compilador se encarga de todo y muchas veces si intentas optimizar tú el código lo que haces es liarlo más»
Ahí queda eso XD
Personalmente no me fío de las opiniones de la mayoría de los profesores…
Después de la asignatura de compiladores llegué a la conclusion que el compilador hace el 90% del trabajo si hablamos de optimización. En el caso del strlen debería almacenarlo en un registro para optimizar los accesos y hacerlo al revés supondría que perderíamos todos los sistemas de cache.
Sin embargo, en C/C++ es posible optimizar ese bucle indicandole al compilador que almacene el contador en registro:
for (register int i=0; i < strlen(cadena; i++) { ... }Las mayore mejoras se obtienen al recorrer matrices cuando se aplican la técnica de intercambio de bucles. Me explico ¿Es más eficiente recorrer la matriz por filas o por columnas?. Lo normal es recorrer los indices tal y como se almacenan en memoria por lo que cobran sentido las cachés utilizadas.
Al menos a partir del Visual C++ 6, y en general en la mayoría de compiladores recientes, la palabra clave register es simplemente ignorada, siendo el propio optimizador el que decide lo que meter en registros de la CPU, y lo que no.
Respecto a la importancia del orden de recorrido en las matrices estoy totalmente de acuerdo.
Otra técnica que no se ha mencionado, y a la que le dedicaré algún futuro artículo, que sin duda afecta a las prestaciones de los bucles, es el desenrrollado.
Sabía que la palabra register era una simple indicación que el compilador podría o no usar pero desconocía que los compiladores modernos la ignoraran.
En cuanto al artículo de desenrrollado de bucles a ver con qué nos sorprendes, porque sólo lo he visto en ensamblador puro nunca para lenguajes de más alto nivel. Y hablando de técnicas de optimización se nos ha olvidado por completo una de las más sencillas y eficaces que se usa en combinación con prácticamente todas las demás: el reemplazo escalar.
No estoy de acuerdo con lo de poner los bucles descendentes. Creo que el código se entiende peor (sobre todo si se usa el índice para llevar a cabo un algoritmo complejo) y prefiero sacrificar algo de eficacia (que no tengo yo muy claro que se gane tanto) a cambio de ganar claridad.
Epaminondas Pantulis, quizás sea cuestión de acostumbrarse. Creo que es igual de legible algo que va de 0-100 que algo que va de 100-0. En ambos casos se hace 100 veces.
Otra cuestión sería que para hacerlo descendente, dentro del cuerpo del bucle, hiciéramos "operaciones tramposas" del estilo 100-i, …