Cuenta atrás en for-loops

Question

Creo (de algunas lecturas de investigación) que la cuenta regresiva en for-loops es en realidad más eficiente y más rápida en tiempo de ejecución. Mi código de software completo es C ++

Actualmente tengo esto:

for (i=0; i<domain; ++i) {

mi 'i' es un registro sin firmar int, también 'dominio' es unsigned int

en el bucle for i se utiliza para atravesar una matriz, por ejemplo,

array[i] = do stuff

convertir esto para descontar desordena la salida esperada / correcta de mi rutina.

Me imagino que la respuesta es bastante trivial, pero no puedo entenderlo.

ACTUALIZACIÓN: 'hacer cosas' no depende de la iteración anterior o posterior. Los cálculos dentro del ciclo for son independientes para esa iteración de i. (Espero que tenga sentido).

ACTUALIZACIÓN: Para lograr una aceleración del tiempo de ejecución con mi ciclo for, ¿cuento hacia atrás y, si es así, elimino la parte sin firmar al delcarcar mi int, o qué otro método?

Por favor ayuda.

Answer 1

Supongo que su bucle hacia atrás se ve así:

for (i = domain - 1; i >= 0; --i) {

En ese caso, dado que i es sin signo , siempre será mayor o igual a cero. Cuando disminuye una variable sin signo que es igual a cero, se ajustará a un número muy grande. La solución es hacer que i esté firmado o cambiar la condición en el bucle for de esta manera:

for (i = domain - 1; i >= 0 && i < domain; --i) {

O cuente desde dominio a 1 en lugar de desde dominio - 1 a 0 :

for (i = domain; i >= 1; --i) {
    array[i - 1] = ...; // notice you have to subtract 1 from i inside the loop now
}

Answer 2

Solo hay un método correcto de bucle hacia atrás utilizando un contador sin firmar:

for( i = n; i-- > 0; )
{
    // Use i as normal here
}

Aquí hay un truco, para la última iteración del bucle tendrá i = 1 en la parte superior del bucle, i-- > 0 pasa porque 1 > 0, entonces i = 0 en el cuerpo del bucle. En la próxima iteración i-- > 0 falla porque i == 0, por lo que no importa que el decremento de postfix haya pasado por encima del contador.

Muy poco obvio, lo sé.

Answer 3

Esta no es una respuesta a su problema, porque parece que no tiene un problema.

Este tipo de optimización es completamente irrelevante y debe dejarse al compilador (si se hace)

¿Ha perfilado su programa para verificar que su ciclo for es un cuello de botella? Si no es así, no necesita pasar tiempo preocupándose por esto. Más aún, tener '' i '' como un " registro " int, a medida que escribe, no tiene ningún sentido desde el punto de vista del rendimiento.

Incluso sin conocer el dominio de su problema, puedo garantizarle que tanto la técnica de bucle inverso como el "registro" int counter tendrá un impacto insignificante en el rendimiento de su programa. Recuerde, "la optimización prematura es la raíz de todo mal".

Dicho esto, el tiempo de optimización mejor empleado sería pensar en la estructura general del programa, las estructuras de datos y los algoritmos utilizados, la utilización de recursos, etc.

Answer 4

La verificación para ver si un número es cero puede ser más rápida o más eficiente que una comparación. Pero este es el tipo de microoptimización por la que realmente no debería preocuparse: algunos ciclos de reloj se verán enormemente eclipsados ??por casi cualquier otro problema de rendimiento.

En x86:

dec eax
jnz Foo

En lugar de:

inc eax
cmp eax, 15
jl Foo

Answer 5

Si tiene un compilador decente, optimizará "contar" tan eficazmente como " cuenta atrás " ;. Solo prueba algunos puntos de referencia y verás.

Answer 6

Así que " lees " Que couting down es más eficiente? Encuentro esto muy difícil de creer a menos que me muestres algunos resultados del generador de perfiles y el código. Puedo comprarlo bajo ciertas circunstancias, pero en el caso general, no. Me parece que este es un caso clásico de optimización prematura.

Su comentario sobre " registrarse int i " También es muy revelador. Hoy en día, el compilador siempre sabe mejor que usted cómo asignar registros. No se moleste en usar la palabra clave de registro a menos que haya perfilado su código.

Answer 7

Cuando recorres las estructuras de datos de cualquier tipo, las fallas de caché tienen un impacto mucho mayor que la dirección en la que vas. Preocúpese con la imagen más amplia del diseño de la memoria y la estructura del algoritmo en lugar de las micro optimizaciones triviales.

Answer 8

No tiene nada que ver con contar arriba o abajo . Lo que puede ser más rápido es contar hacia cero . La respuesta de Michael muestra por qué - x86 le ofrece una comparación con cero como un efecto secundario implícito de muchas instrucciones, así que después de ajustar su contador, simplemente se ramifica en función del resultado en lugar de hacer una comparación explícita. (Quizás otras arquitecturas también hacen eso; no lo sé).

Los compiladores de Pascal de Borland son conocidos por realizar esa optimización. El compilador transforma este código:

for i := x to y do
  foo(i);

en una representación interna más parecida a esto:

tmp := Succ(y - x);
i := x;
while tmp > 0 do begin
  foo(i);
  Inc(i);
  Dec(tmp);
end;

(Digo notorio no porque la optimización afecte el resultado del ciclo, sino porque el depurador muestra la variable del contador incorrectamente. Cuando el programador inspecciona i , el depurador puede mostrar el valor de tmp en su lugar, lo que causa un sinfín de confusión y pánico para los programadores que piensan que sus bucles se están ejecutando hacia atrás).

La idea es que incluso con la instrucción adicional de Inc o Dec , sigue siendo una ganancia neta, en términos de tiempo de ejecución, en lugar de hacer una comparación explícita. Si realmente puede notar que la diferencia está en discusión.

Pero tenga en cuenta que la conversión es algo que el compilador haría automáticamente , en función de si consideraba que la transformación valía la pena. El compilador generalmente es mejor para optimizar el código que usted, por lo que no gaste demasiado esfuerzo compitiendo con él.

De todos modos, preguntaste sobre C ++, no sobre Pascal. C ++ " para " los bucles no son tan fáciles de aplicar esa optimización como Pascal "para" los bucles se deben a que los límites de los bucles de Pascal siempre se calculan completamente antes de que se ejecute el bucle, mientras que los bucles C ++ a veces dependen de la condición de detención y del contenido del bucle. Los compiladores de C ++ necesitan hacer una cierta cantidad de análisis estático para determinar si un bucle dado podría ajustarse a los requisitos para el tipo de transformación que los bucles Pascal califican incondicionalmente. Si el compilador de C ++ realiza el análisis, entonces podría hacer una transformación similar.

No hay nada que te impida escribir tus bucles de esa manera por tu cuenta:

for (unsigned i = 0, tmp = domain; tmp > 0; ++i, --tmp)
  array[i] = do stuff

Hacer eso podría hacer que su código se ejecute más rápido. Sin embargo, como dije antes, probablemente no lo notarás. El mayor costo que paga al organizar manualmente sus bucles de esa manera es que su código ya no sigue modismos establecidos. Su bucle es un `` para '' perfectamente ordinario bucle, pero ya no se ve como uno - tiene dos variables, cuentan en direcciones opuestas, y una de ellas ni siquiera se usa en el cuerpo del bucle - así que cualquiera que lea su código ( incluyéndote a ti, una semana, un mes o un año a partir de ahora, cuando hayas olvidado la `` optimización '' que esperabas lograr), tendrás que dedicar un esfuerzo adicional para probarse a sí mismo que el ciclo es realmente un ciclo normal en disfraz.

(¿Notó que mi código anterior usaba variables sin signo sin peligro de envolverse en cero? Usar dos variables separadas lo permite).

Tres cosas para quitar de todo esto:

1. Deje que el optimizador haga su trabajo; En general, es mejor que tú.
2. Haga que el código ordinario se vea normal para que el código especial no tenga que competir para llamar la atención de las personas que lo revisan, depuran o mantienen.
3. No haga nada sofisticado en nombre del rendimiento hasta que las pruebas y los perfiles demuestren que es necesario.

Answer 9

Puedes probar lo siguiente, qué compilador optimizará de manera muy eficiente:

#define for_range(_type, _param, _A1, _B1) \
    for (_type _param = _A1, _finish = _B1,\
    _step = static_cast<_type>(2*(((int)_finish)>(int)_param)-1),\
    _stop = static_cast<_type>(((int)_finish)+(int)_step); _param != _stop; \
_param = static_cast<_type>(((int)_param)+(int)_step))

Ahora puedes usarlo:

for_range (unsigned, i, 10,0)
{
    cout << "backwards i: " << i << endl;
}

for_range (char, c, 'z','a')
{
    cout << c << endl;
}

enum Count { zero, one, two, three }; 

for_range (Count, c, three, zero)
{
    cout << "backwards: " << c << endl;
}

Puede iterar en cualquier dirección:

for_range (Count, c, zero, three)
{
    cout << "forward: " << c << endl;
}

El bucle

for_range (unsigned,i,b,a)
{
   // body of the loop
}

producirá el siguiente código:

 mov esi,b
L1:
;    body of the loop
   dec esi
   cmp esi,a-1
   jne L1 

Answer 10

Es difícil de decir con la información dada pero ... ¿invierte su matriz y cuenta atrás?

Answer 11

Jeremy Ruten señaló acertadamente que usar un contador de bucle no firmado es peligroso. También es innecesario, por lo que puedo decir.

Otros también han señalado los peligros de la optimización prematura. Tienen toda la razón.

Dicho esto, aquí hay un estilo que usé cuando programaba sistemas embebidos hace muchos años, cuando cada byte y cada ciclo contaban para algo. Estos formularios fueron útiles para mí en las CPU y compiladores particulares que estaba usando, pero su kilometraje puede variar.

// Start out pointing to the last elem in array
pointer_to_array_elem_type p = array + (domain - 1);
for (int i = domain - 1; --i >= 0 ; ) {
     *p-- = (... whatever ...)
}

Este formulario aprovecha el indicador de condición que se establece en algunos procesadores después de las operaciones aritméticas; en algunas arquitecturas, la disminución y las pruebas de la condición de ramificación se pueden combinar en una sola instrucción. Tenga en cuenta que el uso del predecremento ( --i ) es la clave aquí: el uso del postdecremento ( i-- ) no habría funcionado tan bien.

Alternativamente,

// Start out pointing *beyond* the last elem in array
pointer_to_array_elem_type p = array + domain;
for (pointer_to_array_type p = array + domain; p - domain > 0 ; ) {
     *(--p) = (... whatever ...)
}

Esta segunda forma aprovecha la aritmética del puntero (dirección). Raramente veo la forma (pointer - int) en estos días (por una buena razón), pero el lenguaje garantiza que cuando restas un int de un puntero, el puntero se reduce por (int * sizeof (* puntero)) .

Volveré a enfatizar que si estos formularios son beneficiosos para usted depende de la CPU y el compilador que esté usando. Me sirvieron bien en las arquitecturas Motorola 6809 y 68000.

Answer 12

En algunos núcleos de armado posteriores, la disminución y la comparación toman solo una instrucción. Esto hace que los ciclos de reducción sean más eficientes que los incrementos.

No sé por qué no hay una instrucción de comparación de incrementos también.

Me sorprende que esta publicación haya sido votada -1 cuando se trata de un problema real.

Answer 13

Todos aquí se centran en el rendimiento. En realidad, hay una razón lógica para iterar hacia cero que puede resultar en un código más limpio.

Iterar sobre el último elemento primero es conveniente cuando elimina elementos no válidos intercambiando con el final de la matriz. Para elementos defectuosos no adyacentes al final, podemos cambiar a la posición final, disminuir el límite final de la matriz y seguir iterando. Si tuviera que iterar hacia el final, intercambiar con el final podría dar como resultado un intercambio de malo por malo. Al iterar de final a 0, sabemos que el elemento al final de la matriz ya ha demostrado ser válido para esta iteración.

Para más explicaciones ...

Si:

1. Elimina los elementos defectuosos intercambiando con un extremo de la matriz y cambiando los límites de la matriz para excluir los elementos defectuosos.

Entonces obviamente:

2. Cambiaría con un buen elemento, es decir, uno que ya se haya probado en esta iteración.

Entonces esto implica:

3. Si iteramos fuera del límite de la variable, entonces los elementos entre el límite de la variable y el puntero de iteración actual han demostrado ser buenos. Si el puntero de iteración obtiene ++ o - no importa. Lo importante es que estamos iterando fuera del límite de la variable para que sepamos que los elementos adyacentes son buenos.

Así que finalmente:

4. Iterar hacia 0 nos permite usar solo una variable para representar los límites de la matriz. Si esto importa es una decisión personal entre usted y su compilador.

Answer 14

Lo que importa mucho más que si está aumentando o disminuyendo su contador es si sube o baja la memoria. La mayoría de las cachés están optimizadas para aumentar la memoria, no la memoria. Dado que el tiempo de acceso a la memoria es el cuello de botella al que se enfrentan la mayoría de los programas actuales, esto significa que cambiar su programa para que pueda aumentar la memoria puede resultar en 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 al cambiar mi código para subir la memoria en lugar de bajarla.

¿Escéptico? Aquí está la salida que tengo:

sum up   = 705046256
sum down = 705046256
Ave. Up Memory   = 4839 mus
Ave. Down Memory =  5552 mus
sum up   = inf
sum down = inf
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 RAI, class T>
inline void sum_abs_up(RAI first, RAI one_past_last, T &total) {
  T sum = 0;
  auto it = first;
  do {
    sum += *it;
    it++;
  } while (it != one_past_last);
  total += sum;
}

template<class RAI, class T>
inline void sum_abs_down(RAI first, RAI 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;
}

int main() {
  std::size_t num_repititions = 1 << 10;
  {
  typedef int ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  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 << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  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;
  }
  {
  typedef double ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  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 << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  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 0;
}

Tanto sum_abs_up como sum_abs_down hacen lo mismo y se sincronizan de la misma manera, con la única diferencia de que sum_abs_up sube la memoria mientras < El código> sum_abs_down baja la memoria. Incluso paso vec por referencia para que ambas funciones accedan a las mismas ubicaciones de memoria. Sin embargo, sum_abs_up es consistentemente más rápido que sum_abs_down . Inténtalo tú mismo (lo compilé con g ++ -O3).

FYI vec_original está allí para la experimentación, para facilitarme el cambio de sum_abs_up y sum_abs_down de una manera que los haga alterar < code> vec sin permitir que estos cambios afecten los tiempos futuros.

Es importante tener en cuenta lo estrecho que es el bucle que estoy sincronizando. Si el cuerpo de un bucle es grande, entonces probablemente no importará si su iterador sube o baja la memoria, ya que el tiempo que lleva ejecutar el cuerpo del bucle probablemente dominará por completo. Además, es importante mencionar que con algunos bucles raros, bajar la memoria a veces es más rápido que subirlo. Pero incluso con tales bucles, rara vez es así que subir siempre fue más lento que bajar (a diferencia de los bucles que aumentan la memoria, que a menudo son más rápidos que los bucles de memoria baja equivalentes; un pequeño puñado de veces incluso fueron 40). +% más rápido).

El punto es, como regla general, si tiene la opción, si el cuerpo del bucle es pequeño, y si hay poca diferencia entre hacer que su bucle suba la memoria en lugar de bajarla, entonces debería subir la memoria.