delphi - Problemas con ADC/SBB e INC/DEC en lazos cerrados en algunas CPU

assembly x86

Question

Estoy escribiendo un tipo simple BigInteger en Delphi. Consiste principalmente en una matriz dinámica de TLimb, donde un TLimb es un entero sin signo de 32 bits y un campo de tamaño de 32 bits, que también contiene el bit de signo para BigInteger.

Para agregar dos BigIntegers, creo un nuevo BigInteger del tamaño apropiado y luego, después de un poco de contabilidad, llamo al siguiente procedimiento, pasándole tres punteros a los respectivos comienzos de las matrices para el operando izquierdo y derecho y el resultado, así como el número de extremidades para izquierda y derecha, respectivamente.

Código simple :

class procedure BigInteger.PlainAdd(Left, Right, Result: PLimb; LSize, RSize: Integer); 
asm
// EAX = Left, EDX = Right, ECX = Result
        PUSH    ESI
        PUSH    EDI
        PUSH    EBX
        MOV     ESI,EAX                 // Left
        MOV     EDI,EDX                 // Right
        MOV     EBX,ECX                 // Result
        MOV     ECX,RSize               // Number of limbs at Left
        MOV     EDX,LSize               // Number of limbs at Right
        CMP     EDX,ECX
        JAE     @SkipSwap
        XCHG    ECX,EDX                 // Left and LSize should be largest
        XCHG    ESI,EDI                 // so swap
@SkipSwap:
        SUB     EDX,ECX                 // EDX contains rest
        PUSH    EDX                     // ECX contains smaller size
        XOR     EDX,EDX                  
@MainLoop:
        MOV     EAX,[ESI + CLimbSize*EDX]  // CLimbSize = SizeOf(TLimb) = 4.
        ADC     EAX,[EDI + CLimbSize*EDX]
        MOV     [EBX + CLimbSize*EDX],EAX
        INC     EDX
        DEC     ECX
        JNE     @MainLoop
        POP     EDI                        
        INC     EDI                        // Do not change Carry Flag
        DEC     EDI
        JE      @LastLimb
@RestLoop:
        MOV     EAX,[ESI + CLimbSize*EDX]
        ADC     EAX,ECX
        MOV     [EBX + CLimbSize*EDX],EAX
        INC     EDX
        DEC     EDI
        JNE     @RestLoop
@LastLimb:
        ADC     ECX,ECX                    // Add in final carry
        MOV     [EBX + CLimbSize*EDX],ECX
@Exit:
        POP     EBX
        POP     EDI
        POP     ESI
end;
// RET is inserted by Delphi compiler.

Este código funcionó bien, y quedé bastante satisfecho con él, hasta que me di cuenta de que, en mi configuración de desarrollo (Win7 en una VM Parallels en un iMac), una simple rutina de adición PURE PASCAL, haciendo lo mismo al emular el carry con una variable y unas pocas cláusulas, if , fueron más rápidas que mi rutina simple y directa de ensamblador artesanal.

Me llevó un tiempo descubrir que en ciertas CPU (incluida mi iMac y una computadora portátil más antigua), la combinación de DEC o INC y ADC o SBB podría ser extremadamente lenta. Pero en la mayoría de mis otros (tengo otras cinco PC para probarlo, aunque cuatro de estos son exactamente iguales), fue bastante rápido.

Entonces escribí una nueva versión, emulando INC y DEC usando LEA y JECXZ , así:

Parte del código de emulación :

@MainLoop:
        MOV     EAX,[ESI + EDX*CLimbSize]
        LEA     ECX,[ECX - 1]                   // Avoid INC and DEC, see above.
        ADC     EAX,[EDI + EDX*CLimbSize]
        MOV     [EBX + EDX*CLimbSize],EAX
        LEA     EDX,[EDX + 1]
        JECXZ   @DoRestLoop                     // LEA does not modify Zero flag, so JECXZ is used.
        JMP     @MainLoop
@DoRestLoop:
// similar code for the rest loop 

