опустился ниже нуля вместо нуля.)
родолжение некоторых комментариев, сделанных в этой предыдущей теме:
Следующие фрагменты кода вычисляют Фибоначчи, первый пример с циклом, второй пример с вычисленным переходом (индексированная ветвь) в развернутый цикл. Это было протестировано с использованием Visual Studio 2015 Desktop Express в 64-битном режиме Windows 7 Pro с процессором Intel 3770K 3,5 ГГц. С тестом с одной петлей от fib (0) до fib (93) наилучшее время, которое я получаю для версии цикла, составляет ~ 1,901 микросекунды, а для вычисленного скачка - ~ 1,324 микросекунды. Используя внешний цикл, чтобы повторить этот процесс 1 048 576 раз, версия цикла занимает около 1,44 секунды, вычисленный переход занимает около 1,04 секунды. В обоих наборах тестов версия цикла примерно на 40% медленнее, чем версия с вычисленным переходом.
Вопрос: Почему версия цикла гораздо более чувствительна к расположению кода, чем версия вычисленного перехода? В предыдущих тестах некоторые комбинации местоположений кода вызывали увеличение времени версии цикла с примерно 1,44 до 1,93 секунды, но я никогда не находил комбинацию, которая бы существенно повлияла на вычисленное время перехода.
Частичный ответ: вычисленная версия перехода переходит в 94 возможных целевых местоположения в пределах диапазона 280 байт, и, очевидно, целевой буфер ветвления (кэш) хорошо справляется с оптимизацией этого. Для версии цикла использование выравнивания 16 для размещения функции fib () на основе сборки на границе 16 байт решило проблему времени версии цикла в большинстве случаев, но некоторые изменения в main () по-прежнему влияли на время. Мне нужно найти достаточно маленький и повторяемый контрольный пример.
версия цикла (обратите внимание, я читал, что |dec
| jnz
| быстрее чем |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
вычисляемый переход (индексированная ветвь) в версию развернутого цикла:
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
Тестовый код, который выполняет 1 миллион (1048576) циклов для вычисленияfib(0)
вfib(93)
используя кратные 37% 93, поэтому порядок не является последовательным. В моей системе версия цикла заняла около 1,44 секунды, а индексированная версия ветви - около 1,04 секунды.
#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;
}
Выход для x равен 0x812a62b1dc000000. Сумма от fib (0) до fib (93) в hex равна 0x1bb433812a62b1dc0, и добавьте еще 5 нулей для цикла 0x100000 раз: 0x1bb433812a62b1dc000000. Верхние 6 полубайнов усечены из-за 64-битной математики.
Я сделал полностью сборочную версию, чтобы лучше контролировать местоположение кода. «If 1» изменяется на «if 0» для версии цикла. Версия цикла занимает от 1,465 до 2000 секунд в зависимости от заполнения nop, используемого для размещения ключевых позиций на четных или нечетных 16-байтовых границах (см. Комментарии ниже). Вычисленная версия скачка занимает около 1,04 секунды, а границы составляют менее 1% разницы во времени.
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