vivo - ¿Es más rápido realizar una cuenta atrás que contar?

tiempo regresivo 1 minuto

Question

Nuestro profesor de informática dijo una vez que, por alguna razón, es más eficiente contar hacia abajo que contar hacia arriba. Por ejemplo, si necesita usar un bucle FOR y el índice de bucle no se utiliza en algún lugar (como imprimir una línea de N * a la pantalla) me refiero a un código como este:

for (i = N; i >= 0; i--)
putchar(''*'');

es mejor que:

for (i = 0; i < N; i++)
putchar(''*'');

¿Es realmente cierto? Y si es así, ¿alguien sabe por qué?

Answer 1

¿Es más rápido contar hacia abajo que hacia arriba?

Tal vez. Pero mucho más del 99% de las veces no importará, por lo que debe usar la prueba más "sensible" para terminar el ciclo, y por sensato, quiero decir que requiere la menor cantidad de pensamiento por parte del lector para descifrar qué está haciendo el ciclo (incluido lo que lo detiene). Haga que su código coincida con el modelo mental (o documentado) de lo que está haciendo el código.

Si el bucle está funcionando es una forma ascendente a través de una matriz (o lista, o lo que sea), un contador creciente a menudo coincidirá mejor con la forma en que el lector está pensando en lo que está haciendo el bucle - codifique su bucle de esta manera.

Pero si está trabajando en un contenedor que tiene N elementos y está eliminando los elementos a medida que avanza, podría tener más sentido cognitivo bajar el contador.

Un poco más de detalle sobre el ''quizás'' en la respuesta:

Es cierto que en la mayoría de las arquitecturas, probar un cálculo que dé como resultado cero (o pasar de cero a negativo) no requiere instrucciones de prueba explícitas; el resultado se puede verificar directamente. Si desea probar si un cálculo da como resultado algún otro número, la secuencia de instrucciones generalmente tendrá que tener una instrucción explícita para probar ese valor. Sin embargo, especialmente con CPU modernas, esta prueba normalmente agregará menos tiempo de nivel de ruido a una construcción de bucle. Particularmente si ese bucle está realizando E / S.

Por otro lado, si realiza la cuenta atrás desde cero y usa el contador como un índice de matriz, por ejemplo, puede encontrar que el código funciona en contra de la arquitectura de memoria del sistema: las lecturas de memoria a menudo causan que un caché ''mire hacia adelante'' varias ubicaciones de memoria más allá de la actual en anticipación de una lectura secuencial. Si está trabajando hacia atrás a través de la memoria, es posible que el sistema de almacenamiento en caché no anticipe lecturas de una ubicación de memoria en una dirección de memoria inferior. En este caso, es posible que el bucle ''hacia atrás'' pueda perjudicar el rendimiento. Sin embargo, aún así probablemente codificaría el ciclo de esta manera (siempre que el rendimiento no se convierta en un problema) porque la corrección es primordial, y hacer que el código coincida con un modelo es una gran manera de ayudar a garantizar la corrección. El código incorrecto es tan desoptimizado como puede obtener.

Así que tendería a olvidar el consejo del profesor (por supuesto, no en su prueba, sin embargo, debería ser pragmático en lo que respecta al aula), a menos y hasta que el funcionamiento del código importara realmente.

Answer 2

¿Es realmente cierto? y si es así, ¿alguien sabe por qué?

En la antigüedad, cuando las computadoras todavía se salían de la sílice fundida a mano, cuando los microcontroladores de 8 bits deambulaban por la Tierra, y cuando tu profesor era pequeño (o el maestro de tu profesor era pequeño), había una instrucción común llamada decremento y omisión. si es cero (DSZ). Los programadores ensambladores de Hotshot usaron esta instrucción para implementar bucles. Las máquinas posteriores obtuvieron instrucciones más elegantes, pero todavía había bastantes procesadores en los que era más barato comparar algo con cero que comparar con cualquier otra cosa. (Es cierto incluso en algunas máquinas RISC modernas, como PPC o SPARC, que reservan un registro completo para que siempre sea cero).