Eso hizo que mi código en las máquinas "lentas" fuera casi tres veces más rápido, pero un 20% más lento en las máquinas "más rápidas". Así que ahora, como código de inicialización, hago un bucle de sincronización simple y lo uso para decidir si configuraré la unidad para llamar a la (s) rutina (s) simple o emulada. Esto casi siempre es correcto, pero a veces elige las rutinas simples (más lentas) cuando debería haber elegido las rutinas de emulación.

Pero no sé si esta es la mejor manera de hacerlo.

Pregunta

Di mi solución, pero ¿acaso los gurús de asm aquí quizás conozcan una mejor manera de evitar la lentitud en ciertas CPU?

Actualizar

Las respuestas de Peter y Nils me ayudaron mucho a encontrar el camino correcto. Esta es la parte principal de mi solución final para la versión DEC :

Código simple:

class procedure BigInteger.PlainAdd(Left, Right, Result: PLimb; LSize, RSize: Integer);
asm
        PUSH    ESI
        PUSH    EDI
        PUSH    EBX
        MOV     ESI,EAX                         // Left
        MOV     EDI,EDX                         // Right
        MOV     EBX,ECX                         // Result
        MOV     ECX,RSize
        MOV     EDX,LSize
        CMP     EDX,ECX
        JAE     @SkipSwap
        XCHG    ECX,EDX
        XCHG    ESI,EDI
@SkipSwap:
        SUB     EDX,ECX
        PUSH    EDX
        XOR     EDX,EDX
        XOR     EAX,EAX
        MOV     EDX,ECX
        AND     EDX,$00000003
        SHR     ECX,2
        CLC
        JE      @MainTail
@MainLoop:
        // Unrolled 4 times. More times will not improve speed anymore.
        MOV     EAX,[ESI]
        ADC     EAX,[EDI]
        MOV     [EBX],EAX
        MOV     EAX,[ESI + CLimbSize]
        ADC     EAX,[EDI + CLimbSize]
        MOV     [EBX + CLimbSize],EAX
        MOV     EAX,[ESI + 2*CLimbSize]
        ADC     EAX,[EDI + 2*CLimbSize]
        MOV     [EBX + 2*CLimbSize],EAX
        MOV     EAX,[ESI + 3*CLimbSize]
        ADC     EAX,[EDI + 3*CLimbSize]
        MOV     [EBX + 3*CLimbSize],EAX
        // Update pointers.
        LEA     ESI,[ESI + 4*CLimbSize]
        LEA     EDI,[EDI + 4*CLimbSize]
        LEA     EBX,[EBX + 4*CLimbSize]
        // Update counter and loop if required.
        DEC     ECX                             
        JNE     @MainLoop
@MainTail:
        // Add index*CLimbSize so @MainX branches can fall through.
        LEA     ESI,[ESI + EDX*CLimbSize]
        LEA     EDI,[EDI + EDX*CLimbSize]
        LEA     EBX,[EBX + EDX*CLimbSize]
        // Indexed jump.
        LEA     ECX,[@JumpsMain]
        JMP     [ECX + EDX*TYPE Pointer]
        // Align jump table manually, with NOPs. Update if necessary.
        NOP
// Jump table.
@JumpsMain:
        DD      @DoRestLoop
        DD      @Main1
        DD      @Main2
        DD      @Main3
@Main3:
        MOV     EAX,[ESI - 3*CLimbSize]
        ADC     EAX,[EDI - 3*CLimbSize]
        MOV     [EBX - 3*CLimbSize],EAX
@Main2:
        MOV     EAX,[ESI - 2*CLimbSize]
        ADC     EAX,[EDI - 2*CLimbSize]
        MOV     [EBX - 2*CLimbSize],EAX
@Main1:
        MOV     EAX,[ESI - CLimbSize]
        ADC     EAX,[EDI - CLimbSize]
        MOV     [EBX - CLimbSize],EAX
@DoRestLoop:

// etc...    

