Вопрос по performance, x86, c – Вынуждают ли указатели функций очистить конвейер команд?

23

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

Иногда данные, загруженные в конвейер, становятся недействительными, и конвейер должен быть очищен и загружен новыми данными. Время, необходимое для повторного заполнения конвейера, может быть значительным и привести к снижению производительности.

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

Я работаю в C, но я полагаю, что это еще более важно в C ++, где многие вызовы функций осуществляются через v-таблицы.

edit

@JensGustedt пишет:

To be a real performance hit for function calls, the function that you call must be extremely brief. If you observe this by measuring your code, you definitively should revisit your design to allow that call to be inlined

К сожалению, это может быть ловушка, в которую я попал.

Я написал целевую функцию маленькой и быстрой по соображениям производительности.

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

Итак, у меня очень короткая, не встроенная функция.

Да, х86. (64-битный, Core2, если быть более точным) abelenky
@MartinBeckett: Ну, это предполагает дополнительный уровень косвенности ... Oliver Charlesworth
@OliCharlesworth - и это не может быть предсказано во время компиляции, я полагаю Martin Beckett
Указатель функции отличается от обычного вызова функции? Martin Beckett
Я думаю, это зависит от платформы в определенной степени; можем ли мы предположить, что вы говорите о x86? Oliver Charlesworth

Ваш Ответ

4   ответа
9

ального метода в C ++, и, в этом отношении, он принципиально не отличается от возврата. При взгляде в будущее процессор распознает, что происходит переход через указатель, и примет решение, сможет ли он в конвейере предварительной выборки безопасно и эффективно разрешить указатель и следовать по этому пути. Это, очевидно, сложнее и дороже, чем следование обычной относительной ветви, но, поскольку косвенные ветви так распространены в современных программах, это то, что большинство процессоров будет пытаться.

Как сказал Оли, «очистка» конвейер был бы необходим только в том случае, если в условном переходе было неверное предсказание, которое не имеет никакого отношения к тому, является ли ответвление смещением или переменным адресом. Тем не менее, процессоры могут иметь политики, которые предсказывают по-разному в зависимости от типа адреса ветвления - в общем случае процессор будет менее агрессивно следовать по косвенному пути из условной ветки из-за возможности неверного адреса.

Да, я забыл о буфере целевого ветвления (это было какое-то время с тех пор, как я испортил этот материал). Это своего рода кеш (точный характер, в который я никогда не копался), поэтому процессор может смотреть туда, а не смотреть на фактический адрес ветви (который может быть еще недоступен). Фактически это условное предсказание ветвления, похожее на волосок, в котором предположение о том, что та же цель будет использоваться снова, может быть неверным, и поэтому оно может действительно привести к необходимости «очистки». конвейер до такой степени, что код был предварительно выполнен по предсказанному пути.
Для уточнения, скажем, процессор пытается получить четыре или более инструкций в каждом цикле (что они и делают). Ветви создают проблему, поскольку указатель инструкции теперь странно перемещается, поэтому процессор должен предсказать, куда он пойдет. Он использует две структуры: предиктор ветвления и целевой буфер ветвления (BTB). Для косвенных филиалов реальная стоимость указана в BTB, так как она часто просто хранит последнюю цель для филиала. Поэтому в следующий раз, когда процессор встретит инструкцию перехода (в этом случае вызов указателя функции), процессор примет тот же вызов, что и в прошлый раз.
Процессоры всегда берут свой прогноз и следуют ему полностью агрессивно. AFAIK, никакие процессоры не делают «слабее» вещи, когда они не уверены в своих прогнозах. УвидетьWhy not just predict both branches?и обсуждение в комментариях (перенесено в чат) об использовании достоверности прогноза для управления предварительной выборкой (для процессоров, которые на самом деле не являютсяexecute умозрительно).
Предикторы ветвления имеют дело со статическими ветвями (смещение в потоке команд) очень по-разному от косвенных ветвей (цель находится в регистре). Если ветвь является статической - как обычный вызов функции или безусловный GOTO (они одинаковы в микрокоде), то предиктор ветвления может сделать это правильно 100% времени на этапе декодирования команд конвейера. Если адрес назначения указан в регистре, подразделение не может знать, куда будет переходить, пока не будет рассчитана цель. В лучшем случае предсказатель может догадаться, что он пойдет в том же месте, что и в прошлый раз.
@PeterCordes - я уверен, что немногие центральные процессоры общего назначения будут выполнять прогнозируемое хранение, если они не уверены в прогнозе.
1

necessarily вызвать конвейер ясно, но этоmayв зависимости от сценария. Ключ в том, сможет ли ЦП эффективно предсказать пункт назначения ветви заранее.

То, что современно "большой" неработающая ручка для сердечниковindirect calls1 примерно так:

Once you've executed the indirect branch a few times, the indirect branch predictor will try to predict the address to which the branch will occur in the future. The first indirect branch predictors were very simple, capable of "predicting" only a single, fixed location. Later predictors including those on most modern CPUs are much more complex, often capable of predicting well a repeated pattern of indirect jumps and also correlating the jump target with the direction of earlier conditional or indirect branches. If the prediction is successful, the indirect call has a cost similar to a normal direct call, and this cost is largely "out of line" with the rest of the code (i.e., doesn't participate in dependency chains) so the impact on final runtime of the code is likely to be small unless the calls are very dense. On the other hand, if the prediction is unsuccessful, you get a full misprediction, similar to a branch direction misprediction. You can't put a fixed number on the cost of this misprediction, since it depends on the surrounding code, but it usually causes a bubble of about 20 cycles in the front-end, and the overall cost in runtime often ends up similar.

