Problemas con ADC / SBB e INC / DEC en bucles ajustados en algunas CPU

Estoy escribiendo un tipo BigInteger simple 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 BigInteger nuevo del tamaño apropiado y luego, después de un teneduría de libros, llamo al siguiente procedimiento, pasando tres punteros a los respectivos inicios de las matrices para el operando izquierdo y derecho y el resultado, así como el número de miembros 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 noté que, en mi configuración de desarrollo (Win7 en una máquina virtual Parallels en un iMac) una rutina de adición PURE PASCAL simple, haciendo lo mismo mientras emulaba el acarreo con una variable y unas pocas cláusulas if , fue más rápido que mi simple rutina de ensamblador artesanal.

Me tomó un tiempo descubrir que en ciertas CPU (incluyendo mi iMac y una computadora portátil más vieja), 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 ellas son exactamente las mismas), fue bastante rápido.

Así que escribí una nueva versión, emulando INC y DEC utilizando LEA y JECXZ en JECXZ lugar, 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” 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 ciclo de temporización simple y lo uso para decidir si configuraré la unidad para llamar a la (s) rutina (s) simple (s) o emulada (s). Esto es casi siempre 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 hacer esto.

Pregunta

Di mi solución, pero ¿los gurús del 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 seguir 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... 

Quité un montón de espacio en blanco, y creo que el lector puede obtener el rest de la rutina. Es similar al bucle principal. Una mejora de velocidad de aprox. 20% para BigIntegers más grandes, y un 10% para BigIntegers más grandes (solo unas pocas extremidades).

La versión de 64 bits ahora usa 64 bits cuando es posible (en el bucle principal y en Main3 y Main2, que no son “fall-through” como se muestra arriba) y antes, 64 bit era bastante más lento que 32 bit, pero ahora es un 30% más rápido que 32 bits y dos veces más rápido que el bucle simple original de 64 bits.

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

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

Agner Fog dice que las CPU Intel (incluso PPro / PII) no se inc / jnz en inc / jnz . En realidad no es el inc/jnz que se está estancando, es el adc en la próxima iteración el 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 en términos más generales: “Evite el código que se basa en el hecho de que INC o DEC deja la bandera de acarreo sin cambios”. (para Pentium M / Core2 / Nehalem). La sugerencia de evitar inc / dec completamente está obsoleta y solo se aplicó a P4. Otras CPU renombran diferentes partes de EFLAGS por separado, y solo tienen problemas cuando se requiere una fusión (leer una bandera que no fue modificada por la última entrada para escribir banderas).

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

P4 siempre rastrea registros enteros, en lugar de renombrar registros parciales, ni siquiera EFLAGS. Así que inc/jz tiene una dependencia “falsa” de lo que haya escrito las banderas antes. Esto significa que la condición de bucle no puede detectar el final del bucle hasta que la ejecución de la cadena de depc adc llegue allí, por lo que la derivación incorrecta de bifurcación que puede ocurrir cuando la bucle-twig deja de tomarse no se puede detectar temprano. Sin embargo, previene las paradas 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 loop en absoluto. Su versión de 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 una iter por 2 ciclos), sin contar la combinación de banderas que se inserta en lugar de estancarse.

