Влияние отраслевого прогнозирования на производительность?

Question

Когда я пишу какой-то жесткий цикл, который должен работать быстро, меня часто беспокоят мысли о том, как будет вести себя предсказание ветви процессора. Например, я стараюсь изо всех сил избегать использования оператора if в самом внутреннем цикле, особенно с результатом, который не является несколько однородным (скажем, случайным образом оценивается как true или false).

Я склонен это делать из-за довольно распространенного знания о том, что процессор предварительно выбирает инструкции, и если выяснилось, что он неправильно предсказал переход, тогда предварительная выборка бесполезна.

Мой вопрос - действительно ли это проблема современных процессоров? Насколько хорошим может быть предсказание ветвления?
Какие шаблоны кодирования можно использовать, чтобы сделать его лучше?

(Ради обсуждения предположим, что я за рамками фазы "ранняя оптимизация - корень зла")

Answer 1

Предсказание ветвей в наши дни чертовски хорошее. Но это не значит, что штрафы за ветки могут быть устранены.

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

Одним из них является простая задержка ветвления. На обычном процессоре ПК это может быть порядка 12 циклов для неверного прогноза или 1 цикла для правильно предсказанной ветви. Ради аргумента, давайте предположим, что все ваши ветви правильно предсказаны, тогда вы свободны дома, верно? Не совсем.

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

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

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

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

Answer 2

"(Ради обсуждения предположим, что я за рамками" ранней оптимизации - корень зла ")"

Отлично. Затем вы можете профилировать производительность вашего приложения, использовать теги gcc, чтобы сделать прогноз и снова профилировать, использовать теги gcc, чтобы сделать противоположный прогноз и снова профилировать.

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

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

Answer 3

Если мы находимся за пределами фазы «ранней оптимизации», то, конечно же, мы за рамками фазы «Я могу измерить»? С безумными сложностями современной архитектуры процессоров, единственный способ узнать наверняка, это попробовать и измерить. Конечно, не может быть так много обстоятельств, когда у вас будет выбор из двух способов реализации чего-либо, один из которых требует ответвления, а другой - нет.

Answer 4

Да, прогноз ветвления действительно может быть проблемой производительности.

Этот вопрос (в настоящее время вопрос с наибольшим количеством голосов в StackOverflow) дает пример.

Answer 5

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

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

Answer 6

Мой ответ:

Причина, по которой AMD в некоторых моментах была быстрее или лучше, чем у Intel, заключается в том, что у них просто было лучшее предсказание ветвлений.

Если в вашем коде нет прогноза ветвления (имеется в виду, что у него нет ветвей), то можно ожидать, что он будет выполняться быстрее.

Итак, вывод: избегайте веток, если они не нужны. Если это так, попробуйте сделать так, чтобы одна ветвь оценивалась 95% времени.

Answer 7

Одна вещь, которую я недавно обнаружил (на TI DSP), состоит в том, что попытка избежать ветвлений может иногда генерировать больше кода, чем стоимость прогнозирования ветвлений.

У меня было что-то вроде следующего в узком цикле:

if (var >= limit) { otherVar = 0;}

Я хотел избавиться от потенциальной ветви и попытался изменить ее на:

otherVar *= (var<limit)&1;

Но «оптимизация» сгенерировала вдвое больше сборок и была на самом деле медленнее.