C para la indexación de bucle: ¿la indexación hacia delante es más rápida en las nuevas CPU?

optimization for-loop (7)

Al optimizar los bucles, preferiría ver cómo se desenrolla el bucle (ya que reduce el número de comparaciones frente al valor de salida, y puede optimizarse para el procesamiento en paralelo (mmx) según lo que ocurra dentro del bucle).

En una lista de correo a la que estoy suscrito, dos programadores con bastante conocimiento (IMO) discutían un código optimizado y decían algo como:

En las CPU lanzadas hace 5-8 años, fue ligeramente más rápido iterar los bucles hacia atrás ( por ejemplo, for (int i=x-1; i>=0; i--) {...} ) porque comparando i con cero Es más eficiente que compararlo con algún otro número. Pero con CPU muy recientes ( por ejemplo, desde 2008-2009), la lógica del cargador especulativo es tal que funciona mejor si el bucle for se itera hacia adelante ( por ejemplo, for (int i=0; i< x; i++) {...} ) .

Mi pregunta es, ¿es eso cierto? ¿Se han cambiado las implementaciones de la CPU recientemente, de modo que la iteración hacia adelante del bucle ahora tiene una ventaja sobre la iteración hacia atrás? Si es así, ¿cuál es la explicación para eso? es decir, ¿qué cambió?

(Sí, lo sé, la optimización prematura es la raíz de todo mal, revise mi algoritmo antes de preocuparme por las microoptimizaciones, etc., etc., en su mayoría, solo tengo curiosidad)

Es probable que no haya demasiada diferencia en cuanto a la velocidad, pero a menudo escribo:

for (i = n; --i >= 0; ) blah blah

que creo que en un tiempo generó un montaje más limpio.

Por supuesto, al responder a este tipo de pregunta, corro el riesgo de afirmar que esto es importante. Es una pregunta de tipo micro-optimización, que está estrechamente relacionada con la optimización prematura, que todo el mundo dice que no debes hacer , pero que, sin embargo, SO está inundado.

Me topé con esta pregunta después de observar una caída significativa en el rendimiento al iterar una matriz hacia atrás y hacia adelante. Tenía miedo de que fuera el recolector, pero las respuestas anteriores me convencieron de que este no era el caso. Luego investigué más y descubrí que parece que GCC (4.8.4) no puede explotar todo el poder de las operaciones SIMD en bucles hacia atrás.

De hecho, compilando el siguiente código (desde here ) con -S -O3 -mavx :

for (i = 0; i < N; ++i) r[i] = (a[i] + b[i]) * c[i];

conduce esencialmente a:

.L10: addl $1, %edx vmovupd (%rdi,%rax), %xmm1 vinsertf128 $0x1, 16(%rdi,%rax), %ymm1, %ymm1 vmovupd (%rsi,%rax), %xmm0 vinsertf128 $0x1, 16(%rsi,%rax), %ymm0, %ymm0 vaddpd (%r9,%rax), %ymm1, %ymm1 vmulpd %ymm0, %ymm1, %ymm0 vmovupd %xmm0, (%rcx,%rax) vextractf128 $0x1, %ymm0, 16(%rcx,%rax) addq $32, %rax cmpl %r8d, %edx jb .L10

es decir, el código de ensamblaje que utiliza las extensiones AVX para realizar 4 operaciones dobles en paralelo (por ejemplo, vaddpd, vmulpd).

Por el contrario, el siguiente código compilado con los mismos parámetros:

for (i = 0; i < N; ++i) r[N-1-i] = (a[N-1-i] + b[N-1-i]) * c[N-1-i];

produce:

.L5: vmovsd a+79992(%rax), %xmm0 subq $8, %rax vaddsd b+80000(%rax), %xmm0, %xmm0 vmulsd c+80000(%rax), %xmm0, %xmm0 vmovsd %xmm0, r+80000(%rax) cmpq $-80000, %rax jne .L5

que solo realiza una doble operación en el momento (vaddsd, vmulsd).

Este solo hecho puede ser responsable de un factor 4 entre el rendimiento al iterar hacia atrás y hacia adelante.