Si la instrucción de loop no fue lenta , sería perfecto para esto. En realidad es rápido en AMD Bulldozer-family (1 m-op, el mismo costo que una fusión fusionada-y-branch), 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 usando punteros en lugar de modos de direccionamiento indexados, ya que los modos de direccionamiento de 2 regtos no pueden micro fusibles en SnB y posterior . Un grupo de instrucciones load / adc / store es de 6 uops sin microfusión, pero solo 4 con microfusión. Las CPU pueden emitir 4 uops / clock de dominio fusionado. (Consulte el documento de microarch 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 ejecutar, para asegurarse de que pueda ver lo suficientemente lejos en la secuencia de instrucciones como para absorber cualquier burbuja en la búsqueda de entrada (por ejemplo, error en la derivación). El ajuste en el búfer de bucle 28uop también significa ahorro de energía (y en Nehalem, evitando cuellos de botella de deencoding 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 hacen difícil mantener un total de 4 uops / reloj sin el bucle búfer, también.

Otro truco es mantener los punteros al final de sus buffers, y contar hacia cero. (Por lo tanto, al comienzo de su ciclo, obtiene 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 desenrollar 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 desenrollado de solo 3 o 4, tal vez incluso 2.

Un desenrollar de 2 hará que el bucle anterior muestre exactamente 14 Uops de dominio fusionado para las CPU de Intel. adc es 2 ALU (+1 memoria fusionada), jecxz es 2, el rest (incluido LEA) son todos 1. En el dominio no fusionado, 10 ALU / twig 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 cada 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 & branch 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 port5 (y jecx también usa uno de p0 / p1)
  • 6 operaciones de memoria: Toma 3c para ejecutar en CPU pre-Haswell, que puede manejar 2 por reloj. Haswell agregó una AGU dedicada para tiendas para que pueda soportar 2 cargas + 1 tienda / reloj.

Por lo tanto, para las CPU pre-haswell, usando LEA / JECXZ, un desenrollado de 2 no saturará completamente la ALU o los puertos de carga / almacenamiento. Un desenrollar de 4 traerá hasta 22 uops fusionados (6 ciclos para emitir). 14 ALU & branch: 4.66c para ejecutar. 12 memoria: 6 ciclos para ejecutar. Por lo tanto, un desenrollado de 4 saturará CPUs pre-Haswell, pero solo apenas. La CPU no tendrá ningún búfer de instrucciones para batir a través de una ruta incorrecta.

Haswell y más tarde 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 a uno por reloj. Por lo tanto, nunca hay “espacio” para la sobrecarga del ciclo sin reducir el rendimiento de adc . Aquí es donde debes saber que no debes exagerar y desenrollar demasiado.

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

En las CPU AMD, adc es solo una macrooperación, por lo que si la CPU puede soportar una tasa de problemas de 4 (es decir, sin cuellos de botella de deencoding), también pueden usar sus 2 puertos de carga / 1 tienda para vencer a Haswell. Además, jecxz en AMD es tan eficiente como cualquier otra twig: solo una macrooperación. La matemática de precisión múltiple es una de las pocas cosas en las que los procesadores AMD son buenos. Las latencias más bajas en algunas instrucciones enteras les dan una ventaja en algunas rutinas GMP.


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

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

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


Guardar / restaurar CF para CPUs antiguas, en lugar de bucle sin marca:

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

 lahf # clobber flags sahf ; cheap on AMD and Intel. This doesn't restre 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 de distribución adc no es realmente un problema: eax siempre estará listo al mismo tiempo que la salida de CF del último adc . (En AMD y P4 / las grabaciones parciales de Silvermont tienen un depósito falso en el registro completo. No cambian el nombre de las reglas parciales por separado). El save / restre es parte de la cadena de dep adc, no de la cadena de dep de condición de bucle.

La condición de bucle solo verifica las marcas escritas por cmp , sub o dec . Guardar / restaurar indicadores a su alrededor no lo hace parte de la cadena de dep adc , por lo que la derivación incorrecta de la bifurcación al final del bucle puede detectarse antes de que la ejecución adc llegue allí. (Una versión anterior de esta respuesta entendió mal).


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 es necesario usar edi y esi para los punteros, aunque sé que facilita el desarrollo inicial cuando usa registros de forma consistente con su uso “tradicional”. (por ejemplo, puntero de destino en EDI).

¿Delphi te deja usar ebp ? Es bueno tener un 7º registro.

Obviamente, el código de 64 bits haría que tu código de BigInt se ejecutara aproximadamente el doble de rápido, aunque tendrías que preocuparte por hacer un solo adc 32b al final de un ciclo de 64 bits adc . También le daría 2 veces la cantidad de registros.

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

Sin embargo, dependiendo del tamaño de sus BigIntegers, es probable que pueda mejorar su código simplemente desenrollando los bucles. Eso eliminará la sobrecarga del bucle 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, ejecute el bloque anterior siempre que tenga más de 8 elementos para procesar y haga los pocos elementos restantes utilizando el bucle de sum de elemento único que ya tiene.

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

Si lo quiere aún más rápido, escriba siete bloques adicionales que estén especializados para los conteos de elementos restantes y bifurque a ellos en función del 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 por completo el ciclo completo y para los elementos grandes obtendrá el máximo beneficio del ciclo desenrollado.