Eliminé mucho espacio en blanco, y supongo que el lector puede obtener el resto de la rutina. Es similar al bucle principal. Una mejora de velocidad de aprox. 20% para BigIntegers más grandes, y alrededor del 10% para los pequeños (solo unas pocas extremidades).

La versión de 64 bits ahora usa la adición de 64 bits siempre que sea posible (en el bucle principal y en Main3 y Main2, que no son "fall-through" como arriba) y antes, 64 bit era bastante más lento que 32 bit, pero ahora es 30% más rápido que 32 bits y el doble de rápido que el bucle simple original de 64 bits.

Actualización 2

Intel propone, en su Manual de referencia de optimización de arquitecturas Intel 64 e IA-32 , 3.5.2.6 Puestos de registro de bandera parcial - Ejemplo 3-29 :

        XOR     EAX,EAX

        .ALIGN  16

@MainLoop:

        ADD     EAX,[ESI]       // Sets all flags, so no partial flag register stall
        ADC     EAX,[EDI]       // ADD added in previous carry, so its result might have carry
        MOV     [EBX],EAX
        MOV     EAX,[ESI + CLimbSize]
        ADC     EAX,[EDI + CLimbSize]
        MOV     [EBX + CLimbSize],EAX
        MOV     EAX,[ESI + 2*CLimbSize]
        ADC     EAX,[EDI + 2*CLimbSize]
        MOV     [EBX + 2*CLimbSize],EAX
        MOV     EAX,[ESI + 3*CLimbSize]
        ADC     EAX,[EDI + 3*CLimbSize]
        MOV     [EBX + 3*CLimbSize],EAX
        SETC    AL              // Save carry for next iteration
        MOVZX   EAX,AL
        ADD     ESI,CUnrollIncrement*CLimbSize  // LEA has slightly worse latency
        ADD     EDI,CUnrollIncrement*CLimbSize
        ADD     EBX,CUnrollIncrement*CLimbSize
        DEC     ECX
        JNZ     @MainLoop

La bandera se guarda en AL , y a través de MOVZX en EAX . Se agrega a través del primer ADD en el bucle. Entonces se necesita un ADC , porque el ADD podría generar un carry. Ver también comentarios.

Debido a que el carry se guarda en EAX , también puedo usar ADD para actualizar los punteros. El primer ADD en el bucle también actualiza todas las banderas, por lo que ADC no sufrirá un bloqueo parcial del registro de banderas.

Answer 1

Hay tantos chips x86 con tiempos de uso muy diferentes que no se puede tener un código óptimo para todos. Su enfoque para tener dos buenas funciones conocidas y un punto de referencia antes de usarlo ya es bastante avanzado.

Sin embargo, dependiendo del tamaño de sus BigIntegers, es probable que pueda mejorar su código simplemente desenrollando el bucle. Eso eliminará el bucle de arriba drásticamente.

Por ejemplo, podría ejecutar un bloque especializado que agregue ocho enteros como este:

@AddEight:
        MOV     EAX,[ESI + EDX*CLimbSize + 0*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 0*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 0*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 1*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 1*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 1*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 2*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 2*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 2*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 3*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 3*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 3*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 4*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 4*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 4*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 5*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 5*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 5*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 6*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 6*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 6*CLimbSize],EAX
        MOV     EAX,[ESI + EDX*CLimbSize + 7*CLimbSize]
        ADC     EAX,[EDI + EDX*CLimbSize + 7*CLimbSize]
        MOV     [EBX + EDX*CLimbSize + 7*CLimbSize],EAX
        LEA     ECX,[ECX - 8]

Ahora reconstruye su bucle, ejecuta el bloque anterior siempre que tenga más de 8 elementos para procesar y haga los pocos elementos restantes utilizando el bucle de suma de un solo elemento que ya tiene.

Para BitIntegers grandes, pasará la mayor parte del tiempo en la parte desenrollada, que ahora debería ejecutarse mucho más rápido.

Si lo desea aún más rápido, escriba siete bloques adicionales que estén especializados en los recuentos de elementos restantes y bifurque a ellos según el recuento de elementos. Esto se puede hacer mejor almacenando las siete direcciones en una tabla de búsqueda, cargando la dirección desde allí y saltando directamente al código especializado.