Al usar -ftree-vectorizer-verbose=2 , parece que el problema se está almacenando al revés: "paso negativo para la tienda". De hecho, si a , b , c se leen al revés pero r se escribe en la dirección hacia adelante, el código se vectoriza nuevamente.

No lo sé. Pero sí sé cómo escribir un punto de referencia rápido sin garantías de validez científica (en realidad, una con garantías de invalidez bastante estrictas). Tiene resultados interesantes:

#include <time.h> #include <stdio.h> int main(void) { int i; int s; clock_t start_time, end_time; int centiseconds; start_time = clock(); s = 1; for (i = 0; i < 1000000000; i++) { s = s + i; } end_time = clock(); centiseconds = (end_time - start_time)*100 / CLOCKS_PER_SEC; printf("Answer is %d; Forward took %ld centiseconds/n", s, centiseconds); start_time = clock(); s = 1; for (i = 999999999; i >= 0; i--) { s = s + i; } end_time = clock(); centiseconds = (end_time - start_time)*100 / CLOCKS_PER_SEC; printf("Answer is %d; Backward took %ld centiseconds/n", s, centiseconds); return 0; }

Compilado con -O9 usando gcc 3.4.4 en Cygwin, ejecutándose en un "AMD Athlon (tm) 64 Processor 3500+" (2211 MHz) en Windows XP de 32 bits:

Answer is -1243309311; Forward took 93 centiseconds Answer is -1243309311; Backward took 92 centiseconds

(Las respuestas variaron por 1 de cualquier manera en varias repeticiones.)

Compilado con -I9 usando gcc 4.4.1 ejecutándose en una "CPU Intel (R) Atom (TM) N270 a 1.60GHz" (800 MHz y probablemente solo un núcleo, dado el programa) en Ubuntu Linux de 32 bits.

Answer is -1243309311; Forward took 196 centiseconds Answer is -1243309311; Backward took 228 centiseconds

(Las respuestas variaron por 1 de cualquier manera en varias repeticiones.)

Mirando el código, el bucle de avance se traduce a:

; Gcc 3.4.4 on Cygwin for Athlon ; Gcc 4.4.1 on Ubuntu for Atom L5: .L2: addl %eax, %ebx addl %eax, %ebx incl %eax addl $1, %eax cmpl $999999999, %eax cmpl $1000000000, %eax jle L5 jne .L2

El reverso a:

L9: .L3: addl %eax, %ebx addl %eax, %ebx decl %eax subl $1, $eax jns L9 cmpl $-1, %eax jne .L3

Lo que demuestra, si no mucho más, que el comportamiento de GCC ha cambiado entre esas dos versiones.

Al pegar los bucles de GCC más antiguos en el archivo asm de GCC más reciente se obtienen los siguientes resultados:

Answer is -1243309311; Forward took 194 centiseconds Answer is -1243309311; Backward took 133 centiseconds

Resumen: en el Athlon> 5 años, los bucles generados por GCC 3.4.4 son de la misma velocidad. En el átomo newish (<1 año?), El bucle hacia atrás es significativamente más rápido. GCC 4.4.1 tiene una ligera regresión para este caso en particular, lo que personalmente no me preocupa en lo más mínimo, dado el punto. (Tenía que asegurarme de que s se usara después del bucle, porque de lo contrario el compilador elidaría el cálculo por completo).

[1] Nunca puedo recordar el comando para información del sistema ...

No, no podemos decir que las implementaciones de la CPU hayan cambiado para hacer que el bucle de avance sea más rápido. Y eso tiene muy poco que ver con las propias CPU.

Tiene que ver con el hecho de que no ha especificado de qué CPU está hablando, ni de qué compilador.

No puede hacer una pregunta general acerca de los problemas de la CPU con la etiqueta C y esperar obtener una respuesta inteligente simplemente porque nada en el estándar C exige qué tan rápido deben ser las CPU en varias operaciones.

Si desea reformular su pregunta para dirigirse a una CPU y lenguaje de máquina específicos (dado que el lenguaje de máquina que obtiene de un compilador de C depende completamente del compilador), puede obtener una mejor respuesta.

