Como utilizo bucles for-en arreglos multidim de gran tamaño, cualquier ahorro en el mecanismo de bucle for es significativo.consejos de eficiencia del mecanismo de bucle
Por consiguiente, estoy buscando algún consejo sobre cómo reducir esta sobrecarga.
p. Ej. : conteo regresivo usando uint en lugar de int y! = 0 como stop en lugar de> 0 permite que la CPU haga menos trabajo (lo escuché una vez, no estoy seguro de que sea siempre verdad)
Primero, no te preocupes por las cosas pequeñas. Detalles como la cuenta regresiva versus la cuenta regresiva son por lo general completamente irrelevantes en el tiempo de ejecución. Los humanos son notoriamente malos al detectar áreas en el código que necesitan ser aceleradas. Use un perfilador. Preste poca o ninguna atención a cualquier parte del ciclo que no se repita, a menos que el generador de perfiles diga lo contrario. Recuerde que lo que está escrito en un bucle interno no se ejecuta necesariamente en un bucle interno, ya que los compiladores modernos son bastante listos para evitar la repetición innecesaria.
Dicho esto, tenga mucho cuidado con los bucles de desenrollado en las CPU modernas. Cuanto más ajustados sean, mejor encajarán en la memoria caché. En una aplicación de alto rendimiento en la que trabajé el año pasado, mejoré significativamente el rendimiento mediante el uso de bucles en lugar de código de línea recta y apretándolos tanto como pude. (Sí, hice un perfil, la función en cuestión tomó el 80% del tiempo de ejecución.También comparé los tiempos con la entrada típica, así que sabía que los cambios me ayudaron.)
Además, no hay nada de malo en desarrollar hábitos que favorezcan un código eficiente. En C++, debe adquirir el hábito de usar el preincremento (++ i) en lugar del incremento posterior (i ++) para incrementar las variables de bucle. Por lo general, no importa, pero puede marcar una diferencia significativa, no hace que el código sea menos legible o escribible, y no hará daño.
Una sugerencia importante: mueva la mayor cantidad de cálculos a el bucle externo como sea posible. No todos los compiladores pueden hacer eso automáticamente. Para eample, en lugar de:
for row = 0 to 999
for col = 0 to 999
cell[row*1000+col] = row * 7 + col
uso:
for row = 0 to 999
x = row * 1000
y = row * 7
for col = 0 to 999
cell[x+col] = y + col
Sí, eso resuena con mi consejo: el bucle interno rápido. Un ejemplo de esto es Quicksort. –
A medida que sus bucles tendrán O (n^d) complejidad (d = dimensión), lo que realmente importa es lo que pone en el bucle , no el bucle en sí. La optimización de algunos ciclos de distancia en el marco de bucle de millones de ciclos de un algoritmo ineficiente dentro del bucle es solo aceite de serpiente.
Nunca encontré la notación O útil a menos que comparen dos algoritmos que hacen lo mismo. Tiene sentido decir que el tipo de burbuja es O (n^2) mientras que Quicksort es O (n lg n). Nunca tuvo sentido para mí decir que algo es O (n^2), sin algo similar para compararlo. –
Para ser pedante: la implementación básica de Quicksort tiene una complejidad de caso promedio de O (n log n), pero aún tiene la peor complejidad de caso de O (n^2). –
No estamos hablando de comparar algoritmos, Thorsten79 solo quería señalar que un bucle anidado se va a calcular en el orden de n^d veces, y la pequeñez del código interior es más importante que la estructura del bucle. – Karl
Loop-desenrollar puede ser de una sola vía. Es decir:
for (i=0; i<N; i++) {
a[i]=...;
}
se transforma en:
for (i=0; i<N; i+=4) {
a[i]=...;
a[i+1]=...;
a[i+2]=...;
a[i+3]=...;
}
Usted necesita un tratamiento especial cuando N no es un múltiplo de 4 en el ejemplo anterior.
¿Qué hace esto más eficiente? Especialmente en el caso en que N no es divisible por 4, y por lo tanto, ¿está introduciendo comprobaciones extra de declaración en la parte superior del ciclo? –
Si N es grande, la sobrecarga relativa de esas sentencias if es bastante pequeña. (Deben mantenerse fuera del bucle). Además, la sobrecarga introducida por el bucle está en el ejemplo (casi) reducida a 1/4. Desenrollar solo tiene sentido cuando la operación llevada a cabo para cada elemento es rápida. – SteinNorheim
hace la diferencia, ¡sin embargo la mayoría de los compiladores que se respetan ya lo harán! –
¿Ha medido la sobrecarga? ¿Sabes cuánto tiempo se dedica a procesar los bucles for y cuánto tiempo se dedica a ejecutar el código de la aplicación? ¿Cuál es tu objetivo?
Esta no es una pregunta independiente del idioma, depende en gran medida no solo del lenguaje, sino también del compilador. La mayoría de los compiladores creo que va a compilar estos dos equivalentemente:
for (int i = 0; i < 10; i++) { /* ... */ }
int i = 0;
while (i < 10) {
// ...
i++;
}
En la mayoría de idiomas/compiladores, el bucle es simplemente azúcar sintáctica para la tarde, mientras que bucle. Foreach es otra cuestión de nuevo, y depende en gran medida del lenguaje/compilador sobre cómo se implementa, pero generalmente es menos eficiente que un ciclo for/while normal. Cuánto más lo es nuevamente, el lenguaje y el compilador dependen.
Su mejor opción probablemente sea ejecutar algunos puntos de referencia con diferentes variaciones sobre un tema y ver lo que sale en la parte superior.
Editar: Para ese fin, el suggestions here probablemente le ahorrará más tiempo en lugar de preocuparse por el bucle en sí.
Estoy de acuerdo con @Greg. Lo primero que debe hacer es establecer algunos puntos de referencia. No tendrá mucho sentido optimizar nada hasta que pruebe dónde se está gastando todo el tiempo de procesamiento. "¡La optimización prematura es la raíz de todo mal"!
Trate de hacer que sus bucles sean contiguos en la memoria, esto optimizará el uso de la memoria caché. Es decir, no hacen esto:
for (int i = 0; i < m; i++)
for (j = 0; j < n; j++)
s += arr[j][i];
A propósito, a menos que necesite un incremento posterior, siempre debe usar el operador de incremento previo. Es solo una pequeña diferencia, pero es más eficiente.
Internamente esta es la diferencia:
Publica Incremento
i++;
es lo mismo que:
int postincrement(int &i)
{
int itmp = i;
i = i + 1;
return itmp;
}
Pre Inc Re-Ment
++i;
es lo mismo que:
int preincrement(int &i)
{
i = i + 1;
return i;
}
Creo que quisiste escribir ++ i; –
Cuando está incrementando un int, es muy probable que el compilador optimice la diferencia. esto es más relevante cuando se trata de iteradores. – shoosh
Creo que la mayoría de los compiladores probablemente hacer esto de todos modos, dando un paso atrás hasta cero debe ser más eficiente, como un cheque por cero es muy rápido para el procesador. Sin embargo, de nuevo, cualquier compilador que valga su peso haría esto con la mayoría de los bucles de todos modos. Necesita ver lo que está haciendo el compilador.
No hay suficiente información para responder su pregunta con precisión. ¿Qué haces dentro de tus bucles? El cálculo en una iteración depende de un valor calculado en una iteración previa. De lo contrario, puedes reducir tu tiempo a la mitad simplemente usando 2 hilos, suponiendo que tienes al menos un procesador de doble núcleo.
Otra cosa a tener en cuenta es cómo se está accediendo a los datos, si se está haciendo grande el procesamiento de señal, para asegurarse de que tiene acceso a los datos secuencialmente medida que se almacenan en la memoria, evitando el lavado de su L1/L2 cache en cada iteración (visto esto antes en cachés L1 más pequeños, la diferencia puede ser dramática).
Una vez más, me gustaría ver lo que está dentro del circuito, donde la mayoría de las ganancias (> 99%) será, en lugar de la tubería de bucle externo.
Pero, una vez más, si su código de bucle está vinculado a E/S, el tiempo empleado en la optimización se desperdicia.
Hay alguna información relevante entre las respuestas a otra pregunta de stackoverflow, how cache memory works. Encontré el documento por Ulrich Drepper mencionado en this respuesta especialmente útil.
Por cierto, ¿es bueno usar short en lugar de int en for-loop si la capacidad de Int16 es suficiente?
En la mayoría de las computadoras modernas, las operaciones de 32 bits serán tan rápidas como 16 bits. Entonces, la respuesta es no, no importará. –
ver respuesta de @monoxide. esto no debe etiquetarse como independiente del idioma y creo que obtendrás mejores respuestas si las personas saben qué idioma/compilador están tratando de optimizar. –
de acuerdo, la optimización es específica del idioma, y la forma en que se expresa la pregunta parece que también se debe apuntar a una plataforma en particular (los tiempos operativos varían para las diferentes CPU) – Oskar
etiquetado needs-clarification – Sklivvz