Sobrecarga de rama indexada en modo X86 de 64 bits
Este es un seguimiento de algunos comentarios hechos en este hilo anterior:
Asamblea recursiva de fibonacci
Los siguientes fragmentos de código calculan Fibonacci, el primer ejemplo con un bucle, el segundo ejemplo con un salto calculado (rama indexada) en un bucle desplegado. Esto se probó usando Visual Studio 2015 Desktop Express en modo Windows 7 Pro de 64 bits con un procesador Intel 3770K 3.5ghz. Con un solo bucle que prueba fib (0) a fib (93), el mejor tiempo que obtengo para la versión de bucle es ~ 1.901 microsegundos, y para el salto calculado es ~ 1.324 microsegundos. Usando un bucle externo para repetir este proceso 1.048.576 veces, la versión del bucle tarda aproximadamente 1,44 segundos, el salto calculado tarda aproximadamente 1,04 segundos. En ambos conjuntos de pruebas, la versión de bucle es aproximadamente un 40% más lenta que la versión de salto calculada.
Pregunta: ¿Por qué la versión de bucle es mucho más sensible a la ubicación del código que la versión de salto calculada? En pruebas anteriores, algunas combinaciones de ubicación de código hicieron que el tiempo de versión del bucle aumentara de aproximadamente 1.44 segundos a 1.93 segundos, pero nunca encontré una combinación que afectara significativamente el tiempo de la versión de salto calculada.
Respuesta parcial: la versión de salto calculada se ramifica en 94 posibles ubicaciones de destino dentro de un rango de 280 bytes, y aparentemente un búfer de destino de ramificación (caché) hace un buen trabajo al optimizar esto. Para la versión de bucle, el uso de alinear 16 para poner la función fib () basada en el ensamblaje en un límite de 16 bytes resolvió el problema de tiempo de la versión de bucle en la mayoría de los casos, pero algunos cambios en main () todavía estaban afectando el tiempo. Necesito encontrar un caso de prueba razonablemente pequeño y repetible.
versión de bucle (nota que he leído que |dec | jnz El | es más rápido que |loop |):
align 16
fib proc ;rcx == n
mov rax,rcx ;br if < 2
cmp rax,2
jb fib1
mov rdx,1 ;set rax, rdx
and rax,rdx
sub rdx,rax
shr rcx,1
fib0: add rdx,rax
add rax,rdx
dec rcx
jnz fib0
fib1: ret
fib endp
salto calculado (rama indexada) a la versión de bucle desplegado:
align 16
fib proc ;rcx == n
mov r8,rcx ;set jmp adr
mov r9,offset fib0+279
lea r8,[r8+r8*2]
neg r8
add r8,r9
mov rax,rcx ;set rax,rdx
mov rdx,1
and rax,rdx
sub rdx,rax
jmp r8
fib0: ; assumes add xxx,xxx takes 3 bytes
rept 46
add rax,rdx
add rdx,rax
endm
add rax,rdx
ret
fib endp
Código de prueba que ejecuta 1 millón (1048576) bucles para calcularfib(0) afib(93) usando múltiplos del 37% 93 por lo que el orden no es secuencial. En mi sistema, la versión de bucle tardó aproximadamente 1.44 segundos y la versión de rama indexada tardó aproximadamente 1.04 segundos.
#include <stdio.h>
#include <time.h>
typedef unsigned int uint32_t;
typedef unsigned long long uint64_t;
extern "C" uint64_t fib(uint64_t);
/* multiples of 37 mod 93 + 93 at end */
static uint64_t a[94] =
{0,37,74,18,55,92,36,73,17,54,
91,35,72,16,53,90,34,71,15,52,
89,33,70,14,51,88,32,69,13,50,
87,31,,68,12,49,86,30,67,11,48,
85,29,66,10,47,84,28,65, 9,46,
83,27,64, 8,45,82,26,63, 7,44,
81,25,62, 6,43,80,24,61, 5,42,
79,23,60, 4,41,78,22,59, 3,40,
77,21,58, 2,39,76,20,57, 1,38,
75,19,56,93};
/* x used to avoid compiler optimizing out result of fib() */
int main()
{
size_t i, j;
clock_t cbeg, cend;
uint64_t x = 0;
cbeg = clock();
for(j = 0; j < 0x100000; j++)
for(i = 0; i < 94; i++)
x += fib(a[i]);
cend = clock();
printf("%llx\n", x);
printf("# ticks = %u\n", (uint32_t)(cend-cbeg));
return 0;
}
La salida para x es 0x812a62b1dc000000. La suma de fib (0) a fib (93) en hexadecimal es 0x1bb433812a62b1dc0, y agrega 5 ceros más para recorrer 0x100000 veces: 0x1bb433812a62b1dc000000. Los 6 nibbles superiores se truncan debido a las matemáticas de 64 bits.
Hice una versión de todo el ensamblaje para controlar mejor la ubicación del código. "If 1" se cambia a "if 0" para la versión de bucle. La versión de bucle tarda aproximadamente 1.465 a 2.000 segundos dependiendo del relleno de nop utilizado para colocar ubicaciones clave en límites de 16 bytes pares o impares (ver comentarios a continuación). La versión de salto calculada tarda aproximadamente 1,04 segundos y los límites hacen menos del 1% de diferencia en el tiempo.
includelib msvcrtd
includelib oldnames
.data
; multiples of 37 mod 93 + 93 at the end
a dq 0,37,74,18,55,92,36,73,17,54
dq 91,35,72,16,53,90,34,71,15,52
dq 89,33,70,14,51,88,32,69,13,50
dq 87,31,68,12,49,86,30,67,11,48
dq 85,29,66,10,47,84,28,65, 9,46
dq 83,27,64, 8,45,82,26,63, 7,44
dq 81,25,62, 6,43,80,24,61, 5,42
dq 79,23,60, 4,41,78,22,59, 3,40
dq 77,21,58, 2,39,76,20,57, 1,38
dq 75,19,56,93
.data?
.code
; parameters rcx,rdx,r8,r9
; not saved rax,rcx,rdx,r8,r9,r10,r11
; code starts on 16 byte boundary
main proc
push r15
push r14
push r13
push r12
push rbp
mov rbp,rsp
and rsp,0fffffffffffffff0h
sub rsp,64
mov r15,offset a
xor r14,r14
mov r11,0100000h
; nop padding effect on loop version (with 0 padding in padx below)
; 0 puts main2 on odd 16 byte boundary clk = 0131876622h => 1.465 seconds
; 9 puts main1 on odd 16 byte boundary clk = 01573FE951h => 1.645 seconds
rept 0
nop
endm
rdtsc
mov r12,rdx
shl r12,32
or r12,rax
main0: xor r10,r10
main1: mov rcx,[r10+r15]
call fib
main2: add r14,rax
add r10,8
cmp r10,8*94
jne main1
dec r11
jnz main0
rdtsc
mov r13,rdx
shl r13,32
or r13,rax
sub r13,r12
mov rdx,r14
xor rax,rax
mov rsp,rbp
pop rbp
pop r12
pop r13
pop r14
pop r15
ret
main endp
align 16
padx proc
; nop padding effect on loop version with 0 padding above
; 0 puts fib on odd 16 byte boundary clk = 0131876622h => 1.465 seconds
; 16 puts fib on even 16 byte boundary clk = 01A13C8CB8h => 2.000 seconds
; nop padding effect on computed jump version with 9 padding above
; 0 puts fib on odd 16 byte boundary clk = 00D979792Dh => 1.042 seconds
; 16 puts fib on even 16 byte boundary clk = 00DA93E04Dh => 1.048 seconds
rept 0
nop
endm
padx endp
if 1 ;0 = loop version, 1 = computed jump version
fib proc ;rcx == n
mov r8,rcx ;set jmp adr
mov r9,offset fib0+279
lea r8,[r8+r8*2]
neg r8
add r8,r9
mov rax,rcx ;set rax,rdx
mov rdx,1
and rax,rdx
sub rdx,rax
jmp r8
fib0: ; assumes add xxx,xxx takes 3 bytes
rept 46
add rax,rdx
add rdx,rax
endm
add rax,rdx
ret
fib endp
else
fib proc ;rcx == n
mov rax,rcx ;br if < 2
cmp rax,2
jb fib1
mov rdx,1 ;set rax, rdx
and rax,rdx
sub rdx,rax
shr rcx,1
fib0: add rdx,rax
add rax,rdx
dec rcx
jnz fib0
fib1: ret
fib endp
endif
end