En cualquier caso, no debería importar. Debería confiar en el hecho de que las personas que escribieron su compilador saben mucho más que usted sobre cómo obtener la última pulgada de rendimiento de las distintas CPU.

La dirección en la que debes estar iterando siempre ha sido dictada por lo que tienes que hacer. Por ejemplo, si tiene que procesar elementos de matriz en orden ascendente, use:

for (i = 0; i < 1000; i++) { process (a[i]); }

más bien que:

for (i = 999; i >= 0; i--) { process (a[999-i]); }

simplemente porque cualquier ventaja que pueda obtener al ir hacia atrás está más que saturada por los cálculos adicionales en i . Bien puede ser que un bucle desnudo (sin trabajo realizado en el cuerpo) sea más rápido en una dirección que en otra, pero, si tienes un bucle tan desnudo, no está haciendo ningún trabajo real de todos modos.

Como nota al margen, puede ser que ambos bucles anteriores se reduzcan al mismo código de la máquina de todos modos. He visto algunos de los códigos emitidos por el optimizador GCC y me dieron vueltas la cabeza. Los escritores de compiladores son, en mi opinión, una especie sola cuando se trata de niveles de optimización insanos.

Mi consejo: siempre programe la legibilidad primero y luego apunte a cualquier problema de rendimiento específico que tenga ("primero hágalo funcionar, luego hágalo funcionar rápido").

Realmente estás preguntando sobre la captación previa, no sobre la lógica de control de bucle.

En general, el rendimiento del bucle no será dictado por la lógica de control (es decir, el incremento / decremento y la condición que se verifica cada vez que se realiza). El tiempo que lleva hacer estas cosas es intrascendente, excepto en bucles muy ajustados. Si está interesado en eso, eche un vistazo a la respuesta de John Knoeller para obtener información específica sobre el registro de contador del 8086 y por qué podría haber sido cierta en los viejos tiempos en que la cuenta regresiva fue más eficiente. Como dice John, la predicción de rama (y también la especulación) puede desempeñar un papel en el desempeño aquí, al igual que la obtención previa de instrucciones .

El orden de iteración puede afectar significativamente el rendimiento cuando cambia el orden en que su bucle toca la memoria. El orden en el que solicita las direcciones de memoria puede afectar lo que se dibuja en su cache y también lo que se desaloja de su caché cuando ya no hay espacio para buscar nuevas líneas de caché. Tener que ir a la memoria más a menudo de lo necesario es mucho más costoso que comparar, aumentar o disminuir. En las CPU modernas, pueden pasar miles de ciclos desde el procesador a la memoria, y es posible que su procesador deba estar inactivo durante parte o todo ese tiempo.

Probablemente estés familiarizado con los cache , así que no voy a entrar en todos los detalles aquí. Lo que quizás no sepa es que los procesadores modernos emplean una gran cantidad de captadores previos para tratar de predecir qué datos van a necesitar a continuación en diferentes niveles de la jerarquía de memoria. Una vez que predicen, intentan extraer esos datos de la memoria o cachés de nivel inferior para que tenga lo que necesita cuando lo procesa. Dependiendo de qué tan bien tomen lo que necesita a continuación, su rendimiento puede o no mejorar cuando los usa.

Eche un vistazo a la guía de Intel para optimizar los buscadores de hardware . Hay cuatro prefetchers en la lista; dos para los chips de NetBurst :

El prefetcher de hardware de NetBurst puede detectar flujos de accesos de memoria hacia adelante o hacia atrás, e intentará cargar datos de esas ubicaciones en el caché L2.
NetBurst también tiene un prefetcher de línea de caché adyacente (ACL) , que cargará automáticamente dos líneas de caché adyacentes cuando recupere la primera.

y dos para Core :

Core tiene un prefetcher de hardware un poco más sofisticado; puede detectar el acceso a zancadas además de flujos de referencias contiguas, por lo que funcionará mejor si atraviesas una matriz cada otro elemento, cada 4, etc.
Core también tiene un prefetcher ACL como NetBurst.

