Индексированные накладные расходы ветки в 64-битном режиме X86
Это продолжение некоторых комментариев, сделанных в этой предыдущей теме:
Следующие фрагменты кода вычисляют Фибоначчи, первый пример с циклом, второй пример с вычисленным переходом (индексированная ветвь) в развернутый цикл. Это было протестировано с использованием 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 до 2.000 секунд, в зависимости от заполнения 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
1 ответ
Это был ответ на первоначальный вопрос о том, почему цикл занимает в 1,4 раза больше времени для версии с вычисленным переходом, когда результат полностью не используется. ИДК точно, зачем накапливать результат за 1 цикл add Цепочка зависимостей, переносимая циклами, имела бы такое большое значение. Интересные вещи, чтобы попробовать: сохранить его в памяти (например, назначить его volatile int discard) так что цепочка asm dep не просто заканчивается закрытым регистром. HW может оптимизировать это (например, отменить моп, как только он уверен, что результат мертв). Intel говорит, что семья Сэндибридж может сделать это для одного из флагов shl reg,cl,
Старый ответ: почему вычисленный скачок в 1,4 раза быстрее, чем цикл с неиспользованным результатом
Здесь вы тестируете пропускную способность, а не задержку. В нашей предыдущей дискуссии я в основном фокусировался на задержке. Это могло быть ошибкой; влияние пропускной способности на вызывающего может часто быть таким же значимым, как и задержка, в зависимости от того, сколько из того, что делает вызывающий, имеет зависимость данных от результата.
Внеочередное выполнение скрывает задержку, потому что результат одного вызова не является входной зависимостью для аргумента arg к следующему вызову. И окно вывода из строя IvyBridge достаточно велико, чтобы быть полезным здесь: ROB с 168 записями (от выпуска к выбытию), и планировщик с 54 записями (от выпуска к выполнению), и физический регистровый файл с 160 записями. См. Также ограничения PRF и ROB для размера окна ООО.
Исполнение ООО также скрывает стоимость ошибочного прогноза филиала до того, как любая работа Fib будет выполнена. Работа с последнего fib(n) dep chain все еще находится в полете и работает над этим ошибочным прогнозом. (Современные процессоры Intel откатываются только до ошибочно предсказанной ветви и могут продолжать выполнение мопов до ветви, пока разрешается ошибочный прогноз.)
Имеет смысл, что версия с вычисляемой ветвью здесь хороша, потому что вы в основном ограничены в пропускной способности uop, а неверный прогноз из ветви loop-exit стоит примерно так же, как и ошибочный прогноз косвенной ветви при входе в развернутую версию. IvB может слить макрос sub/jcc в один моп для порта 5, так что число 40% совпадает довольно хорошо. (3 исполнительных блока ALU, поэтому тратить 1/3 или вашу пропускную способность выполнения ALU на издержки цикла объясняет это. Различия между ошибками ветвления и ошибками и пределы выполнения OOO объясняют остальное)
Я думаю, что в большинстве реальных случаев латентность может иметь значение. Возможно, пропускная способность по-прежнему будет наиболее важной, но что-либо еще, кроме этого, сделает задержку более важной, потому что это вообще не использует результат. Конечно, это нормально, что в конвейере будет предыдущая работа, над которой можно будет работать, пока восстанавливается ошибочный прогноз непрямой ветви, но это задержит готовность результата, что может означать остановку позже, если большинство инструкций после fib() Возврат зависит от результата. Но если это не так (например, много перезагрузок и вычислений адресов для определения места результата), внешний интерфейс начнет выдавать мопы после fib() скорее хорошая вещь.
Я думаю, что хорошим промежуточным положением здесь было бы развертывание на 4 или 8, с проверкой перед развернутым циклом, чтобы убедиться, что он запустится один раз. (например sub rcx,8 / jb .cleanup).
Также обратите внимание, что ваша зацикленная версия имеет зависимость от данных n для начальных значений. В нашем предыдущем обсуждении я указывал, что избегать этого было бы лучше для выполнения не по порядку, потому что это позволяет add цепочка начала работать раньше n готов. Я не думаю, что это является важным фактором, потому что вызывающая сторона имеет низкую задержку для n, Но это делает ошибочный прогноз ветвления цикла при выходе из цикла в конце n -> fib(n) Деп цепочка вместо посередине. (Я представляю без ветки lea / cmov после цикла, чтобы сделать еще одну итерацию, если sub ecx, 2 опустился ниже нуля вместо нуля.)