Antecedentes:
Al optimizar un código Pascal con lenguaje ensamblador incorporado, noté una MOVinstrucción innecesaria y la eliminé.
Para mi sorpresa, eliminar las instrucciones innecesarias hizo que mi programa se ralentizara .
Descubrí que agregar MOVinstrucciones arbitrarias e inútiles aumentaba aún más el rendimiento .
El efecto es errático y los cambios se basan en el orden de ejecución: las mismas instrucciones basura transpuestas hacia arriba o hacia abajo por una sola línea producen una desaceleración .
Entiendo que la CPU realiza todo tipo de optimizaciones y racionalizaciones, pero esto parece más magia negra.
Los datos:
Una versión de mi código compila condicionalmente tres operaciones basura en medio de un ciclo que ejecuta 2**20==1048576tiempos. (El programa circundante solo calcula los hash SHA-256 ).
Los resultados en mi máquina bastante antigua (Intel (R) Core (TM) 2 CPU 6400 @ 2.13 GHz):
avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without: 1836.44 ms
Los programas se ejecutaron 25 veces en un bucle, con el orden de ejecución cambiando al azar cada vez.
Extracto:
{$asmmode intel}
procedure example_junkop_in_sha256;
var s1, t2 : uint32;
begin
// Here are parts of the SHA-256 algorithm, in Pascal:
// s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
// s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
// Here is how I translated them (side by side to show symmetry):
asm
MOV r8d, a ; MOV r9d, e
ROR r8d, 2 ; ROR r9d, 6
MOV r10d, r8d ; MOV r11d, r9d
ROR r8d, 11 {13 total} ; ROR r9d, 5 {11 total}
XOR r10d, r8d ; XOR r11d, r9d
ROR r8d, 9 {22 total} ; ROR r9d, 14 {25 total}
XOR r10d, r8d ; XOR r11d, r9d
// Here is the extraneous operation that I removed, causing a speedup
// s1 is the uint32 variable declared at the start of the Pascal code.
//
// I had cleaned up the code, so I no longer needed this variable, and
// could just leave the value sitting in the r11d register until I needed
// it again later.
//
// Since copying to RAM seemed like a waste, I removed the instruction,
// only to discover that the code ran slower without it.
{$IFDEF JUNKOPS}
MOV s1, r11d
{$ENDIF}
// The next part of the code just moves on to another part of SHA-256,
// maj { r12d } := (a and b) xor (a and c) xor (b and c)
mov r8d, a
mov r9d, b
mov r13d, r9d // Set aside a copy of b
and r9d, r8d
mov r12d, c
and r8d, r12d { a and c }
xor r9d, r8d
and r12d, r13d { c and b }
xor r12d, r9d
// Copying the calculated value to the same s1 variable is another speedup.
// As far as I can tell, it doesn't actually matter what register is copied,
// but moving this line up or down makes a huge difference.
{$IFDEF JUNKOPS}
MOV s1, r9d // after mov r12d, c
{$ENDIF}
// And here is where the two calculated values above are actually used:
// T2 {r12d} := S0 {r10d} + Maj {r12d};
ADD r12d, r10d
MOV T2, r12d
end
end;
Inténtalo tú mismo:
El código está en línea en GitHub si quieres probarlo tú mismo.
Mis preguntas:
- ¿Por qué copiar inútilmente el contenido de un registro a la RAM aumentaría el rendimiento?
- ¿Por qué la misma instrucción inútil proporcionaría una aceleración en algunas líneas y una desaceleración en otras?
- ¿Es este comportamiento algo que un compilador podría explotar de manera predecible?
fuente
Respuestas:
La causa más probable de la mejora de la velocidad es que:
Su Core2 no mantiene un registro de historial separado para cada salto condicional. En cambio, mantiene un historial compartido de todos los saltos condicionales. Una desventaja de la predicción de rama global es que el historial se diluye con información irrelevante si los diferentes saltos condicionales no están correlacionados.
Este pequeño tutorial de predicción de rama muestra cómo funcionan los búferes de predicción de rama. El búfer de caché está indexado por la parte inferior de la dirección de la instrucción de bifurcación. Esto funciona bien a menos que dos ramas importantes no correlacionadas compartan los mismos bits inferiores. En ese caso, terminas con alias que causa muchas ramas mal predichas (que detiene la canalización de instrucciones y ralentiza tu programa).
Si desea comprender cómo las predicciones erróneas de las ramas afectan el rendimiento, eche un vistazo a esta excelente respuesta: https://stackoverflow.com/a/11227902/1001643
Los compiladores generalmente no tienen suficiente información para saber qué ramas tendrán un alias y si esos alias serán significativos. Sin embargo, esa información se puede determinar en tiempo de ejecución con herramientas como Cachegrind y VTune .
fuente
Es posible que desee leer http://research.google.com/pubs/pub37077.html
TL; DR: la inserción aleatoria de instrucciones nop en los programas puede aumentar fácilmente el rendimiento en un 5% o más, y no, los compiladores no pueden explotar esto fácilmente. Por lo general, es una combinación de predicción de ramificación y comportamiento de caché, pero también puede ser, por ejemplo, una parada de la estación de reserva (incluso en el caso de que no haya cadenas de dependencia que estén rotas o que haya sobre-suscripciones de recursos evidentes).
fuente
Creo que en las CPU modernas, las instrucciones de ensamblaje, aunque son la última capa visible para un programador para proporcionar instrucciones de ejecución a una CPU, en realidad son varias capas de la ejecución real de la CPU.
Las CPU modernas son híbridos RISC / CISC que traducen las instrucciones CISC x86 en instrucciones internas que tienen un comportamiento más RISC. Además, hay analizadores de ejecución fuera de orden, predictores de rama, "fusión de micro-operaciones" de Intel que intentan agrupar las instrucciones en lotes más grandes de trabajo simultáneo (algo así como el VLIW / Itanium titanic). Incluso hay límites de caché que podrían hacer que el código se ejecute más rápido para Dios sabe por qué si es más grande (tal vez el controlador de caché lo ranura de manera más inteligente o lo mantiene por más tiempo).
CISC siempre ha tenido una capa de traducción de ensamblado a microcódigo, pero el punto es que con las CPU modernas las cosas son mucho mucho más complicadas. Con todo el espacio extra del transistor en las plantas modernas de fabricación de semiconductores, las CPU probablemente pueden aplicar varios enfoques de optimización en paralelo y luego seleccionar el que al final proporciona la mejor aceleración. Las instrucciones adicionales pueden estar sesgando la CPU para usar una ruta de optimización que sea mejor que otras.
El efecto de las instrucciones adicionales probablemente depende del modelo / generación / fabricante de la CPU, y no es probable que sea predecible. Optimizar el lenguaje ensamblador de esta manera requeriría la ejecución en muchas generaciones de arquitectura de CPU, tal vez utilizando rutas de ejecución específicas de la CPU, y solo sería deseable para secciones de código realmente muy importantes, aunque si está haciendo ensamblaje, probablemente ya lo sepa.
fuente
Preparando el caché
Mover operaciones a la memoria puede preparar el caché y acelerar las operaciones de movimiento posteriores. Una CPU generalmente tiene dos unidades de carga y una unidad de almacenamiento. Una unidad de carga puede leer desde la memoria en un registro (una lectura por ciclo), una unidad de almacenamiento almacena desde el registro en la memoria. También hay otras unidades que realizan operaciones entre registros. Todas las unidades funcionan en paralelo. Entonces, en cada ciclo, podemos hacer varias operaciones a la vez, pero no más de dos cargas, una tienda y varias operaciones de registro. Por lo general, son hasta 4 operaciones simples con registros simples, hasta 3 operaciones simples con registros XMM / YMM y 1-2 operaciones complejas con cualquier tipo de registro. Su código tiene muchas operaciones con registros, por lo que una operación de almacenamiento de memoria ficticia es gratuita (ya que hay más de 4 operaciones de registro de todos modos), pero prepara la memoria caché para la operación de almacenamiento posterior. Para saber cómo funcionan los almacenes de memoria, consulte elManual de referencia de optimización de arquitecturas Intel 64 e IA-32 .
Romper las falsas dependencias
Aunque esto no se refiere exactamente a su caso, pero a veces el uso de operaciones mov de 32 bits bajo el procesador de 64 bits (como en su caso) se usa para borrar los bits más altos (32-63) y romper las cadenas de dependencia.
Es bien sabido que bajo x86-64, el uso de operandos de 32 bits borra los bits más altos del registro de 64 bits. Lea la sección correspondiente - 3.4.1.1 - del Manual del desarrollador de software de arquitecturas Intel® 64 e IA-32 Volumen 1 :
Entonces, las instrucciones mov, que pueden parecer inútiles a primera vista, borran los bits más altos de los registros apropiados. ¿Qué nos da? Rompe las cadenas de dependencia y permite que las instrucciones se ejecuten en paralelo, en orden aleatorio, mediante el algoritmo Fuera de servicio implementado internamente por las CPU desde Pentium Pro en 1995.
Una cita del Manual de referencia de optimización de arquitecturas Intel® 64 e IA-32 , Sección 3.5.1.8:
El MOVZX y el MOV con operandos de 32 bits para x64 son equivalentes: todos rompen las cadenas de dependencia.
Es por eso que su código se ejecuta más rápido. Si no hay dependencias, la CPU puede renombrar internamente los registros, aunque a primera vista parezca que la segunda instrucción modifica un registro utilizado por la primera instrucción, y las dos no pueden ejecutarse en paralelo. Pero debido al cambio de nombre de registro pueden.
El cambio de nombre de registro es una técnica utilizada internamente por una CPU que elimina las dependencias de datos falsos que surgen de la reutilización de registros mediante instrucciones sucesivas que no tienen ninguna dependencia de datos real entre ellos.
Creo que ahora ves que es demasiado obvio.
fuente