При рассмотрении вызова условной функции в критической части кода я обнаружил, что и gcc, и clang будут разветвляться вокруг вызова.Например, для следующего (по общему признанию тривиального) кода:
int32_t __attribute__((noinline)) negate(int32_t num) {
return -num;
}
int32_t f(int32_t num) {
int32_t x = num < 0 ? negate(num) : num;
return 2*x + 1;
}
И GCC, и Clang компилируются по существу в следующее:
.global _f
_f:
cmp edi, 0
jg after_call
call _negate
after_call:
lea rax, [rax*2+1]
ret
Это заставило меня задуматься: что, если x86 имелинструкция условного вызова типа ARM?Представьте себе, была ли такая инструкция "ccall cc " с семантикой вроде cmov cc .Тогда вы можете сделать что-то вроде:
.global _f
_f:
cmp edi, 0
ccalll _negate
lea rax, [rax*2+1]
ret
Хотя мы не можем избежать предсказания ветвления, мы исключаем ветвление.А именно, в фактическом выводе GCC / clang мы вынуждены переходить независимо от того, num < 0 или нет.И если num < 0, мы должны разветвляться дважды.Это кажется расточительным.
Сейчас такой инструкции в amd64 не существует, но я разработал способ имитации такой инструкции.Я сделал это, разбив call func на составные части: push rip (ну технически [rip+label_after_call_instruction]) и затем jmp func.Мы можем сделать jmp условным, но нет условного push.Мы можем смоделировать это, вычислив [rip+label_after_call_instruction] и записав его в соответствующее место в стеке, а затем условно обновив rsp, если мы планируем вызвать функцию (которая фактически "выталкивает" [rip+label_after_call_instruction]).Это выглядит примерно так:
.global _f
_f:
cmp edi, 0
# ccalll _negate
lea rax, [rip+after_ccall] # Compute return address
mov [rsp-8], rax # Prepare to "push" return address
lea rax, [rsp-8] # Compute rsp (after push)
cmovl rsp, rax # Conditionally push (by actually changing rsp)
jl _negate # "Conditional call"
after_ccall:
lea rax, [rax*2+1]
ret
У этого подхода есть несколько потенциальных недостатков:
- Он вводит несколько инструкций (но их общее количество циклов меньше).чем штраф за неправильное предсказание ветви)
- Требуется запись в память (но стек, вероятно, кешируется?)
- Он всегда выполняет 2
lea s и mov, даже если вызовне сделано (но я понимаю, что это не имеет значения, так как cmov cc занимает столько же циклов, что и, например, mov)
Для проверки свойств каждогоиз этих подходов я провел критические разделы через iaca.Если он установлен (и вы клонируете мой список тестов ниже), вы можете запустить make iaca, чтобы убедиться в этом.Передайте IACAFLAGS='-arch=...', чтобы указать другую арку.
Выход для подхода с переходом через ветвь:
Intel(R) Architecture Code Analyzer Version - v3.0-28-g1ba2cbb build date: 2017-10-30;16:57:45
Analyzed File - ./branch_over_call_iaca.o
Binary Format - 64Bit
Architecture - SKL
Analysis Type - Throughput
Throughput Analysis Report
--------------------------
Block Throughput: 0.82 Cycles Throughput Bottleneck: Dependency chains
Loop Count: 36
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
--------------------------------------------------------------------------------------------------
| Cycles | 0.5 0.0 | 0.0 | 0.3 0.0 | 0.3 0.0 | 1.0 | 0.0 | 0.5 | 0.3 |
--------------------------------------------------------------------------------------------------
DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3)
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion occurred
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256/AVX512 instruction, dozens of cycles penalty is expected
X - instruction not supported, was not accounted in Analysis
| Num Of | Ports pressure in cycles | |
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
-----------------------------------------------------------------------------------------
| 1 | 0.5 | | | | | | 0.5 | | jnle 0x6
| 4^# | | | 0.3 | 0.3 | 1.0 | | | 0.3 | call 0x5
Total Num Of Uops: 5
И выход для подхода условного вызова:
Intel(R) Architecture Code Analyzer Version - v3.0-28-g1ba2cbb build date: 2017-10-30;16:57:45
Analyzed File - ./conditional_call_iaca.o
Binary Format - 64Bit
Architecture - SKL
Analysis Type - Throughput
Throughput Analysis Report
--------------------------
Block Throughput: 1.94 Cycles Throughput Bottleneck: Dependency chains
Loop Count: 35
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
--------------------------------------------------------------------------------------------------
| Cycles | 1.0 0.0 | 1.0 | 0.5 0.0 | 0.5 0.0 | 1.0 | 1.0 | 1.0 | 0.0 |
--------------------------------------------------------------------------------------------------
DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3)
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion occurred
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256/AVX512 instruction, dozens of cycles penalty is expected
X - instruction not supported, was not accounted in Analysis
| Num Of | Ports pressure in cycles | |
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 |
-----------------------------------------------------------------------------------------
| 1 | | 1.0 | | | | | | | lea rax, ptr [rip]
| 2^ | | | 0.5 | 0.5 | 1.0 | | | | mov qword ptr [rsp-0x8], rax
| 1 | | | | | | 1.0 | | | lea rax, ptr [rsp-0x8]
| 1 | 1.0 | | | | | | | | cmovl rsp, rax
| 1 | | | | | | | 1.0 | | jl 0x6
Total Num Of Uops: 6
Похоже, что условный подход к вызову использует больше оборудования.Но мне показалось интересным, что условный подход имеет только 1 моп (в подходе ветвления было 5 моп).Я думаю, это имеет смысл, учитывая, что под капотом вызов превращается в push и jmp (а push превращается в rsp math и память mov).Это наводит меня на мысль, что подход условного вызова приблизительно эквивалентен (хотя, может быть, мой упрощенный анализ здесь ошибочен?).
По крайней мере, мое всеобъемлющее подозрение заключалось в введении нескольких инструкций между cmp иjl, я бы сделал возможным, чтобы результат cmp был доступен до того, как jl может быть спекулятивно выполнен (таким образом, предотвращая прогноз ветвления вообще).Хотя, возможно, трубопровод длиннее этого?Это затрагивает области, с которыми (несмотря на то, что я прочитал и сохранил понимание глубины Руководства по оптимизации Агнера Фога ), я не очень знаком.
Моя гипотеза состоит в том, что для равномерного распределения(отрицательный и положительный) num с (где предсказание ветвления не сможет предсказать ветвление вокруг call), что мой подход «условного вызова» превзойдет ветвление вокруг вызова.
Я написал жгут для оценки производительности этих двух подходов .Вы можете git clone https://gist.github.com/baileyparker/8a13c22d0e26396921f501fe87f166a9 и make запустить тесты на вашем компьютере.
Вот время выполнения 100 итераций каждого подхода на массиве из 1 048 576 чисел (равномерно распределенных между int32_t мин. И макс.).
| CPU | Conditional Call | Branch Over |
|-------------------------------------------|-----------------:|------------:|
| Intel(R) Core(TM) i7-7920HQ CPU @ 3.10GHz | 10.9872 ms | 8.4602 ms |
| Intel(R) Xeon(R) CPU E3-1240 v6 @ 3.70GHz | 8.8132 ms | 7.0704 ms |
Эти результаты согласуются между прогонами и хотяувеличивается при увеличении размера массива (или количества итераций), ветвление всегда побеждает.
Я также попытался изменить порядок шагов условного вызова (сначала вычисление и условное обновление rsp, затем запись в стек), но это выполнялось аналогичным образом.
Какие детали аппаратного обеспечения, которые я пропускаю (или неправильно), объясняютэтот?Из моих вычислений дополнительные инструкции добавляют где-то около 6-7 циклов, но ошибочное прогнозирование ветвлений стоит 15. Таким образом, в среднем половина чисел прогнозируется неверно, поэтому каждая итерация стоит 15/2 циклов (для подхода с переходом по ветвлению) и всегда 6-7 циклов для условного вызова.Упс из iaca предполагают, что подходы в этом отношении еще ближе.Так что, не должно ли выступление быть ближе?Является ли мой пример кода слишком надуманным / коротким?Разве моя методика бенчмаркинга не подходит для такого рода тестирования критических секций низкого уровня?Есть ли способ переупорядочить / изменить условный вызов, чтобы сделать его более производительным (лучше или сравнимым с подходом ветвления, может быть)?
tl; dr Почему мой код условного вызова(4-й фрагмент кода) работает хуже, чем производит gcc / clang (условный переход через call) (2-й фрагмент кода) (для кода в 1-м фрагменте) на моем тесте ?