Para recuentos de elementos pequeños, esto elimina completamente el bucle completo y para elementos grandes obtendrá el beneficio completo del bucle desenrollado.

Answer 2

Lo que estás viendo es un puesto de bandera parcial.

Las CPU Intel (que no sean P4) cambian el nombre de cada bit de indicador por separado, por lo que JNE solo depende de la última instrucción que establezca todos los indicadores que usa (en este caso, solo el indicador Z ). De hecho, las CPU Intel recientes pueden incluso combinar internamente un inc/jne en un único uop inc-and-branch (macro-fusión). Sin embargo, el problema surge cuando se lee un bit de marca que no se modificó en la última instrucción que actualizó las marcas.

Agner Fog dice que las CPU Intel (incluso PPro / PII) no se estancan en inc / jnz . En realidad, no es el inc/jnz que se está estancando, es el adc en la próxima iteración que tiene que leer la bandera CF después de que inc escribió otras banderas pero dejó CF sin modificar.

; Example 5.21. Partial flags stall when reading unmodified flag bits
cmp eax, ebx
inc ecx
jc xx
; Partial flags stall  (P6 / PIII / PM / Core2 / Nehalem)

Agner Fog también dice de manera más general: "Evite el código que se basa en el hecho de que INC o DEC deja la bandera de transporte sin cambios". (para Pentium M / Core2 / Nehalem). La sugerencia para evitar inc / dec completo es obsoleta y solo se aplica a P4. Otras CPU cambian el nombre de diferentes partes de EFLAGS por separado, y solo tienen problemas cuando se requiere la fusión (leer un indicador que no fue modificado por la última información para escribir cualquier indicador).

En las máquinas donde es rápido (Sandybridge y posterior), están insertando una uop adicional para fusionar el registro de banderas cuando lee bits que no fueron escritos por la última instrucción que lo modificó. Esto es mucho más rápido que demorarse durante 7 ciclos, pero aún así no es ideal.

P4 siempre rastrea registros completos, en lugar de renombrar registros parciales, ni siquiera EFLAGS. Por lo tanto, inc/jz tiene una dependencia "falsa" de lo que sea que haya escrito las banderas antes. Esto significa que la condición del bucle no puede detectar el final del bucle hasta que llegue la ejecución de la cadena adc dep, por lo que la predicción errónea de la rama que puede ocurrir cuando la rama del bucle deja de tomarse no se puede detectar temprano. Sin embargo, previene los puestos de banderas parciales.

Su lea / jecxz evita el problema muy bien. Es más lento en SnB y más tarde porque no desenrollaste tu bucle en absoluto. Su versión LEA es de 11 uops (puede emitir una iteración por 3 ciclos), mientras que la versión inc es de 7 uops (puede emitir un iter por 2 ciclos), sin contar la unión de banderas que inserta en lugar de detenerse.

Si la instrucción de loop no fuera lenta , sería perfecta para esto. En realidad, es rápido en la familia AMD Bulldozer (1 m-op, el mismo costo que una comparación y rama fusionada) y Via Nano3000. Sin embargo, es malo en todas las CPU Intel (7 uops en la familia SnB).

Desenrollar

Cuando se desenrolla, puede obtener otra pequeña ganancia al usar punteros en lugar de modos de direccionamiento indexados, porque los modos de direccionamiento de 2 registros no pueden fusionarse en SnB y más adelante . Un grupo de instrucciones de carga / adc / tienda es 6 uops sin micro fusión, pero solo 4 con micro fusión. Las CPU pueden emitir 4 uops / clock de dominio fusionado. (Consulte el documento de microarquitectura de CPU de Agner Fog y las tablas de instrucciones para obtener detalles sobre este nivel).

