Выполнение "условного звонка" на amd64

Question

Рассматривая вызов условной функции в критической части кода, я обнаружил, что и 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? Представьте, если бы была такая инструкция "ccallcc" с семантикой вроде cmovcc. Тогда вы можете сделать что-то вроде:

.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с и mov даже если вызов не сделан (но, насколько я понимаю, это не имеет значения, поскольку cmovcc занимает столько же циклов, что и, например, 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 может быть спекулятивно выполнен (таким образом, предотвращая предсказание ветвления вообще). Хотя, возможно, трубопровод длиннее этого? Это затрагивает области, с которыми (несмотря на то, что я прочитал и сохранил глубокое понимание руководств по оптимизации Agner Fog), я не очень знаком.

Моя гипотеза заключается в том, что для равномерного распределения (отрицательное и положительное) nums (где предсказание ветвления не сможет предсказать ветвление вокруг 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-м фрагменте) в моем тесте?

Answer 1

Как отметил @fuz в комментариях, проблема производительности почти наверняка связана со стеком обратных адресов (RAS), который является специализированным предсказателем ветвления для возвратов функций.

Как преимущество наличия отдельного call а также ret инструкции от jmp и ручная модификация стека, процессоры подключаются к цели выполняемого кода. В частности, когда мы call функция это, вероятно, будет ret и когда это произойдет, мы собираемся вернуться к rip толкнул перед call, Другими словами, callS обычно в паре с ret, Процессор использует это, сохраняя стек фиксированной длины просто адресами возврата, называемыми стеком адресов возврата (RAS). call инструкции в дополнение к отправке адреса возврата в реальный стек в памяти дополнительно отправят его в RAS. Таким образом, когда ret Встречается, что процессор может выскочить из RAS (что намного быстрее, чем доступ к памяти для фактического стека) и спекулятивно выполнить возврат. Если окажется, что адрес, извлеченный из RAS, был адресом, извлеченным из стека, ЦП продолжает работу без штрафа. Однако, если RAS предсказал неправильный адрес возврата, происходит очистка конвейера, что является дорогостоящим.

Моя первоначальная интуиция заключалась в том, что условные инструкции будут лучше, потому что они дадут время для результата сравнения до перехода. Тем не менее, какую бы пользу это ни принесло, имея несбалансированный jmp/ret (мой условный звонок заменен call с jmp, но вызываемая функция все еще использовала ret) привел к тому, что RAS, скорее всего, всегда предсказывал неправильный адрес возврата (и, таким образом, мой подход, несмотря на то, что изначально пытался избежать этого, вызывает больше остановок конвейера). Ускорение от RAS более значимо, чем моя "оптимизация", поэтому подход с ветвлением превзошел подход с условными вызовами.

По некоторым эмпирическим результатам несоответствие call а также ret (в частности, используя jmp + ret) в 5-6 раз больше циклов, чем при правильном сопряжении call а также ret, Некоторая математика для салфеток предполагает, что штраф в +21 такт при 3,1 ГГц для 1048 576 вызовов добавляет около 7,1 мс к общему времени выполнения. Наблюдаемое замедление было меньше чем это. Вероятно, это комбинация условных инструкций, задерживающих скачок до тех пор, пока условие не будет готово, и тот факт, что скачки колеблются между фиксированными точками в памяти (что другие предсказатели ветвей, вероятно, стали хорошими в предсказании).

Answer 2

Вы можете точно определить, почему conditional_call подход медленнее, чем branch_over_call, Вы провели эксперименты на двух процессорах KBL, но в сообщении блога, на которое вы ссылались, не обсуждается, как работает RAS на KBL. Таким образом, первый шаг анализа состоит в том, чтобы определить, является ли ret в negate функция неправильно прогнозируется или нет (как это было бы в более ранних микроархитектурах). Вторым шагом является определение стоимости неправильного прогнозирования ret инструкция по общему времени исполнения. Самое близкое, что я имею к KBL, это CFL, и мои номера оказались близки к вашим. Единственное существенное различие между ними заключается в том, что LSD включен в CFL, но отключен в KBL. Тем не менее, ЛСД не имеет значения в этом случае из-за call инструкция в цикле, которая не позволяет ЛСД обнаружить любой цикл. Вы также можете легко повторить тот же анализ на KBL.

Есть несколько способов проанализировать поведение инструкций ветвления. Но в этом конкретном случае код достаточно прост для того, чтобы метод подсчета событий раскрыл всю необходимую нам информацию о каждой статической инструкции ветвления.

BR_INST_RETIRED_* События производительности могут использоваться для подсчета общего количества удаленных инструкций динамического ветвления и общего количества конкретных типов инструкций удаленного ветвления, включая условные, вызовы и возвраты. BR_MISP_RETIRED_* события могут использоваться для подсчета общего количества неверных прогнозов, общих условных ошибок и общих неправильных прогнозов вызовов.

Полный контрольный график свечения conditional_call выглядит так:

           total   misp
call         1      0
    jl       1     0.5
       ret  0.5     1
    ret      1      0
jne          1      0

Первый call инструкция вызывает conditional_call функция, которая содержит jl а также ret, jl инструкция условно переходит на negate функция, которая содержит ret, jne Инструкция используется для цикла. Числа, показанные в первом и втором столбцах, нормализуются по общему количеству итераций и общему количеству динамических инструкций соответственно. Из статической структуры программы мы знаем, что call, jl, conditional_call"s ret, а также jne каждый выполняется один раз в каждой итерации. Самое внутреннее ret выполняется только тогда, когда jl ветка взята. Используя события производительности, мы можем подсчитать общее количество выполненных инструкций возврата и вычесть из него общее количество итераций, чтобы получить количество раз, которое является внутренним наиболее ret выполнен. Поскольку входные данные рандомизированы в соответствии с равномерным распределением, неудивительно, что внутренний ret выполняется в половине случаев.

call инструкция никогда не прогнозируется. jne Инструкция также никогда не прогнозируется неправильно, за исключением последнего выполнения инструкций (где оно выходит из цикла). Следовательно, мы можем приписать общее количество условных неправильных прогнозов jl инструкция. Это может быть вычтено из общего количества неправильных прогнозов, чтобы получить количество неправильных прогнозов возврата, которые могут быть отнесены к одной или обеим инструкциям возврата. Второй ret может неправильно предсказать, когда неверный прогноз первого ret забивает или смещает РАН. Один из способов определить, является ли второй ret когда-либо неправильно прогнозируется с помощью точной выборки BR_MISP_RETIRED.ALL_BRANCHES, Другой способ - использовать метод, описанный в сообщении в блоге, которое вы цитировали. Действительно, только внутренняя ret неправильно прогнозируется. Дело в том, что jl неправильно предсказано, что половина времени предполагает, что инструкция либо предсказывается, либо всегда выполняется, либо всегда не выполняется.

Полный контрольный график свечения branch_over_call выглядит так:

           total   misp
call         1      0
    jg       1     0.5
    call    0.5     0
        ret 0.5     0
    ret      1      0
jne          1      0

Единственная неверно предсказанная инструкция jg, который неверно предсказан в половине случаев.

Чтобы измерить среднюю стоимость одного ret неправильное прогнозирование в conditional_call подход, ret Инструкция может быть заменена на lea/jmp последовательность, так что BTB, а не RAS используется для прогнозирования. С этим изменением единственная неверно предсказанная инструкция jl, Разницу во времени выполнения можно рассматривать как оценку общей стоимости ret mispredictions. На моем процессоре CFL это около 11,3 циклов в ret misprediction. К тому же, conditional_call стал примерно на 3% быстрее, чем branch_over_call, Ваши цифры в KBL показывают, что средняя стоимость ret неправильное прогнозирование составляет около 13 циклов. Я не уверен, в чем причина этой разницы. Это не может быть микроархитектура. Я использовал gcc 7.3, но вы использовали gcc 8, так что, возможно, есть некоторые различия в коде или выравнивании различных частей кода, которые вызывают расхождения между нашими результатами.