Комментарии 77

хороший перевод, спасибо


Скрытый текст
  • Knock knock
  • Branch prediction
  • Who's there?
В основном, каждое отдельное ветление часто срабатывают в одном направвлении, и очень редко в другом. Если каждый переход, еще на уровне компилятора, помечать в какую сторону он срабатывает чаще, то можно без сякого предсказания получать очень высокую вероятность правильного попадания.
Компании столько тысяч человеко-лет инвестировали в патенты, а ты им предлогаеш всю эту лавочку похерить.
Это не про предсказание переходов, а про группировку кода.
Чтобы редко используемые куски вынести подальше, чтобы они не перемешивались с «горячими» и не захламляли кеш L1.
Если «чаще» — это только 75%, то получаем проигрыш в сравнении с динамическими предикторами, которые дают 95%.
В основном, каждое отдельное ветление часто срабатывают в одном направвлении, и очень редко в другом.

Так себе гипотеза.
Почему вдруг? Гипотеза, что ветвления чаще всего срабатывают в одном направлении (назад, BTFNT), дает очень хороший прирост производительности, на фоне которого все остальные изыски — мелкие оптимизации.
Так считали люди, для которых оптимизация на 30% — не мелкая.
Очевидным вариантом является, что при наличии пустых таблиц для оптимизации предсказаний — считать, что все переходы — назад. При накоплении некоторой достаточной статистики — плавно переключаться на более продвинутые методы. Что интересно, именно такой подход используется в Pentium и, видимо, более поздних процессорах…
Таким образом мы получаем начальный уровень успеха предсказания не 50:50, а 80:20. Что дает хорошую прибавку к пенсии, пока накапливается статистика для остальных предикторов.
Почему же? Intel в старых процессорах её использовала. Переходы назад — likely, переходы вперёд — unlikely.
Видимо, Intel посчитала, что может лучше предсказывать переходы.
Потому что не отказалась?
Какая-та статическая модель предсказаний до сих пор используется в случаях, если таблицы для динамических предикторов пусты.
Не какая-то, а вполне конкретная — fallthrough likely. Собственно, это даже сложно назвать моделью, просто принимается самое простое решение из всех возможных. Однако это не полноценный статический предиктор, о котором мы говорили — выше по ветке речь шла про 2EH/3EH префиксы :)
Скорее всего, этого можно достичь с PGO. Скорее всего, разработчики компиляторов в курсе, какие ветвления лучше предсказываются процессором, и строят код именно так, чтобы достичь минимума ошибок перехода для тестового случая.
Интересно, а как процессор контролирует изменение кода? Например при выгрузке/загрузке в своп. Или никак, просто некоторое время перезаполняет таблицу переходов с кучей промахов?
При Page Fault происходит аппаратное прерывание, приводящее к сбросу конвейера.
Ничего страшного в этом нет: по сравнению с чтением из диска, разгон конвейера — мгновение.
А таблицы переходов являются частью конвейера или привязаны к оперативке? Или при каждом переключении задачи это всё сбрасываться в 0? Не очень понял этот момент. Или это какие-то внутренние регистры проца?
Всё, что я могу сказать — никакой привязки к оперативке быть не должно: в инструкциях x86 просто не предусмотрено хранения соответстующего флага предпочтительной ветки, да и в случае ROM непонятно, как быть.

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