Entonces, si ajusta sus bucles para comparar con cero en lugar de N , ¿qué podría pasar?

• Puede guardar un registro
• Puede obtener una instrucción de comparación con una codificación binaria más pequeña
• Si ocurre una instrucción previa para configurar un indicador (probablemente solo en máquinas de la familia x86), es posible que ni siquiera necesite una instrucción de comparación explícita

¿Es probable que estas diferencias den lugar a una mejora mensurable en los programas reales en un procesador fuera de servicio moderno? Altamente improbable. De hecho, me impresionaría si pudiera mostrar una mejora mensurable incluso en un microbenchmark.

Resumen: ¡Golpeo a tu profesor con la cabeza! No deberías estar aprendiendo pseudo-hechos obsoletos sobre cómo organizar bucles. Debería estar aprendiendo que lo más importante de los bucles es asegurarse de que finalicen , produzcan respuestas correctas y sean fáciles de leer . Me gustaría que tu profesor se centrara en las cosas importantes y no en la mitología.

Answer 3

Chelín,

No hasta que esté haciendo microoptimizaciones, en ese momento tendrá a mano el manual de su CPU. Además, si estuvieras haciendo ese tipo de cosas, probablemente no necesitarías hacer esta pregunta de todos modos. :-) Pero, su profesor evidentemente no se suscribe a esa idea ...

Hay 4 cosas a considerar en su ejemplo de bucle:

for (i=N;
i>=0; //thing 1
i--) //thing 2
{
putchar(''*''); //thing 3
}

• Comparación

La comparación es (como han indicado otros) relevante para arquitecturas de procesador particulares. Hay más tipos de procesadores que aquellos que ejecutan Windows. En particular, puede haber una instrucción que simplifique y acelere las comparaciones con 0.

• Ajuste

En algunos casos, es más rápido ajustar hacia arriba o hacia abajo. Típicamente, un buen compilador lo resolverá y rehará el ciclo si puede. Sin embargo, no todos los compiladores son buenos.

• Loop Body

Estás accediendo a un syscall con putchar. Eso es masivamente lento. Además, estás renderizando en la pantalla (indirectamente). Eso es aún más lento. Piensa en una relación de 1000: 1 o más. En esta situación, el cuerpo del bucle supera por completo el costo del ajuste / comparación del bucle.

• Cachés

Un diseño de caché y memoria puede tener un gran efecto en el rendimiento. En esta situación, no importa. Sin embargo, si estuviera accediendo a una matriz y necesitara un rendimiento óptimo, le incumbiría investigar cómo accede su compilador y su procesador a los accesos de memoria y ajustar su software para sacar el máximo provecho de eso. El ejemplo de stock es el dado en relación con la multiplicación de matrices.

Answer 4

Cuente hacia abajo más rápido en caso como este:

for (i = someObject.getAllObjects.size(); i >= 0; i--) {…}

porque someObject.getAllObjects.size() ejecuta una vez al principio.

Claro, se puede lograr un comportamiento similar llamando al size() fuera del ciclo, como Peter mencionó:

size = someObject.getAllObjects.size();
for (i = 0; i < size; i++) {…}

Answer 5

El punto es que cuando se realiza la cuenta regresiva no es necesario marcar i >= 0 separado para decrementar i . Observar:

for (i = 5; i--;) {
alert(i); // alert boxes showing 4, 3, 2, 1, 0
}

Tanto la comparación como la disminución se pueden hacer en una expresión.

Vea otras respuestas de por qué esto se reduce a menos instrucciones x86.

En cuanto a si hace una diferencia significativa en su aplicación, bueno, supongo que eso depende de cuántos bucles tenga y cuán profundamente anidados estén. Pero para mí, es tan fácil de leer de esta manera, así que lo hago de todos modos.

Answer 6

En C a psudo-ensamblado:

for (i = 0; i < 10; i++) {
foo(i);
}

se convierte en

 clear i
top_of_loop:
call foo
increment i
compare 10, i
jump_less top_of_loop

mientras:

for (i = 10; i >= 0; i--) {
foo(i);
}

se convierte en

 load i, 10