Guarde uops cuando pueda para asegurarse de que la CPU pueda emitir instrucciones más rápido que la ejecución, para asegurarse de que pueda ver lo suficientemente adelante en el flujo de instrucciones para absorber cualquier burbuja en la búsqueda de información (por ejemplo, error de predicción de rama). Encajar en el búfer de bucle 28uop también significa ahorro de energía (y en Nehalem, evitando cuellos de botella de decodificación de instrucciones). Hay cosas como la alineación de instrucciones y el cruce de los límites de la línea de caché uop que dificultan mantener 4 uops / reloj sin el bucle tampón también.

Otro truco es mantener los punteros hasta el final de los búferes y contar hasta cero. (Entonces, al comienzo de tu ciclo, obtienes el primer elemento como end[-idx] ).

        ; pure loads are always one uop, so we can still index it
        ; with no perf hit on SnB
        add     esi, ecx   ; point to end of src1
        neg     ecx

UNROLL equ 4
@MainLoop:
        MOV     EAX, [ESI + 0*CLimbSize + ECX*CLimbSize]
        ADC     EAX, [EDI + 0*CLimbSize]
        MOV     [EBX + 0*CLimbSize], EAX

        MOV     EAX, [ESI + 1*CLimbSize + ECX*CLimbSize]
        ADC     EAX, [EDI + 1*CLimbSize]
        MOV     [EBX + 1*CLimbSize], EAX

        ; ... repeated UNROLL times.  Use an assembler macro to repeat these 3 instructions with increasing offsets

        LEA     ECX, [ECX+UNROLL] ; loop counter

        LEA     EDI, [EDI+ClimbSize*UNROLL]  ; Unrolling makes it worth doing
        LEA     EBX, [EBX+ClimbSize*UNROLL]  ; a separate increment to save a uop for every ADC and store on SnB & later.

        JECXZ   @DoRestLoop                     // LEA does not modify Zero flag, so JECXZ is used.
        JMP     @MainLoop
@DoRestLoop:

Un roll de 4 debería ser bueno. No es necesario exagerar, ya que eres un problema. va a poder saturar los puertos de carga / almacenamiento de pre-Haswell con un despliegue de solo 3 o 4, tal vez incluso 2.

Un desenrollado de 2 hará que el bucle anterior sea exactamente 14 uops de dominio fusionado para CPU de Intel. adc es 2 ALU (+1 memoria fusionada), jecxz es 2, el resto (incluido LEA) son todos 1. En el dominio no fusionado, 10 ALU / rama y 6 memoria (bueno, 8 memoria si realmente cuenta la dirección de la tienda y almacenar datos por separado).

• 14 Uops de dominio fusionado por iteración: emita una iteración por 4 relojes. (Los 2 uops impares al final tienen que emitirse como un grupo de 2, incluso desde el búfer de bucle).
• 10 ALU y rama Uops: Toma 3.33c para ejecutarlos todos en pre-haswell. Tampoco creo que ningún puerto sea un cuello de botella: los uops de adc pueden ejecutarse en cualquier puerto, y lea puede ejecutarse en p0 / p1. Los saltos usan el puerto 5 (y jecx también usa uno de p0 / p1)
• 6 operaciones de memoria: toma 3c para ejecutarse en CPUs anteriores a Haswell, que pueden manejar 2 por reloj. Haswell agregó un AGU dedicado para tiendas para que pueda soportar 2 carga + 1 tienda / reloj.

Entonces, para las CPU pre-haswell, usando LEA / JECXZ, un desenrollado de 2 no saturará ni el ALU ni los puertos de carga / almacenamiento. Un desenrollado de 4 lo llevará hasta 22 uops fusionados (6 ciclos para emitir). 14 ALU y rama: 4.66c para ejecutar. 12 memorias: 6 ciclos para ejecutar. Por lo tanto, un despliegue de 4 saturará las CPU anteriores a Haswell, pero solo apenas. La CPU no tendrá ningún búfer de instrucciones para pasar por una rama de predicción errónea.

Haswell y versiones posteriores siempre tendrán un cuello de botella en el frontend (4 uops por límite de reloj), porque el combo load / adc / store toma 4 uops, y puede mantenerse en uno por reloj. Por lo tanto, nunca hay "espacio" para la sobrecarga del bucle sin reducir el rendimiento del adc . Aquí es donde debes saber no exagerar y desenrollar demasiado.