А вообще, это нужно уже инженеров Intel спрашивать, потому что гадание на кофейной гуще получается.
Я боюсь, что даже те, кто знает ничего не скажут. Если интересно, есть хорошие мануалы от Agner Fog, которые лучше публичной документации некоторых компаний.
Иными словами, хорошей практикой является упрощение ветвлений до такой степени, чтобы их ветки (по возможности) выполнялись всегда и без ошибок. Правильно?
GPU так и работают, поскольку условные переходы там весьма дороги (если получаются разные переходы в пределах одной группы потоков). Там куча встроенных инструкций (типа min, max, clamp), которые позволяют избавиться от очень большого количества условных переходов. А некоторые переходы бывает дешевле (и достаточно не сложно) свести к чуть более громоздким вычислениям, чем пихать лишний if. Например вместо
if( a < 10.) b = 20.; else b = 30.;
можно
b = 20. + step(a, 10.) * 10.;
обычно есть способ заинвалидировать таблицу переходов, чтобы избежать ложных срабатываний. Ядро операционки должно это делать при переключении контекста
Не совсем так. В x86/amd64 архитектуре этого делать не нужно. А вот в ARM есть соответствующая команда.
А зачем кэш инвалидировать? Внутренний кэш декодированных инструкций очистится сам. Кэш памяти же ещё пригодится, когда ОС вернёт управление процессу.
В случае x86 ни branch predictor ни кэш инвалид рожать не нужно. Что касается ARM, там инструкция branch predictor invalidate действительно присутствует, но с некоторых пор ничего не делает и оставлена в целях совместимости. Кэш же в ARM программист обязан инвалидировать в случае self-modified code, а именно, если код был перезаписан, программист обязан выполнить Data Cache Clean by VA at Point of Unification и Instruction Cache Invalidate by VA at Point of Unification. Связано это с тем, что в ARM кэш инструкций согласно архитектуре не является когерентным.
Сорри, там не 'инвалид рожать', а инвалидировать. Это всё грёбаная автозамена в андроиде
Можно ли перенести предсказание переходов с аппаратной части на программную (компилятор, стат.анализатор, правила написания кода) и будет ли это выгоднее с точки зрения скорости исполнения? Я имею в виду не взаимодействие с пользователем или оборудованием, а числомолотилки.
В числомолотилках эта проблема не настолько актуальна.
Разворот циклов, условное выполнение операций (в SSE/AVX расширениях) — и ветвлений становится значительно меньше.
Возьмём, например, умножение матриц:
void mult(int n, double *a, *b, *c) {
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            ....

При n=3 динамический предиктор рано или поздно выявит паттерн, что во внутреннем цикле каждый 3-й переход не выполняется, а как это должен понять компилятор?
На практике размер матриц, особенно небольших, редко является произвольным.
Поэтому n будет константой, и оптимизирующий компилятор просто развернёт цикл.
Это модельный пример. На практике может быть любой другой цикл обработки данных, который программист сделал параметризуемым, а параметр читается из конфига.
Если производительность настолько важна, то в приложении можно сделать несколько веток: для n = 2, n = 3, n = 4 и произвольного n, где ошибки в предсказании ветвления для внутренних циклов уже не насколько критичны.
Вопрос выше был, что может сделать компилятор, а не программист вручную )))
Ну, теоретически, компилятор может сделать versioning. Т.е. несколько кусков кода под разные параметры.
Если только PGO.
Иначе откуда компилятор узнает, какой кусок кода наиболее критичен.
Если n константное, то можно развернуть цикл. Если неконстантное, но вычислимое заранее, то тоже можно, если язык есть поддержка самомодифицирующегося кода. Можно попробовать векторизовать и раскидать на разные ядра, предвычислив i и/или j
PS Компиляторов не писал, процессоров не разрабатывал, так что все мои рассуждения сугубо теоретические
Цикл менее 1000 итераций, внутри которых пара арифметических действий, нет смысла раскидывать по ядрам. Больше потеряешь на создании потоков.

Насколько я видел (OpenMP, TPL и т.п.), везде программист даёт указания, что можно попробовать запараллелить. Поскольку программисты оптимизируют только горячие места, а не всё подряд, оптимизации всего остального лучше переложить на процессор.
Подскажите, если не сложно, статью, где обобщенно (я понимаю, что серебряной пули нет) рекомендуется, начиная со скольки итераций/инструкций и какого объёма памяти раскидывание по ядрам или на GPU становится выгодным.
Ха, у процессора есть таймер с потактовой точностью замера (RDTSC).
Можете сами померять, сколько что стоит, и сделать соответствующие расчёты.
Проверяется просто: создаёте поток в играете с ним в пинг-понг через средства синхронизации.

Вот одна из простейших реализаций parallel do: https://gist.github.com/e673/31b73495bfb83e818f226d2300568176

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

Под Windows на 4-ядерном процессоре при N = 3 у меня получается 400к переключений в секунду (при N = 1, кстати, получается ~2 миллиона), т.е. ~10000 тактов уходит только на одну синхронизацию. Под Linux на 2-ядернике вдвое меньшей частоты при N = 1 — 80к переключений.

Чем на большее число потоков вы параллелите задачу, тем выше накладные расходы. Я даже боюсь представить, что будет твориться на Threadripper при 32 потоках, ведь блокировка шины при изменении атомарной переменной, за которую борется куча потоков — штука очень неприятная.

То есть, чтобы задачу вообще имело смысл параллелить, задача должна выполняться ощутимое время — несколько десятков микросекунд.

Кстати, низкая гранулярность тоже может оказаться не в фаворе, если будет страдать локальность доступа к памяти.
Update: при использовании Windows-specific варианта при больших N (N = 8 и выше) накладные расходы становятся ниже, чем при кросс-платформенном варианте.
Кстати в командах x86 есть ведь и команды для цикла ( loop и иже с ними ). Нельзя ли их как-то оптимизировать и делать циклы по возможности на них. Правда для вложенных циклов необходимо, чтобы компилятор достаточно заранее восстанавливал CX, чтобы все ступени конвейера успели среагировать.
Кстати, с VLIW-компиляторами как-то выкрутились, или по прежнему не получается выжать всё из архитектуры?
У меня ощущение, что они не нужны никому. Тот же Intel прекратил развитие Itanium.
Есть ещё неподимый и легендарный Эльбрус, но документацию я одолеть не смог, она гораздо грустнее интеловской, и компилятор я не знаю, где скачать
Можно-то можно, но есть один нюанс. Дешифрация команды не происходит мгновенно, и сколько тактов пройдет, прежде чем процессор поймет, что он испольняет команду ветвления — одному Аллаху ведомо. А знать это процессору необходимо сразу, ибо следующую команду надо выбирать уже на следующем такте.
Современные процессоры не читают по одной инструкции — они гребут код, что называется, «большой лопатой». В частности, мне приходилось видеть CPU, который читает по 2 кэшлайна кода за такт.
Согласен. Только декодирование — процесс достаточно быстрый, и, соответственно, на out of order CPU о том, что инструкция является переходом, может быть известно сильно раньше, чем она реально начнёт исполняться. Что же касается двухстадийного конвейера, который нам упорно рисуют в статье, так в нём вообще можно обойтись без предсказания переходов — человечество изобрело такое понятие как delay slot.