top_of_loop:
call foo
decrement i
jump_not_neg top_of_loop

Tenga en cuenta la falta de la comparación en el segundo psudo-assembly. En muchas arquitecturas hay banderas que se establecen mediante operaciones aritméticas (sumar, restar, multiplicar, dividir, incrementar, disminuir) que puede usar para saltos. Estos a menudo le dan lo que es esencialmente una comparación del resultado de la operación con 0 gratis. De hecho, en muchas arquitecturas

x = x - 0

es semánticamente el mismo que

compare x, 0

Además, la comparación contra un 10 en mi ejemplo podría resultar en un código peor. Es posible que 10 tengan que vivir en un registro, por lo tanto, si son escasos, ese costo puede dar como resultado un código adicional para mover cosas o volver a cargar las 10 cada vez que pasa el ciclo.

Los compiladores a veces pueden reordenar el código para aprovechar esto, pero a menudo es difícil porque a menudo no pueden estar seguros de que invertir la dirección a través del ciclo es semánticamente equivalente.

Answer 7

En algunas CPU más antiguas hay / instrucciones como DJNZ == "decremento y salto si no es cero". Esto permitió la realización de bucles eficientes en los que cargó un valor de recuento inicial en un registro y luego pudo administrar de manera efectiva un ciclo de decremento con una instrucción. Estamos hablando de ISA de los 80 aquí, sin embargo, su maestro está seriamente fuera de contacto si cree que esta "regla de oro" todavía se aplica con las CPU modernas.

Answer 8

En el conjunto de instrucciones Intel x86, construir un bucle para realizar una cuenta regresiva a cero normalmente se puede hacer con menos instrucciones que un bucle que cuenta hasta una condición de salida distinta de cero. Específicamente, el registro ECX se usa tradicionalmente como un contador de bucle en x86 asm, y el conjunto de instrucciones Intel tiene una instrucción especial de salto jcxz que prueba el registro ECX para cero y salta en función del resultado de la prueba.

Sin embargo, la diferencia de rendimiento será insignificante, a menos que su ciclo ya sea muy sensible a los recuentos del ciclo de reloj. Contar hasta cero puede reducir 4 o 5 ciclos de reloj de cada iteración del ciclo en comparación con el conteo, por lo que en realidad es más una novedad que una técnica útil.

Además, un buen compilador de optimización en estos días debería ser capaz de convertir el código fuente del bucle de conteo en una cuenta regresiva para cero código máquina (dependiendo de cómo use la variable de índice de bucle) así que realmente no hay ninguna razón para escribir sus bucles formas extrañas solo para exprimir un ciclo o dos aquí y allá.

Answer 9

Es una pregunta interesante, pero como una cuestión práctica, no creo que sea importante y no hace que un bucle sea mejor que el otro.

De acuerdo con esta página wikipedia: segundo salto , "... el día solar se vuelve 1.7 ms más largo cada siglo debido principalmente a la fricción de las mareas". Pero si está contando días hasta su cumpleaños, ¿realmente le importa esta pequeña diferencia de tiempo?

Es más importante que el código fuente sea fácil de leer y entender. Esos dos bucles son un buen ejemplo de por qué la legibilidad es importante, no se repiten el mismo número de veces.

Apuesto a que la mayoría de los programadores leen (i = 0; i <N; i ++) y entienden inmediatamente que esto se repite N veces. Un bucle de (i = 1; i <= N; i ++), para mí de todos modos, es un poco menos claro, y con (i = N; i> 0; i--) Tengo que pensarlo un momento . Lo mejor es que la intención del código vaya directamente al cerebro sin necesidad de pensar.

Answer 10

Esto es lo que podría suceder en algún hardware dependiendo de lo que el compilador pueda deducir sobre el rango de los números que está usando: con el ciclo de incremento debe probar i<N cada vez que pasa el ciclo. Para la versión decreciente, la bandera de acarreo (establecida como un efecto secundario de la resta) puede decirle automáticamente si i>=0 . Eso ahorra una prueba por cada ronda del ciclo.

