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.