En Broadwell / Skylake, adc es solo una única uop con latencia 1c, y cargar / adc r, m / store parece ser la mejor secuencia. adc m, r/i es 4 uops. Esto debería sostener un adc por reloj, como AMD.

En las CPU AMD, adc es solo una macrooperación, por lo que si la CPU puede mantener una tasa de emisión de 4 (es decir, sin cuellos de botella de decodificación), también puede usar su puerto de 2 cargas / 1 tienda para vencer a Haswell. Además, jecxz en AMD es tan eficiente como cualquier otra rama: solo una macrooperación. Las matemáticas de precisión múltiple son una de las pocas cosas en las que las CPU de AMD son buenas. Las latencias más bajas en algunas instrucciones enteras les dan una ventaja en algunas rutinas GMP.

Un despliegue de más de 5 podría afectar el rendimiento en Nehalem, porque eso haría que el bucle sea más grande que el búfer de bucle 28uop. La decodificación de instrucciones lo limitaría a menos de 4 uops por reloj. Incluso antes (Core2), hay un búfer de bucle de instrucciones x86 de 64B (64B de código x86, no uops), que ayuda a algunos con la decodificación.

A menos que esta rutina adc sea ​​el único cuello de botella en su aplicación, mantendría el factor de desenrollado hasta quizás 2. O tal vez incluso no se desenrolle, si eso ahorra mucho código de prólogo / epílogo, y sus BigInts no son demasiado grandes. No desea hinchar demasiado el código y crear errores de caché cuando las personas que llaman llaman a muchas funciones diferentes de BigInteger, como agregar, sub, mul y hacer otras cosas intermedias. Desenrollar demasiado para ganar en microbenchmarks puede dispararse en el pie si su programa no pasa mucho tiempo en su ciclo interno en cada llamada.

Si sus valores de BigInt no suelen ser gigantescos, entonces no es solo el ciclo que debe ajustar. Un desenrollado más pequeño podría ser bueno para simplificar la lógica del prólogo / epílogo. Asegúrese de verificar las longitudes para que ECX no cruce cero sin ser cero, por supuesto. Este es el problema con el desenrollado y los vectores. : /

Guardar / restaurar CF para CPU antiguas, en lugar de bucles sin banderas:

Esta podría ser la forma más eficiente:

lahf
# clobber flags
sahf              ; cheap on AMD and Intel.  This doesn''t restore OF, but we only care about CF

# or

setc al
# clobber flags
add  al, 255      ; generate a carry if al is non-zero

Usar el mismo registro que la cadena adc dep no es realmente un problema: eax siempre estará listo al mismo tiempo que la salida CF del último adc . (En AMD y P4 / Silvermont, las escrituras de registro parcial tienen un dep falso en el registro completo. No cambian el nombre de los registros parciales por separado). El guardado / restauración es parte de la cadena de depósito de ADC, no la cadena de depósito de condición de bucle.

La condición de bucle solo verifica los indicadores escritos por cmp , sub o dec . Guardar / restaurar banderas a su alrededor no lo hace parte de la cadena adc dep, por lo que la rama de predicción errónea al final del bucle se puede detectar antes de que llegue la ejecución adc . (Una versión anterior de esta respuesta se equivocó).

Es casi seguro que hay espacio para eliminar las instrucciones en el código de configuración, tal vez mediante el uso de registros donde comienzan los valores. No tiene que usar edi y esi para los punteros, aunque sé que hace que el desarrollo inicial sea más fácil cuando usa registros de manera consistente con su uso "tradicional". (por ejemplo, puntero de destino en EDI).

¿Delphi te permite usar ebp ? Es bueno tener un séptimo registro.

Obviamente, el código de 64 bits haría que su código de BigInt se ejecute aproximadamente el doble de rápido, a pesar de que tendría que preocuparse por hacer un solo 32c adc al final de un bucle de 64 bits adc . También le daría el doble de la cantidad de registros.