En realidad, en el hardware de procesador moderno con tuberías, esto es casi seguro irrelevante ya que no hay un simple mapeo 1-1 de instrucciones a ciclos de reloj. (Aunque podría imaginar que surgiría si estuvieras haciendo cosas como generar señales de video sincronizadas con precisión desde un microcontrolador. Pero de todos modos escribirías en lenguaje ensamblador).

Answer 11

Extrañamente, parece que hay una diferencia. Al menos, en PHP. Considera seguir el punto de referencia:

<?php
print "<br>".PHP_VERSION;
$iter = 100000000;
$i=$t1=$t2=0;
$t1 = microtime(true);
for($i=0;$i<$iter;$i++){}
$t2 = microtime(true);
print ''<br>$i++ : ''.($t2-$t1);
$t1 = microtime(true);
for($i=$iter;$i>0;$i--){}
$t2 = microtime(true);
print ''<br>$i-- : ''.($t2-$t1);
$t1 = microtime(true);
for($i=0;$i<$iter;++$i){}
$t2 = microtime(true);
print ''<br>++$i : ''.($t2-$t1);
$t1 = microtime(true);
for($i=$iter;$i>0;--$i){}
$t2 = microtime(true);
print ''<br>--$i : ''.($t2-$t1);

Los resultados son interesantes:

PHP 5.2.13
$i++ : 8.8842368125916
$i-- : 8.1797409057617
++$i : 8.0271911621094
--$i : 7.1027431488037
PHP 5.3.1
$i++ : 8.9625310897827
$i-- : 8.5790238380432
++$i : 5.9647901058197
--$i : 5.4021768569946

Si alguien sabe por qué, sería bueno saber :)

EDITAR : Los resultados son los mismos incluso si comienza a contar no desde 0, sino con otro valor arbitrario. Entonces, probablemente no solo haya una comparación con cero, ¿qué hace la diferencia?

Answer 12

Lo que importa mucho más que aumentar o disminuir su contador es si está subiendo en la memoria o disminuyendo la memoria. La mayoría de las memorias caché están optimizadas para subir memoria, no para memoria. Dado que el tiempo de acceso a la memoria es el cuello de botella que enfrentan la mayoría de los programas de hoy, esto significa que cambiar su programa para que suba la memoria puede generar un aumento del rendimiento incluso si esto requiere comparar su contador con un valor distinto de cero. En algunos de mis programas, vi una mejora significativa en el rendimiento cambiando mi código para ir a la memoria en lugar de bajarla.

¿Escéptico? Aquí está el resultado que obtuve:

Ave. Up Memory = 4839 mus
Ave. Down Memory = 5552 mus
Ave. Up Memory = 18638 mus
Ave. Down Memory = 19053 mus

de ejecutar este programa:

#include <chrono>
#include <iostream>
#include <random>
#include <vector>
template<class Iterator, typename T>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) {
std::random_device rnd_device;
std::mt19937 generator(rnd_device());
std::uniform_int_distribution<T> dist(a, b);
for (auto it = start; it != one_past_end; it++)
*it = dist(generator);
return ;
}
template<class Iterator>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, double a, double b) {
std::random_device rnd_device;
std::mt19937_64 generator(rnd_device());
std::uniform_real_distribution<double> dist(a, b);
for (auto it = start; it != one_past_end; it++)
*it = dist(generator);
return ;
}
template<class Iterator, class T>
inline void sum_abs_up(Iterator first, Iterator one_past_last, T &total) {
T sum = 0;
auto it = first;
do {
sum += *it;
it++;
} while (it != one_past_last);
total += sum;
}
template<class Iterator, class T>
inline void sum_abs_down(Iterator first, Iterator one_past_last, T &total) {
T sum = 0;
auto it = one_past_last;
do {
it--;
sum += *it;
} while (it != first);
total += sum;
}
template<class T>
std::chrono::nanoseconds TimeDown(std::vector<T> &vec, const std::vector<T> &vec_original,
std::size_t num_repititions, T &running_sum) {
std::chrono::nanoseconds total{0};
for (std::size_t i = 0; i < num_repititions; i++) {
auto start_time = std::chrono::high_resolution_clock::now();
sum_abs_down(vec.begin(), vec.end(), running_sum);
total += std::chrono::high_resolution_clock::now() - start_time;
vec = vec_original;
}
return total;
}
template<class T>
std::chrono::nanoseconds TimeUp(std::vector<T> &vec, const std::vector<T> &vec_original,
std::size_t num_repititions, T &running_sum) {
std::chrono::nanoseconds total{0};
for (std::size_t i = 0; i < num_repititions; i++) {
auto start_time = std::chrono::high_resolution_clock::now();
sum_abs_up(vec.begin(), vec.end(), running_sum);
total += std::chrono::high_resolution_clock::now() - start_time;
vec = vec_original;
}
return total;
}
template<class ValueType>
void TimeFunctions(std::size_t num_repititions, std::size_t vec_size = (1u << 24)) {
auto lower = std::numeric_limits<ValueType>::min();
auto upper = std::numeric_limits<ValueType>::max();
std::vector<ValueType> vec(vec_size);
FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
const auto vec_original = vec;
ValueType sum_up = 0, sum_down = 0;
auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count();
auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
std::cout << "Ave. Up Memory = " << time_up/(num_repititions * 1000) << " mus/n";
std::cout << "Ave. Down Memory = " << time_down/(num_repititions * 1000) << " mus"
<< std::endl;
return ;
}
int main() {
std::size_t num_repititions = 1 << 10;
TimeFunctions<int>(num_repititions);
std::cout << ''/n'';
TimeFunctions<double>(num_repititions);
return 0;
}

Both sum_abs_up and sum_abs_down do the same thing and are timed they same way with the only difference being that sum_abs_up goes up memory while sum_abs_down goes down memory. I even pass vec by reference so that both functions access the same memory locations. Nevertheless, sum_abs_up is consistently faster than sum_abs_down . Give it a run yourself (I compiled it with g++ -O3).

FYI vec_original is there for experimentation, to make it easy for me to change sum_abs_up and sum_abs_down in a way that makes them alter vec while not allowing these changes to affect future timings.

It''s important to note how tight the loop that I''m timing is. If a loop''s body is large then it likely won''t matter whether its iterator goes up or down memory since the time it takes to execute the loop''s body will likely completely dominate. Also, it''s important to mention that with some rare loops, going down memory is sometimes faster than going up it. But even with such loops it''s rarely ever the case that going up was always slower than going down (unlike small-bodied loops that go up memory, for which the opposite is frequently true; in fact, for a small handful of loops I''ve timed, the increase in performance by going up memory was 40+%).

The point is, as a rule of thumb, if you have the option, if the loop''s body is small, and if there''s little difference between having your loop go up memory instead of down it, then you should go up memory.

Answer 13

Lo que tu maestro dijo fue una declaración oblicua sin mucha aclaración. NO es que decrementar es más rápido que incrementar, pero puede crear un bucle mucho más rápido con decremento que con incremento.

Sin prolongarlo al respecto, sin necesidad de utilizar el contador de bucles, etc., lo que importa a continuación es solo la velocidad y el recuento de bucles (distinto de cero).

Aquí es cómo la mayoría de las personas implementan el bucle con 10 iteraciones:

int i;
for (i = 0; i < 10; i++)
{
//something here
}

Para el 99% de los casos es todo lo que uno puede necesitar, pero junto con PHP, PYTHON, JavaScript existe todo el mundo de software de tiempo crítico (generalmente integrado, sistema operativo, juegos, etc.) donde las marcas de la CPU realmente importan, así que mire brevemente el código ensamblador de:

int i;
for (i = 0; i < 10; i++)
{
//something here
}

después de la compilación (sin optimización) la versión compilada puede verse así (VS2015):

-------- C7 45 B0 00 00 00 00 mov dword ptr [i],0
-------- EB 09 jmp labelB
labelA 8B 45 B0 mov eax,dword ptr [i]
-------- 83 C0 01 add eax,1
-------- 89 45 B0 mov dword ptr [i],eax
labelB 83 7D B0 0A cmp dword ptr [i],0Ah
-------- 7D 02 jge out1
-------- EB EF jmp labelA
out1:

