В этом ответе рассматривается только часть вопроса «быстро».
Предсказание обратного адреса
Сначала краткое описание поведения типичного предиктор обратного адреса.
- Каждый раз, когда создается
call
, адрес возврата, который помещается в реальный стек, также сохраняется в структуре ЦП, называемой буфером адреса возврата или чем-то в этом роде. - Когда выполняется
ret
(возврат), ЦПУ предполагает, что адресатом будет текущий адрес в верхней части буфера адреса возврата, и эта запись из буфера адреса возврата "вытолкнута".
Эффект заключается в идеальном 1 прогнозировании call
/ ret
пар, при условии, что они встречаются в своем обычном правильно вложенном шаблоне и что ret
фактически удаляет неизмененныйадрес возврата нажимается call
в каждом случае.Для получения более подробной информации вы можете начать здесь .
Обычные вызовы функций в C или C ++ (или почти любом другом языке) обычно всегда следуют этому правильно вложенному шаблону 2 ,Поэтому вам не нужно делать ничего особенного, чтобы воспользоваться преимуществом предсказания возврата.
Режимы сбоя
В случаях, когда call
/ ret
не спарены нормально,предсказания могут потерпеть неудачу (по крайней мере) несколькими различными способами:
- Если указателем стека или возвращаемым значением в стеке манипулируют так, что
ret
не возвращает место, гдесоответствующее нажатие call
приведет к ошибке прогнозирования цели ветвления для этого ret
, но последующие обычно вложенные ret
инструкции будут продолжать предсказывать правильно, пока они правильно вложены.Например, если в функции вы добавляете несколько байтов к значению [rsp]
, чтобы пропустить инструкцию, следующую за call
в вызывающей функции, следующий ret
будет неверно предсказан, а ret
, который следуетвнутри вызывающей функции должно быть все в порядке. - С другой стороны, функции
call
и ret
неправильно вложены, весь буфер предсказания возврата может стать не выровненным, что приведет к будущим инструкциям ret
,если таковые имеются, которые используют существующие значения для неверного прогнозирования 2.5 .Например, если вы call
входите в функцию, но затем используете jmp
для возврата к вызывающей стороне, существует несоответствие call
без ret
.ret
внутри вызывающего абонента будет неверно предсказываться, как и ret
внутри вызывающего абонента и т. Д., Пока все не выровненные значения не будут использованы или перезаписаны 3 .Подобный случай произошел бы, если бы у вас ret
не было сопоставления с соответствующим вызовом (и этот случай важен для последующего анализа).
Вместо двух приведенных выше правил вы также можете простоопределить поведение предиктора возврата, проследив код и отслеживая, как выглядит стек возврата в каждой точке.Каждый раз, когда у вас есть инструкция ret
, посмотрите, вернется ли она к текущей вершине стека возврата - если нет, вы получите неверное предсказание.
Стоимость неверного предсказания
Фактическая стоимостьот неправильного прогноза зависит окружающий код.Обычно дается ~ 20 циклов, и это часто можно увидеть на практике, но фактическая стоимость может быть ниже: например, до нуля, если процессор способен разрешить ошибочное прогнозирование рано и и начать выборкупо новому пути без прерывания критического пути или выше: например, если ошибки прогнозирования ветвления требуют много времени для устранения и уменьшения эффективного параллелизма операций с большой задержкой.Независимо от того, мы можем сказать, что штраф обычно значительный , когда это происходит в операции, когда другие требуют только несколько инструкций.
Быстрые сопрограммы
Существующее поведение для Coresume и Coyield
Существующая функция _yield
(переключение контекста) меняет указатель стека rsp
, а затем использует ret
для возврата в другое местоположение, чем то, что было фактически нажано вызывающим абонентом (в частности, оно возвращается в местоположение, которое было помещено встек caller
, когда вызывающая сторона ранее вызывала yield
).Как правило, это приведет к неправильному прогнозу в ret
внутри _yield
.
Например, рассмотрим случай, когда какая-то функция A0
делает обычный вызов функции для A1
, который она вызывает coresume
4 для возобновления сопрограммы B1
, которая позже вызывает coyield
для возврата к A1
.Внутри вызова к coresume
стек возврата выглядит как A0, A1
, но затем coresume
меняет rsp
, указывая на стек для B1
, а верхнее значение этого стека - это адрес внутри B1
сразуследующий coyield
в коде для B1
.Следовательно, ret
внутри coresume
переходит к точке в B1
, а не к точке в A1
, как ожидает стек возвратов.Следовательно, вы получаете неправильное предсказание для этого ret
, и стек возврата выглядит как A0
.
Теперь рассмотрим, что происходит, когда B1
вызывает coyield
, что реализуется в основном таким же образом coresume
: вызов coyield
толкает B1
в стек возвратов, который теперь выглядит как A0, B1
, а затем меняет местами стек, указывая на A1
стек, а затем выполняет ret
, который вернется к A1
,Таким образом, неправильное предсказание ret
произойдет таким же образом, и стек останется как A0
.
Таким образом, плохая новость заключается в том, что жесткая серия вызовов coresume
и coyield
(как, например, типично для итератора, основанного на доходности), будет неверно предсказывать каждый раз.Хорошей новостью является то, что теперь внутри A1
, по крайней мере, стек возвратов верен (не выровнен) - если A1
возвращается к своему вызывающему A0
, возвращение правильно прогнозируется (и так далее, когда A0
возвращается к его абонент и т. Д.).Таким образом, вы каждый раз получаете ошибочный прогноз, но, по крайней мере, в этом сценарии вы не смещаете стек возвратов.Относительная важность этого зависит от того, как часто вы вызываете coresume
/ coyield
по сравнению с вызывающими функциями, как правило, в приведенной ниже функции, которая вызывает coresume
.
Как сделать это быстрым
Так можем ли мы исправить неверное предсказание?К сожалению, это сложно в комбинации вызовов C и внешних ASM, потому что выполнение вызова coresume
или coyield
подразумевает вызов, вставленный компилятором, и это трудно размотать в ассемблере.
Тем не менее, давайте попробуем.
Использовать косвенные вызовы
Один из подходов - использовать вообще ret
и просто использовать косвенные переходы.
Этопросто замените ret
в конце ваших вызовов coresume
и coyield
на:
pop r11
jmp r11
Это функционально эквивалентно ret
, но влияет на буфер возвращаемого стека по-разному (вв частности, это не влияет на это).
Если проанализировать повторную последовательность вызовов coresume
и coyield
, как указано выше, мы получим результат, что буфер стека возврата просто начинает расти бесконечно, как A0, A1, B1, A1, B1, ...
,Это происходит потому, что на самом деле мы не используем ret
вообще в этой реализации.Таким образом, мы не терпим ошибочных предсказаний возврата, потому что мы не используем ret
!Вместо этого мы полагаемся на точность косвенного предиктора ветвления для прогнозирования jmp11
.
Принцип работы этого предиктора зависит от того, как реализованы coresume
и coyeild
.Если они оба вызывают общую функцию _yield
, которая не встроена, существует только одно местоположение jmp r11
, и этот jmp
поочередно перейдет в местоположение в A1
и B1
.Большинство современных косвенных предикторов будут предсказывать этот простой повторяющийся паттерн в порядке, хотя более старые, которые отслеживали только одно местоположение, не будут.Если _yield
вставлено в coresume
и coyield
или вы просто скопировали код в каждую функцию, есть два отдельных jmp r11
сайта вызова, каждый из которых видит только одно местоположение, и должен быть хорошопредсказывается любым процессором с косвенным предсказателем ветвления 6 .
Так что это, как правило, должно предсказывать серию жестких coyield
и coresume
вызовов 7 , но за счет уничтожения буфера возврата, поэтому, когда A1
решает вернуться к A0
это будет неверно предсказано, а также последующие возвраты A0
и так далее.Размер этого штрафа ограничен выше размером буфера возврата стека, поэтому, если вы делаете много жестких coresume/yield
вызовов, это может быть хорошим компромиссом.
Это лучшее, что я могу придумать в рамкахограничение внешних вызовов функций, написанных на ASM, потому что у вас уже есть подразумеваемое значение call
для ваших подпрограмм co
, и вам нужно перейти к другой процедуре изнутри, и я не вижу, как сохранитьстеки уравновешены и возвращаются в правильное местоположение с этими ограничениями.
Встроенный код на сайте вызова
Если вы можете встроить код на сайте вызова ваших методов процедуры (например, с поддержкой компилятора)или встроенный asm), тогда вы, возможно, сможете добиться большего успеха.
Вызов coresume
может быть встроен примерно так (я пропустил код сохранения и восстановления регистра, потому что это просто):
; rcx - current context
; rdc - context for coroutine we are about to resume
; save current non-volatile regs (not shown)
; load non-volatile regs for dest (not shown)
lea r11, [rsp - 8]
mov [rcx + 64], r11 ; save current stack pointer
mov r11, [rdx + 64] ; load dest stack pointer
call [r11]
Обратите внимание, что coresume
на самом деле не выполняет обмен стека - он просто загружает целевой стек в r11
и затем does call
против [r11]
, чтобы прыгнуть к сопрограмме.Это необходимо для того, чтобы call
правильно выдвигал местоположение, к которому мы должны вернуться в стеке вызывающей стороны.
Тогда coyield
будет выглядеть примерно так (встроено в вызывающую функцию):
; save current non-volatile regs (not shown)
; load non-volatile regs for dest (not shown)
lea r11, [after_ret]
push r11 ; save the return point on the stack
mov rsp, [rdx + 64] ; load the destination stack
ret
after_ret:
mov rsp, r11
Когда вызов coresume
переходит на сопрограмму, он заканчивается на after_ret
, и перед выполнением кода пользователя инструкция mov rsp, r11
переходит в соответствующий стек для сопрограммы, которая была сохранена в r11
на coresume
.
Таким образом, по существу, coyield
состоит из двух частей: верхняя половина выполняется перед выходом (что происходит при вызове ret
) и нижняя половина, которая завершает работу, начатую coresume
,Это позволяет использовать call
в качестве механизма для выполнения прыжка coresume
и ret
для выполнения прыжка coyield
.call
/ ret
в этом случае сбалансированы.
Я замалчиваю некоторые детали этого подхода: например, поскольку не задействован вызов функции, энергонезависимые регистры, заданные ABIна самом деле не особенные: в случае встроенной сборки вам нужно будет указать компилятору, какие переменные вы закроете и сохраните остальные, но вы можете выбрать любой набор, который вам удобен.Выбор большего набора закрытых переменных делает кодовые последовательности coresume
/ coyield
самими короче, но потенциально создает большее регистровое давление на окружающий код и может заставить компилятор пролить больше окружающего вас кода.Возможно, в идеале нужно просто объявить все засоренным, и тогда компилятор просто выдаст то, что ему нужно.
1 Конечно, на практике существуют ограничения: размер возвратаБуфер стека, вероятно, ограничен некоторым небольшим числом (например, 16 или 24), поэтому, как только глубина стека вызовов превысит это, некоторые обратные адреса будут потеряны и не будут правильно предсказаны.Кроме того, различные события, такие как переключение контекста или прерывание, могут испортить предиктор стека возврата.
2 Интересным исключением был общий шаблон для чтения текущего указателя инструкции в x86 (32-битный) код: нет инструкции, чтобы сделать это напрямую, поэтому вместо этого можно использовать последовательность call next; next: pop rax
: call
для следующей инструкции, которая обслуживает только push адрес в стеке, который удален.Нет соответствующего ret
.Однако современные процессоры фактически распознают этот шаблон и не разбалансируют предиктор обратного адреса в этом особом случае.
2.5 Сколько неверных прогнозов это предполагает, зависит от того, как net возвращает вызывающую функцию: если она немедленно начинает вызывать еще одну глубокую цепочку вызовов, неправильно выровненные записи стека возврата могут вообще никогда не использоваться, например.
3 Или, возможно, до тех пор, пока стек обратного адреса не будет выровнен с помощью ret
без соответствующего вызова, в случае "два неправильных действия делают право".
4 Вы на самом деле не показали, как coyield
и coresume
на самом деле вызывают _yield
, поэтому в остальной части вопроса я буду предполагать, что они реализованы по существу так же, как _yield
, напрямуюв пределах coyield
или coresume
без вызова _yield
: т.е. скопируйте и вставьте код _yield
в каждую функцию, возможно, с небольшими изменениями, чтобы учесть разницу.Вы также можете выполнить эту работу, позвонив по номеру _yield
, но у вас будет дополнительный уровень вызовов и повторов, который усложнит анализ.
5 В той степени, в которой эти термины даже имеют смысл всимметричная реализация процедуры, поскольку в этом случае нет абсолютного понятия вызывающего и вызываемого абонентов.
6 Конечно, этот анализ применим только к простому случаю, когда у вас есть одинcoresume
вызов, вызываемый в сопрограмму с одним coyield
вызовом.Возможны более сложные сценарии, например, несколько вызовов coyield
внутри вызываемого абонента или несколько вызовов coresume
внутри вызывающего абонента (возможно, для различных процедур).Однако применяется та же схема: случай с разделенными jmp r11
сайтами будет представлять собой более простую партию, чем объединенный случай (возможно, за счет увеличения ресурсов iBTB).
7 Одно исключениебудет первым или двумя вызовами: предиктору ret
не требуется «разминка», но может сделать предиктор непрямой ветвления, особенно когда в промежутке вызывается другая сопрограмма.