Si está iterando a través de una matriz hacia delante, va a generar un montón de referencias de memoria secuenciales, generalmente contiguas. Los prefetchers de ACL lo harán mucho mejor para los bucles de avance (porque terminará usando esas líneas de caché subsiguientes) que para los bucles de retroceso, pero puede hacerlo haciendo las referencias de memoria hacia atrás si los captadores de prefijos pueden detectar esto (como con el hardware recolectores previos). Los prefetchers de hardware en el Core pueden detectar avances, lo que es útil para recorridos de arreglos más sofisticados.

Estas simples heurísticas pueden causarle problemas en algunos casos. Por ejemplo, Intel realmente recomienda que desactive la búsqueda previa de la línea de caché adyacente para los servidores, ya que tienden a hacer más referencias de memoria al azar que las máquinas de los usuarios de escritorio. La probabilidad de no usar una línea de caché adyacente es mayor en un servidor, por lo que la obtención de datos que realmente no va a usar termina contaminando su caché (llenándola de datos no deseados) y el rendimiento se resiente. Para más información sobre cómo abordar este tipo de problema, eche un vistazo a este documento de Supercomputing 2009 sobre el uso del aprendizaje automático para ajustar los recolectores de datos en grandes centros de datos . Algunos chicos de Google están en ese papel; El desempeño es algo que les preocupa mucho.

La heurística simple no lo ayudará con algoritmos más sofisticados, y es posible que tenga que comenzar a pensar en los tamaños de sus cachés L1, L2, etc. El procesamiento de imágenes, por ejemplo, a menudo requiere que realice alguna operación en subsecciones de una imagen 2D, pero el orden en que atraviesa la imagen puede afectar la forma en que las partes útiles permanecen en su caché sin ser desalojadas. Eche un vistazo a los recorridos de orden Z y el mosaico de bucles si está interesado en este tipo de cosas. Es un ejemplo bastante básico de mapear la localidad 2D de los datos de imagen a la localidad 1D de la memoria para mejorar el rendimiento. También es un área donde los compiladores no siempre pueden reestructurar su código de la mejor manera, pero la reestructuración manual de su código C puede mejorar drásticamente el rendimiento del caché.

Espero que esto te dé una idea de cómo el orden de iteración afecta el rendimiento de la memoria. Depende de la arquitectura particular, pero las ideas son generales. Debería poder comprender la búsqueda previa en AMD y Power si puede entenderla en Intel, y no necesita conocer el ensamblaje para estructurar su código y aprovechar la memoria. Solo necesitas conocer un poco la arquitectura de la computadora.

Sí. pero con una advertencia. La idea de que el bucle hacia atrás es más rápido nunca se aplica a todas las CPU antiguas. Es una cosa x86 (como en 8086 a 486, posiblemente Pentium, aunque no pienso más).

Esa optimización nunca se aplicó a ninguna otra arquitectura de CPU que yo sepa.

Este es el por qué.

El 8086 tenía un registro que se optimizó específicamente para su uso como contador de bucle. Pones tu cuenta de bucles en CX, y luego hay varias instrucciones que disminuyen CX y luego establecen los códigos de condición si van a cero. De hecho, había un prefijo de instrucción que podía poner antes que otras instrucciones (el prefijo REP) que básicamente iterarían las otras instrucciones hasta que CX llegara a 0.

En los días en que contábamos las instrucciones, las instrucciones se conocían con recuento de ciclos fijos usando cx, ya que su contador de bucles era el camino a seguir, y cx estaba optimizado para la cuenta atrás.

Pero eso fue hace mucho tiempo. Desde el Pentium, esas complejas instrucciones han sido más lentas en general que el uso de más instrucciones simples. (¡RISC baby!) Lo más importante que intentamos hacer en estos días es intentar pasar un tiempo entre cargar un registro y usarlo porque las tuberías pueden hacer varias cosas por ciclo siempre y cuando no intentes usar el mismo registro. por más de una cosa a la vez.

Hoy en día, lo que mata el rendimiento no es la comparación, es la bifurcación, y solo cuando la predicción de bifurcación predice un error.