El ciclo completo es de 8 instrucciones (26 bytes). En él, en realidad hay 6 instrucciones (17 bytes) con 2 ramas. Sí, sí sé que se puede hacer mejor (es solo un ejemplo).

Ahora considere este constructo frecuente que a menudo encontrará escrito por un desarrollador integrado:

i = 10;
do
{
//something here
} while (--i);

También itera 10 veces (sí, sé que el valor es diferente en comparación con el ciclo mostrado, pero nos importa el recuento de iteraciones aquí). Esto puede ser compilado en esto:

00074EBC C7 45 B0 01 00 00 00 mov dword ptr [i],1
00074EC3 8B 45 B0 mov eax,dword ptr [i]
00074EC6 83 E8 01 sub eax,1
00074EC9 89 45 B0 mov dword ptr [i],eax
00074ECC 75 F5 jne main+0C3h (074EC3h)

5 instrucciones (18 bytes) y solo una rama. En realidad, hay 4 instrucciones en el ciclo (11 bytes).

Lo mejor es que algunas CPU (compatible con x86 / x64) tienen instrucciones que pueden disminuir un registro, luego comparar el resultado con cero y realizar una bifurcación si el resultado es diferente de cero. Prácticamente TODAS las computadoras de PC implementan esta instrucción. Utilizándolo, el bucle es realmente solo uno (sí uno) instrucción de 2 bytes:

00144ECE B9 0A 00 00 00 mov ecx,0Ah
label:
// something here
00144ED3 E2 FE loop label (0144ED3h) // decrement ecx and jump to label if not zero

¿Debo explicar cuál es más rápido?

Ahora, incluso si una CPU particular no implementa las instrucciones anteriores, todo lo que requiere para emular es una disminución seguida de un salto condicional si el resultado de la instrucción anterior pasa a ser cero.

Por lo tanto, independientemente de algunos casos que pueda señalar como un comentario por el cual estoy equivocado, etc. AURICULAR, SI ES BENEFICIAL ABATIRSE ABAJO si sabe cómo, por qué y cuándo.

PD. Sí, sé que el compilador inteligente (con el nivel de optimización apropiado) volverá a escribir para el ciclo (con el contador de ciclo ascendente) en el equivalente ... do equivalente para las iteraciones de ciclo constante ... (o para desenrollarlo) ...

Answer 14

No, eso no es realmente cierto. Una situación en la que podría ser más rápido es cuando, de lo contrario, estarías llamando a una función para verificar los límites durante cada iteración de un ciclo.

for(int i=myCollection.size(); i >= 0; i--)
{
...
}

Pero si no está claro hacerlo de esa manera, no vale la pena. En los idiomas modernos, debe utilizar un bucle Foreach cuando sea posible, de todos modos. Menciona específicamente el caso en el que debería usar un bucle foreach, cuando no necesita el índice.

Answer 15

Sí..!!

Contando desde N hasta 0 es ligeramente más rápido que Contando de 0 a N en el sentido de cómo el hardware manejará la comparación.

Tenga en cuenta la comparación en cada ciclo

i>=0
i<N

La mayoría de los procesadores tienen una comparación con cero instrucciones ... por lo que el primero se traducirá al código máquina como:

1. Cargar i
2. Compare y salte si es inferior o igual a cero

Pero el segundo necesita cargar N Memory cada vez

1. cargar i
2. carga N
3. Sub i y N
4. Compare y salte si es inferior o igual a cero

Por lo tanto, no es debido a la cuenta atrás o hacia arriba ... sino por la forma en que su código se traducirá en código de máquina.

Entonces contar de 10 a 100 es lo mismo que contar de 100 a 10
Pero contar desde i = 100 a 0 es más rápido que desde i = 0 a 100 - en la mayoría de los casos
Y contar desde i = N a 0 es más rápido que desde i = 0 a N

• Tenga en cuenta que hoy en día los compiladores pueden hacer esta optimización por usted (si es lo suficientemente inteligente)
• Tenga en cuenta también que la tubería puede causar el efecto similar a la anomalía de Belady (no puede estar seguro de qué será mejor)
• Por último: tenga en cuenta que los 2 for bucles que ha presentado no son equivalentes ... el primero imprime uno más * ....