Довольно интересная ситуация, когда предсказание переходов можно пощупать на практике:


https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array


Задача: пробежаться по массиву байт и посчитать количество байт, больших 128.
Наблюдение: при случайном заполнении скорость работы алгоритма в 6 раз медленнее, чем при неслучайном (отсортированный массив).

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

> Можно ли пойти сразу по двум веткам одновременно и отбросить результат работы той, что не сбылась?

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

По такому принципу кстати работают GPU. Но там это обусловлено тем, что блоки по 32 ядра (warpы в cuda) в один момент времени могут выполнять только одинаковые инструкции.

Не совсем по такому. Речь об одновременном выполнении обоих, а в GPU последовательное. Так что вместо выигрыша получаем наоборот проигрыш. Но там это частично решается кучей команд условных вычислений.
НЛО прилетело и опубликовало эту надпись здесь
В наборе x86/x64 нет такой инструкции.

С другой стороны, зачем? Если ветвление выполняется часто, оно будет запомнено и не вытеснится из буфера предсказаний. А если редко, потеря нескольких тактов не важна.
НЛО прилетело и опубликовало эту надпись здесь
может даже так сложиться, что именно вторая, малоприоритетная ветка станет выполняться чаще, что добавит тактов 10 на перезагрузку конвейера в случае, когда код должен быть максимально быстрым
Не понимаю примера. Статически — это значит один раз при компиляции, без возможности изменения. То есть, эта ветка 100 раз выполнялась, её предиктор пометил как приоритетную, а потом она 3 раза не выполнилась и предиктор промахнулся? А что будет, если её статически пометить как не приоритетную? Будет 100 промахов и 3 попадания?

Если они близки к случайным, то в половине случаев (!) предсказатель будет ошибаться и результат работы будет ужасный
Что предлагается? Например, в цикле
for (int i = 0; i < N; i++) { if (i & 1) { .... } }

Перед условным переходом вычислить i&1 и выполнить какую-то команду, которая подскажет по значению i, будет ли переход? Так такая команда — то же самое, что и ветвление, почему бы эти 2 команды не объединить в логику инструкции ветвления. На самом дела, нужно загрузить конвеер намного заранее до вычисления условия, а не прямо перед ним.
НЛО прилетело и опубликовало эту надпись здесь
Но такой возможности на x64 нет.

Архитектура х86 всё равно не подходит для задач реального времени, которые, видимо, вам нужно выполнять, раз у вас такие критические требования к предсказуемости скорости выполнения.
На самом деле не совсем. Например в циклах о том, будет ли переход часто известно ещё в начале цикла, что (теоретически) можно использовать. Кстати у x86 есть встроенная команда (loop и её вариации) которую можно было бы оптимизировать предсказанием, если бы были какие-то гарантии, что её рабочий регистр (CX для основного варианта) не используют подо что-то другое. Правда там ещё есть варианты, которые по флагам работаю, и тут уже ничего не предскажешь.
Допустим минус вопросу означает, что это не юмор. Тогда тем более не понимаю, к чему это было вынесено в заголовок и больше в тексте не упоминалось.
Допустим минус вопросу означает, что это не юмор

Непонятна основа такого допущения.
Мне кажется что лучше было бы использовать не «цель перехода», а «целевой адрес перехода». К слову «цель» напрашивается вопрос «зачем», но это совсем не то, что имелось в виду.
Замените пожалуйста везде по тексту «подым(\S+)» на «подним$1». А то читать тяжело с самого начала.
Объясните, пожалуйста следующий момент:

if x > 0:
x -= 1
if y > 0:
y -= 1
if x * y > 0:
foo()


Если произойдёт переход по первой или второй ветви, то третья определённо останется незадействованной.


Пусть x = 3, y = 3… Независимо от того, по какой из ветвей пойдёт код (даже если по обеим), условие выполнения третьей всегда будет истинно (2*2 > 0). Или какой это язык? Возможно имелось ввиду x = -1?

В чём смысл вставок с кодом, если они никаких пояснений не вносят?
Объясняю: это косяки перевода.
В оригинале: If either the first branch or the next branch isn’t taken, then the third branch definitely will not be taken.
То есть вместо «или» должно быть «исключающее или».
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.