Sobrecarga de ramificação indexada no modo X86 de 64 bits
Este é um acompanhamento de alguns comentários feitos neste tópico anterior:
Montagem de fibonacci recursiva
Os seguintes trechos de código calculam Fibonacci, o primeiro exemplo com um loop, o segundo exemplo com um salto computado (ramificação indexada) em um loop desdobrado. Isso foi testado usando o Visual Studio 2015 Desktop Express no modo Windows 7 Pro de 64 bits com um processador Intel 3770K 3.5ghz. Com um único loop testando fib (0) a fib (93), o melhor momento para a versão de loop é ~ 1,901 microssegundos e, para salto computado, é ~ 1,324 microssegundos. Usando um loop externo para repetir esse processo 1.048.576 vezes, a versão do loop leva cerca de 1,44 segundos, o salto computado leva cerca de 1,04 segundos. Nos dois conjuntos de testes, a versão do loop é cerca de 40% mais lenta que a versão do salto computado.
Pergunta: Por que a versão do loop é muito mais sensível ao local do código do que a versão do salto computado? Em testes anteriores, algumas combinações de localização de código fizeram com que o tempo da versão do loop aumentasse de 1,44 segundos para 1,93 segundos, mas nunca encontrei uma combinação que afetasse significativamente o tempo da versão do salto computado.
Resposta parcial: A versão de salto computado ramifica em 94 locais de destino possíveis dentro de um intervalo de 280 bytes e, aparentemente, um buffer de destino de ramificação (cache) faz um bom trabalho de otimização disso. Para a versão do loop, o uso do align 16 para colocar a função fib () baseada em assembly em um limite de 16 bytes resolveu o problema de tempo da versão do loop na maioria dos casos, mas algumas alterações no main () ainda estavam afetando o tempo. Preciso encontrar um caso de teste razoavelmente pequeno e repetível.
versão loop (note que eu li isso |dec | jnz | é mais 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 computado (ramificação indexada) na versão de loop desdobrado:
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 teste que executa 1 milhão (1048576) de loops para calcularfib(0) parafib(93) usando múltiplos de 37% 93 para que o pedido não seja seqüencial. No meu sistema, a versão em loop demorou cerca de 1,44 segundos e a versão ramificada indexada em 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;
}
A saída para x é 0x812a62b1dc000000. A soma de fib (0) a fib (93) em hexadecimal é 0x1bb433812a62b1dc0 e adicione mais 5 zeros para repetir 0x100000 vezes: 0x1bb433812a62b1dc000000. Os 6 petiscos superiores são truncados devido à matemática de 64 bits.
Eu fiz uma versão de montagem para controlar melhor a localização do código. O "se 1" é alterado para "se 0" para a versão do loop. A versão em loop leva de 1,465 a 2.000 segundos, dependendo do preenchimento de nop usado para colocar os locais principais nos limites pares ou ímpares de 16 bytes (veja os comentários abaixo). A versão do salto computado leva cerca de 1,04 segundos e os limites fazem menos de 1% de diferença no tempo.
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