Relacionado: ¿Por qué n ++ se ejecuta más rápido que n = n + 1?

Answer 16

independientemente de la dirección, siempre use la forma de prefijo (++ i en lugar de i ++)!

for (i=N; i>=0; --i)

o

for (i=0; i<N; ++i)

Explicación: http://www.eskimo.com/~scs/cclass/notes/sx7b.html

Además puedes escribir

for (i=N; i; --i)

Pero esperaría que los compiladores modernos puedan hacer exactamente estas optimizaciones.

Answer 17

Puede ser más rápido.

En el procesador NIOS II con el que estoy trabajando actualmente, el bucle tradicional para

for(i=0;i<100;i++)

produce el montaje:

ldw r2,-3340(fp) %load i to r2
addi r2,r2,1 %increase i by 1
stw r2,-3340(fp) %save value of i
ldw r2,-3340(fp) %load value again (???)
cmplti r2,r2,100 %compare if less than equal 100
bne r2,zero,0xa018 %jump

Si hacemos una cuenta regresiva

for(i=100;i--;)

obtenemos un conjunto que necesita 2 instrucciones menos.

ldw r2,-3340(fp)
addi r3,r2,-1
stw r3,-3340(fp)
bne r2,zero,0xa01c

Si tenemos bucles anidados, donde el bucle interno se ejecuta mucho, podemos tener una diferencia medible:

int i,j,a=0;
for(i=100;i--;){
for(j=10000;j--;){
a = j+1;
}
}

Si el bucle interno se escribe como arriba, el tiempo de ejecución es: 0.12199999999999999734 segundos. Si el ciclo interno está escrito de la manera tradicional, el tiempo de ejecución es: 0.17199999999999998623 segundos. Entonces, la cuenta regresiva del bucle es aproximadamente un 30% más rápida.

Pero: esta prueba se realizó con todas las optimizaciones de GCC desactivadas. Si los activamos, el compilador es realmente más inteligente que esta optimización manual e incluso mantiene el valor en un registro durante todo el ciclo y obtendríamos un ensamblado como

addi r2,r2,-1
bne r2,zero,0xa01c

En este ejemplo particular, el compilador incluso advierte que esa variable siempre será 1 después de la ejecución del bucle y omite todos los bucles.

Sin embargo, experimenté que a veces, si el cuerpo del bucle es lo suficientemente complejo, el compilador no puede hacer esta optimización, por lo que la forma más segura de obtener siempre una ejecución rápida del bucle es escribir:

register int i;
for(i=10000;i--;)
{ ... }

Por supuesto, esto solo funciona, si no importa que el ciclo se ejecute en reversa y, como dijo Betamoo, solo si está regresando a cero.

Answer 18

At an assembler level a loop that counts down to zero is generally slightly faster than one that counts up to a given value. If the result of a calculation is equal to zero most processors will set a zero flag. If subtracting one makes a calculation wrap around past zero this will normally change the carry flag (on some processors it will set it on others it will clear it), so the comparison with zero comes essentially for free.

This is even more true when the number of iterations is not a constant but a variable.

In trivial cases the compiler may be able to optimise the count direction of a loop automatically but in more complex cases it may be that the programmer knows that the direction of the loop is irrelevant to the overall behaviour but the compiler cannot prove that.

Answer 19

Now, I think you had enough assembly lectures:) I would like to present you another reason for top->down approach.

The reason to go from the top is very simple. In the body of the loop, you might accidentally change the boundary, which might end in incorrect behaviour or even non-terminating loop.

Look at this small portion of Java code (the language does not matter I guess for this reason):

 System.out.println("top->down");
int n = 999;
for (int i = n; i >= 0; i--) {
n++;
System.out.println("i = " + i + "/t n = " + n);
}
System.out.println("bottom->up");
n = 1;
for (int i = 0; i < n; i++) {
n++;
System.out.println("i = " + i + "/t n = " + n);
}

So my point is you should consider prefering going from the top down or having a constant as a boundary.