Итак, учитывая эти основы, мы можем сделать некоторые обоснованные предположения о том, что происходит в некоторых конкретных сценариях:

A function pointer always points to the same function will almost always1 be well predicted and cost about the same as a regular function call. A function pointer that alternates randomly between several targets will almost always be mispredicted. At best, we can hope the predictor always predicts whatever target is most common, so in the worst-case that the targets are chosen uniformly at random between N targets the prediction success rate is bounded by 1 / N (i.e., goes to zero as N goes to infinity). In this respect, indirect branches have a worse worst-case behavior than conditional branches, which generally have a worst-case misprediction rate of 50%2. The prediction rate for a function pointer with behavior somewhere in the middle, e.g., somewhat predictable (e.g., following a repeating pattern), will depend heavily on the details of the hardware and the sophistication of the predictor. Modern Intel chips have quite good indirect predictors, but details haven't been publicly released. Conventional wisdom holds that they are using some indirect variant of an TAGE predictors used also for conditional branches.

1 Случай, который мог бы ошибочно предсказать даже для одной цели, включает в себя первое (или несколько раз) обнаружение функции, поскольку предиктор не может предсказать косвенные вызовы, которые он еще не видел! Кроме того, размер ресурсов прогнозирования в ЦП ограничен, поэтому, если указатель функции не использовался в течение некоторого времени, в конечном итоге ресурсы прогнозирования будут использоваться для других ветвей, и вы будете подвержены ошибочному прогнозированию при следующем вызове. ,

2 Действительно, очень простой условный предиктор, который просто предсказывает направление, наиболее часто встречающееся в последнее время, должен иметь 50% -ную степень предсказания в совершенно случайно выбранных направлениях. Чтобы получить значительно худший результат, чем 50%, вам необходимо разработать состязательный алгоритм, который по существу моделирует предиктор и всегда выбирает ветвление в направлении, противоположном модели.

2

вызов, кроме дополнительного уровня косвенности. Таким образом, потенциально существует большая задержка; если адрес назначения еще не находится в кэше или регистрах, то ЦП потенциально должен ждать, пока он не будет извлечен из основной памяти.

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

Конечно, я понимаю, что конвейер может зависнуть, если соответствующие инструкции недоступны (в кеше L1 или L2). Но стойло отличается от чистого. Ясно, что конвейер уже начал готовиться к выполнению одной инструкции, а затем внезапно осознает, что будет выполнять совершенно другую работу. Нужно выбросить уже выполненную часть работы и начать заново заполнять конвейер новым заданием. abelenky
@abelenky: AFAIK, конвейер нужно очищать только в ситуациях, таких как неправильное предсказание ветвления.
Нет, конвейер должен быть очищен от любого неверного прогноза, включая неправильное прогнозирование цели филиала. Если он ошибается с целью, он загрузится и, вероятно, начнет умозрительно выполнять инструкции из неправильного места, и они должны быть сброшены.
12

часть конвейера, потому что она всегда будет неверно предсказана. Особенно это касается процессоров на заказ.

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

Я написал крошечное тело функции и измерил его в узком цикле миллионов вызовов, чтобы определить стоимость только штрафа за вызовы. & Quot; встроенный & quot; Функция была контрольной группой, которая измеряла только стоимость тела функции (в основном, опциональная нагрузка). Прямая функция измеряет штраф за правильно предсказанную ветвь (потому что она является статической целью и предсказатель PPC всегда может получить это право) и пролог функции. Косвенная функция измеряет штрафbctrl косвенная ветвь.

614,400,000 function calls:

inline:   411.924 ms  (   2 cycles/call )
direct:  3406.297 ms  ( ~17 cycles/call )
virtual: 8080.708 ms  ( ~39 cycles/call )

Как видите, прямой вызов стоит на 15 циклов больше, чем тело функции, а виртуальный вызов (точно эквивалентно вызову указателя на функцию) стоит на 22 цикла больше, чем прямой звонок. Это примерно столько этапов конвейера между началом конвейера (выбор команды) и концом ALU ветвления. Поэтому в этой архитектуре косвенная ветвь (или виртуальный вызов) вызывает очистку 22 этапов конвейера.100% of the time.

Другие архитектуры могут отличаться. Вы должны делать эти определения из прямых эмпирических измерений или из спецификаций конвейера ЦП, а не из предположений о том, какие процессоры "должны" предсказать, потому что реализации настолько разные. В этом случае происходит очистка конвейера, потому что предсказатель ветвления не может знать, куда пойдет bctrl до тех пор, пока он не будет удален. В лучшем случае он может догадаться, что он имеет ту же цель, что и последний bctrl, и этот конкретный процессор даже не пытается сделать это предположение.

Это очень интересный пост, но следует подчеркнуть, что он зависит от архитектуры. Из вашего поста (ссылка устарела, кстати) кажется, что вы тестировали процессоры IBM Xenon. Я бы также предположил, что то же самое может быть применимо к встроенным микроконтроллерам более низкого уровня, но процессоры Intel и AMD имеют какой-то прогноз относительно косвенных скачков с ~ 2004 года или около того. Даже современные процессоры ARM не должны очищать весь конвейер без неверного прогноза.

Похожие вопросы