Если говорить о производительности вне существующих решений в железе, то интуиция будет подсказывать достаточно простую модель выполнения, когда процессор обрабатывает инструкции, а память поставляет данные, и чем быстрее и то и другое, тем быстрее работает программа.
Но процессоры научились выполнять миллиарды операций в секунду, а память наращивает скорость доступа намного медленнее, и разрыв между скоростью вычислений и доступа к данным стал настолько большим, что именно ожидание памяти, превратилось в главный источник потерь производительности.
Ответом на это стало не ускорение памяти, а усложнение самих процессоров, которые перестали быть просто пассивными исполнителями кода и стали решать задачи управления потоком данных: выполнять инструкции вне порядка, переупорядочивать зависимости и на каком-то этапе подошли к идее спекулятивно исполнять код, который, возможно, вообще не понадобится.
Предсказание ветвлений стало один из ключевых механизмов в этой системе, которая должна была снять часть времени простоя потока вычислений, но если удачное предсказание стало возможностью начать дорогие загрузки заранее и скрыть их латентность, то ошибка предсказания скрывает не только потерянные такты, но и зря использованные ресурсы памяти: шину, буферы загрузки, пропускную способность контроллера и сами кеш-линии, которые могли бы быть заняты полезными данными.
Именно здесь возникает интересный и неочевидный компромисс, позволяющий с одной стороны, писать branchless-код и полностью избавиться от ошибок предсказания, а с другой лишающий процессор возможности работать на опережение и запускать доступ к памяти раньше времени. Но в зависимости от того, где находятся данные в памяти выигрывать будет то один, то другой подход.
Если вы собираетесь писать branchless код, надо помнить как именно спекулятивное выполнение и предсказание ветвлений взаимодействуют с подсистемой памяти, потому что “лишняя работа” иногда ускоряет программу, а в некоторых случаях попытка сделать код более “предсказуемым” приводит к обратному эффекту.
Если смотреть на ранние компьютеры, то никакой спекуляции там не было и первые системы выполняли код последовательно, таская одну инструкция за другой, без попыток что-то угадать или ускорить за счёт предположений. Это была честная, но медленная модель, когда процессор делал ровно то, что ему сказали.
Потом оказалось, что производительность упирается не в сами вычисления, а в ожидание данных. Но сначала это были простои из-за длинных операций, потом из-за памяти и процессор часто мог выполнять инструкции быстрее, и большую часть времени простаивал.
Одним из первых серьёзных шагов в сторону “нарушения последовательности” стал проект IBM System/360 Model 91 в середине 60-х, когда команда инженеров, среди которых был Роберт Томасуло, предложила алгоритм динамического планирования инструкций, который позже получит его имя. Это позволило выполнять инструкции вне порядка (out-of-order), как только становились доступны их операнды, а не строго в том порядке, в котором они записаны в программе.
Это ещё не была полноценная спекуляция в современном исполнении, там уже был механизм выполнения инструкций вне порядка, но не предсказание ветвлений в современном смысле и процессор мог переупорядочивать независимые инструкции, однако выбор ветки всё ещё требовал разрешения условия.
Следующий шаг был в реализации идеи, если процессор уже умеет выполнять инструкции вне порядка и имеет историю ветвлений, то можно пойти ещё дальше и начать выполнять блоки ветвления до того, как станет известно, нужны ли они вообще. Так появляется спекулятивное выполнение.
В более-менее современном виде оно оформилось позже в суперскалярных процессорах 80+ годов. Одним из первых представителей здесь был Intel Pentium Pro (1995), где спекуляция, переупорядочивание и предсказание ветвлений уже работали вместе как единая система, позволяя выполнять инструкции вне порядка и начинать работать "наперёд". А конвейер на 40 микроопераций позволял удерживать десятки инструкций в полёте одновременно.
for (size_t i = 0; i < n; i++) { if (arr[i] >= 0) { ... code_true ...; } else { ... code_false ...; } }
Обычный if будет ветвлением на уровне языка, но на уровне потока данных в процессоре, он является точкой неопределённости, и чтобы понять, какую ветку выполнять, нужно сначала загрузить arr[i]. И тут мы получаем просадку перфа, потому что в точке получения arr[i]их может не оказаться в кешах, и в худшем случае простой здесь может занять десятки или даже сотни тактов, если данные и вовсе в оперативке. И поверьте это очень даже не редкий случай, когда данные в кеш попасть не успели.
Вариантов тут может быть несколько: если просто ждать, то останавливаются все инструкции, зависящие от этих данных, хотя OoO-процессор продолжит выполнять независимые инструкции из других цепочек, если угадать, то можно будет продолжить работу (но есть нюансы со сбросом, когда не угадали), если начать выполнять обе ветки ветвления, то сброса фактически не будет, но часть ресурсов придется отдать спекулятивному блоку выполнения. Со спекулятивным выполнением тоже есть свою нюансы, как положительные так и не очень, но о них позже.
Все современные процессоры предсказывают. Например по истории ветвлений, что ветка, скажем, будет истинной, и начинает выполнять code_true, параллельно ожидая данные из памяти. Если предсказание оказалось верным, то часть работы уже будет сделана и мы продолжаем выполнение, а если нет, то результаты откатываются, и выполняется другая ветка.
Здесь цена ошибки получается порядка 10–20 тактов, но цена ожидания памяти в разы больше, поэтому в среднем это выгодно. Учитывая, что большинство ветвлений строится вокруг одних и тех же данных, то с большой вероятностью данных для обеих веток исполнения будут уже в кеше, какую бы ветку вы не начали выполнять.
Как я уже сказал, спекуляция влияет не только на вычисления, но и на работу с памятью и когда процессор спекулятивно выполняет код, он также должен будет инициировать загрузки из памяти, занимать кеш-линии, и использовать ресурсы кеша, чтобы выполнить "ненужную" ветку код.
И если предсказание оказалось неверным, эти ресурсы "казалось бы" будут потрачены впустую. С этой точки зрения программиста кажется, что логичным шагом было бы вообще избавиться от ветвлений, поэтому вместе с появления механизма ветвлений, растет и число сторонников branchless-подхода (я тоже долгое время был адептом этой школы, пока ps4/5 не сломали мою "веру"). Допустим вы нашли в коде проекта места, которые выглядят как хорошие точки для применения "серых клеток":
if (arr[i] > 0) { result++; } -> result += (arr[i] > 0);
Что будет с кодом, в котором убрали ветвление? Первое - мы убрали ветвления (сюрприз) и теперь код не имеет misprediction (не может быть отложен), соответсвенно у такого кода "условно" не будет спекулятивной версии. Но современные процессоры рассчитаны на ветвления, и отложенное выполенние, поэтому мы получаем другую проблему и процессор теперь вынужден дождаться данных, прежде чем продолжить.
И тут возникает проблема, из-за которой наши "благие намерения" не только не улудшили перф, а наоборот его замедлили. Но опять же, все упирается в нюанcы.
Если к моменту выполнения данные arr находятся в быстром кеше L1, то задержка минимальная и мы получим прирост, потому что убрали "спекулятивную" ветку и освободили ресурсы процессора для реальной работы. В этом случае branchless-код часто выигрывает.
Если данные arr находятся в L2, то время выборки тоже достаточно мало, и цена ошибки предсказания становится менее заметной, но общего прироста скорости вычислений мы не видим. В этом случае branchless-код никак не влияет, разве что на читабельность исходников.
Но если данные приходят из L3 или памяти задерка по данным уже становится доминирующим фактором, и тогда важнее не ошибаться реже, а начинать работу раньше, чтобы к моменту реальных вычислений эти данные уже попали в кеши L1/L2. Так и получается, что рассчитанный на "спекулятивное" выполнение процессор, скрывал недостатки алгоритма и позволял ему работать с приемлимой скоростью.
Но избавившись от отложенного исполнения и переместив эту задержку непосредственно в точку вычислений, мы переносим это время в критический путь выполнения, где её уже нечем скрыть, и начинаем платить полную стоимость доступа к памяти на каждом шаге цикла, теряя то самое перекрытие вычислений и загрузок, которое раньше обеспечивала спекуляция.
Другой пример:
Value result = default_value; for (size_t i = 0; i < n; ++i) { if (keys[i] == target) { result = values[i]; } } return result.
Это "проблемная на вид" ветка, потому keys[i] == target почти случайное условие, и CPU не знает заранее, на каком i будет совпадение, поэтому предсказатель ошибается часто, и при каждом промахе предсказателя будет штраф на сброс конвейера, а values[i] так и не начали читать заранее. Мы решаем её немного переписать и сделать branchless версию.
Value result = default_value; for (size_t i = 0; i < n; ++i) { result = (keys[i] == target) ? values[i] : result; } return result;
У нас теперь нет ветки, нет промахов предсказателя. Теперь values[i] читается на каждой итерации безусловно, заставляя CPU подтягивать следующие элементы через prefetch. Но изменилась цена работы с памятью, потому оригинальный цикл делает чтение при совпадении, и если ключ найден на третьем элементе из десяти тысяч, то он прочитает только три элемента, а branchless будет всегда проходить весь массив, вычитывая как keys так и values.
Последствия адаптации современных процессоров к "спекулятивным" алгоритама хорошо видны на примере бинарного поиска. В branchful версии процессор будет предсказывать направление поиска, заранее вычислять low и highи может раньше инициировать загрузку следующего элемента. Да, примерно половина предсказаний будет неверной, но выигрыш от раннего доступа к памяти часто перекрывает эти потери.
while (low < high) { size_t mid = low + (high - low) / 2; if (keys[mid] < target) low = mid + 1; // CPU предсказывает это направление else high = mid; // и начинает читать keys[mid] следующей итерации }
В branchless версии, будет больше инструкций, загрузки будут начинаться позже, память используется без лишних спекулятивных загрузок, но каждая итерация вынуждена дожидаться результата предыдущей, и задержки памяти явно добавляются в работу алгоритма.
while (low < high) { size_t mid = low + (high - low) / 2; size_t step = (high - low) / 2; low = (keys[mid] < target) ? mid + 1 : low; high = (keys[mid] < target) ? high : mid; // нет ветки, но следующий mid вычислится только после записи low и high }
В branchful версии процессор видит if и начинает спекулятивно вычислять следующий mid и читать keys[mid] по предсказанной ветке, не дожидаясь результата сравнения. В branchless следующий mid зависит от новых low и high, которые зависят от результата сравнения и цепочка зависимостей не позволяет процессору забежать вперёд.
Такие нюансы очень часто всплывают при адаптации ПК игр для консолей, там исторически более слабые процессоры со своими подводными камнями, но картинка в целом получается такая: если данные случайные и массив меньше L1 кеша, то branchless почти всегда быстрее. Если массив большой или данные с явным паттерном доступа, то branchful может выиграть за счёт спекулятивных загрузок, но единственный способ знать точно - это профилировать на реальных данных, потому что конкретный процессор и характер данных меняют ответ кардинально. Вот тут я более предметно рассказывал про эффекты кеша, если кому интересен практический пример наступания на эти грабли, то вот простой пример бинарного поиска как из примеров выше на Jaguar (PS 4)
+----------------------+--------------+--------------+--------------+ | Benchmark | Branchful | Branchless | For Loop | +----------------------+--------------+--------------+--------------+ | BinarySearch/63 | 1914 ns | 904 ns | 704 ns | | BinarySearch/64 | 1984 ns | 995 ns | 795 ns | | BinarySearch/65 | 2006 ns | 1040 ns | 805 ns | | BinarySearch/66 | 2062 ns | 1086 ns | 886 ns | | BinarySearch/67 | 2113 ns | 1100 ns | 900 ns | | BinarySearch/68 | 2175 ns | 1148 ns | 948 ns | | BinarySearch/125 | 8404 ns | 3371 ns | 4371 ns | | BinarySearch/126 | 8216 ns | 3196 ns | 4196 ns | | BinarySearch/127 | 8952 ns | 3894 ns | 4894 ns | | BinarySearch/254 | 32792 ns | 32959 ns | 42959 ns | | BinarySearch/255 | 32950 ns | 32959 ns | 42959 ns | | BinarySearch/256 | 60374 ns | 59989 ns | 45989 ns | | BinarySearch/257 | 34202 ns | 33424 ns | 43424 ns | | BinarySearch/510 | 169570 ns | 192631 ns | 352631 ns | | BinarySearch/511 | 175509 ns | 196467 ns | 356467 ns | | BinarySearch/513 | 206741 ns | 225078 ns | 365078 ns | | BinarySearch/514 | 223825 ns | 243467 ns | 373467 ns | | BinarySearch/1022 | 1904859 ns | 1999431 ns | 3999431 ns | | BinarySearch/1023 | 1889650 ns | 1985054 ns | 3985054 ns | | BinarySearch/1024 | 1898959 ns | 1992857 ns | 3992857 ns | | BinarySearch/1026 | 1918389 ns | 2003320 ns | 4003320 ns | +----------------------+--------------+--------------+--------------+
Что интересного в результатах бенчмарка: на малых размерах от 63 до 68 элементов линейный перебор оказывается быстрее обоих вариантов бинарного поиска, что является прямым следствие архитектуры Jaguar с его L1 (32Кб) кешем, куда обычно помещаются небольшие массивы целиком. Задержек по памяти тут нет вообще и сам линейный перебор не имеет ни сложной логики вычисления mid, ни зависимостей между итерациями, поэтому процессор просто молотит его без остановок.
Eager Execution
Отдельные участки кода можно и вовсе переписать так, чтобы действительно выполнялись обе ветки. Вместо того чтобы выбирать одну ветку через if, код можно переписать так, чтобы вычислить оба варианта сразу, а затем выбрать нужный результат с помощью маски. На уровне данных это выглядит как выполнение двух веток параллельно без участия предсказателя ветвлений.
if (cond) x = a; else x = b; -> mask = cond ? 0xFFFFFFFF : 0; x = (a & mask) | (b & ~mask);
Приём оправдан в ситуациях, когда данные уже находятся в быстрых кешах, и стоимость ошибки предсказания ветвлений становится существенной, либо когда есть возможность эффективно распараллелить вычисления с помощью SIMD. Но т.к. обе ветки вычисляются всегда и полностью при каждом проходе это сильно увеличивает нагрузку на подсистему памяти.
На этом же диапазоне Branchless опережает Branchful, что объясняется достаточно слабым BPU Jaguar и там где Intel/AMD отделались бы штрафом в 10-15 тактов, Jaguar платит заметно больше из-за более простого BPU и меньшей глубины спекуляции, поэтому выигрыш от устранения ветвлений на малых данных здесь выше, чем можно было бы ожидать на десктопе.
Но начиная с 200+ элементов картинка меняется, и Branchful начинает догонять и обходить Branchless, а на 1022-1024 они уже практически сравниваются с небольшим преимуществом у Branchful, потому что данные всё реже оказываются в L1 целиком вместе с остальным рабочим контекстом, и задержки памяти начинают напрямую влиять на скорость вычислений.
Получается что спекулятивные загрузки Branchful-версии начинают перекрывать потери от ошибок предсказания, тогда как Branchless вынужден каждый раз дожидаться результата предыдущей итерации. For Loop на больших размерах предсказуемо деградирует быстрее всех с его O(n), и прямой перебор перестает быть выгодным уже на массиве более 100 элементов.
В итоге мы приходим к довольно нетривиальному выводу, что спекуляция напрямую взаимодействует с подсистемой памяти, одновременно увеличивая на неё нагрузку и скрывая её же задержки. Спекулятивное выполнение стоит ресурсов, но именно оно позволяет не стоять и ждать, пока память ответит, и получается, что производительность определяется не каким-то одним параметром, а балансом между ошибками предсказания, задержками памяти и доступной пропускной способностью. И этот баланс каждый раз разный в зависимости от данных, процессора и паттернов доступа.
Архитектура современного железа в каком-то смысле повторяет принцип любой сложной системы: надо учиться жить с системой эффективно, превращая потери в приемлемую цену за скорость работы.
З.Ы. Если Вы дочитали до этого места, то Вам наверное интересна немного тема производительности в приложениях и играх. В прошлом году я выложил статью "Game++. Dancing with allocators" на Хабре, из которой вырос позже целый цикл Game++, а потом и книга, которую БХВ выпустили не так давно.
Эта и еще пара статей стала основой для одной из глав книги, целиком посвященой программированию без аллокаций, пулам, стековым и кастомным аллокаторам, другим подходам и тому, как всё это ведёт себя в реальном игровом движке под нагрузкой. Материал в книге получился достаточно плотный, но все равно какие-то моменты остались за кадром, а мне хотелось дать возможность отработать его руками, а не просто прочитать. Поэтому я сделал из главы отдельный курс на Stepik "Нескучное программирование. С++ без аллокаций памяти".
Курс устроен так, что теория из пары глав книги разбита на короткие блоки, каждый сопровождается вопросами и задачами, которые нужно решить самому, а не просто запустить готовый код. Упражнения построены на реальных паттернах из игровой разработки, но без особой жести, мне главное было показать как можно обходить ограничения языка и улучшать производительность, иногда парой строк кода.
З.З.Ы. Всем кто пройдёт курс до конца и пришлет номер сертификата в сообщениях на степике - вышлю бумажную версию Game++ (По РФ, там проще, потому что издатель в Питере. С другими странами надо подумать как это сделать будет). Это не автоматически, поэтому напишите мне после прохождения и договоримся про доставку. FORHABRBOOK Скидка 50% на курс, что примерно равно стоимости самой книги. Ну и велкам в комментарии, напишите насколько вам зашел формат курса, думаю в следующем месяце открыть его на некоторое время для всех. А может кто и книгу уже успел почитать, тоже интересно какие впечатления.
