Вы стали жертвой предсказания ветвления сбоя.
Что такое прогнозирование переходов?
Рассмотрим железнодорожный узел:
Изображение от Mecanismo, через Wikimedia Commons. Используется по лицензии CC-By-SA 3.0.
Теперь для аргументации предположим, что это еще в 1800-х годах - до междугородной или радиосвязи.
Вы оператор развязки и слышите приближающийся поезд. Вы не представляете, по какому пути он должен идти. Вы останавливаете поезд, чтобы спросить машиниста, в каком направлении они хотят. Затем вы устанавливаете переключатель соответствующим образом.
Поезда тяжелые и обладают большой инерцией, поэтому они бесконечно запускаются и замедляются.
Есть способ лучше? Вы угадаете, в каком направлении пойдет поезд!
- Если вы угадали, это продолжается.
- Если вы ошиблись, капитан остановится, отступит назад и крикнет, чтобы вы щелкнули выключателем. Затем он может перезапуститься по другому пути.
Если вы угадаете каждый раз правильно , поезд никогда не должен будет останавливаться.
Если вы слишком часто угадаете, , поезд будет много времени останавливаться, резервное копирование и перезапуск.
Рассмотрим оператор if: На уровне процессора это инструкция ветвления:
Вы процессор и видите ветку. Вы не представляете, в каком направлении это пойдет. Что вы делаете? Вы останавливаете выполнение и ждете, пока не будут выполнены предыдущие инструкции. Затем продолжайте движение по правильному пути.
Современные процессоры сложны и имеют длинные конвейеры. Это означает, что им потребуется целая вечность, чтобы «разогреться» и «замедлиться».
Есть способ лучше? Вы угадаете, в каком направлении пойдет ветка!
- Если вы угадали, продолжайте выполнение.
- Если вы не угадали, нужно промыть конвейер и откатиться на ветку. Затем вы можете перезапустить другой путь.
Если вы угадываете каждый раз правильно , выполнение никогда не должно останавливаться.
Если вы слишком часто угадываете неправильно , вы тратите много времени на откатывание назад и перезапуск.
Это прогнозирование ветвления. Признаюсь, это не лучшая аналогия, поскольку поезд мог просто сигнализировать о направлении флагом. Но в компьютерах процессор до последнего момента не знает, в каком направлении пойдет ветвь.
Как вы стратегически догадались бы минимизировать количество раз, когда поезд должен возвращаться назад и спускаться по другому пути? Вы посмотрите на прошлую историю! Если поезд идет налево в 99% случаев, значит, вы угадали. Если он чередуется, то вы меняете свои догадки. Если каждые три раза он пойдет в одну сторону, вы угадаете то же самое ...
Другими словами, вы пытаетесь идентифицировать шаблон и следовать ему. Более или менее так работают предикторы ветвления.
У большинства приложений есть ветки с хорошим поведением. Следовательно, современные предсказатели ветвления обычно достигают> 90% попаданий. Но когда вы сталкиваетесь с непредсказуемыми ветвями без распознаваемых паттернов, предсказатели ветвлений практически бесполезны.
Дополнительная литература: Статья «Предиктор ветвления» в Википедии.
Как указано выше, виноват следующий оператор if:
if (data[c] >= 128)
sum += data[c];
Обратите внимание, что данные равномерно распределены между 0 и 255. Когда данные сортируются, примерно первая половина итераций не входит в if-оператор. После этого все они войдут в оператор if.
Это очень удобно для предсказателя ветвления, поскольку ветвление последовательно проходит в одном и том же направлении много раз. Даже простой счетчик насыщения правильно предсказывает ветвь, за исключением нескольких итераций после смены направления.
Быстрая визуализация:
T = branch taken
N = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
Однако, когда данные полностью случайны, предсказатель ветвления становится бесполезным, потому что он не может предсказать случайные данные. Таким образом, вероятно, будет около 50% ошибочных прогнозов (не лучше, чем случайное предположение).
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T ...
= TTNTTTTNTNNTTT ... (completely random - impossible to predict)
Что можно сделать?
Если компилятор не может оптимизировать ветвь в условное перемещение, вы можете попробовать несколько хаков, если вы готовы пожертвовать удобочитаемостью ради производительности.
Заменить:
if (data[c] >= 128)
sum += data[c];
с:
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
Это устраняет ветвление и заменяет его некоторыми побитовыми операциями.
(Обратите внимание, что этот прием не является строго эквивалентным исходному оператору if. Но в данном случае он действителен для всех входных значений data[]
.)
Тесты: Core i7 920 @ 3,5 ГГц
C ++ - Visual Studio 2010 - выпуск x64
Сценарий |
Время (секунды) |
Ветвление - случайные данные |
11,777 |
Ветвление - Сортированные данные |
2,352 |
Без филиалов - случайные данные |
2,564 |
Без филиалов - Сортированные данные |
2,587 |
Java - NetBeans 7.1.1 JDK 7 - x64
Сценарий |
Время (секунды) |
Ветвление - случайные данные |
10.93293813 |
Ветвление - Сортированные данные |
5.643797077 |
Без филиалов - случайные данные |
3,113581453 |
Без филиалов - Сортированные данные |
3,186068823 |
Наблюдения:
-
С веткой: Между отсортированными и несортированными данными существует огромная разница.
-
С помощью взлома: Нет разницы между отсортированными и несортированными данными.
- В случае C ++ взлом на самом деле немного медленнее, чем с ветвью при сортировке данных.
Общее практическое правило - избегать зависимых от данных ветвлений в критических циклах (например, в этом примере).
Обновление:
-
GCC 4.6.1 с -O3
или -ftree-vectorize
на x64 может генерировать условное перемещение, поэтому нет никакой разницы между отсортированными и несортированными данными - оба работают быстро.
(Или несколько быстро: для уже отсортированного случая cmov
может быть медленнее, особенно если GCC помещает его на критический путь вместо просто add
, особенно на Intel до Broadwell, где cmov
имеет задержку в 2 цикла : Флаг оптимизации gcc -O3 делает код медленнее, чем -O2)
-
VC ++ 2010 не может генерировать условные перемещения для этой ветви даже под /Ox
.
-
Компилятор Intel C ++ (ICC) 11 творит чудеса. Он меняет местами два цикла, тем самым поднимая непредсказуемую ветвь во внешний цикл. Он не только невосприимчив к ошибочным предсказаниям, но и в два раза быстрее, чем все, что может генерировать VC ++ и GCC! Другими словами, ICC воспользовалась тестовым циклом, чтобы обойти тест ...
-
Если вы дадите компилятору Intel код без ветвей, он просто векторизует его ... и будет так же быстро, как и с ветвлением (с заменой цикла).
Это говорит о том, что даже зрелые современные компиляторы могут сильно различаться по своей способности оптимизировать код ...
Для записи ваши данные не нужно сортировать, только разделенные на разделы, что намного быстрее.
Еще одно наблюдение состоит в том, что вам не нужно сортировать массив, вам просто нужно разделить его со значением 128. Сортировка n * log (n), тогда как разделение просто линейное. По сути, это всего лишь один запуск шага быстрой сортировки по разделу с выбранным значением поворота 128. К сожалению, в C ++ есть только функция nth_element, которая выполняет разделение по позиции, а не по значению.
@screwnut вот эксперимент, который покажет, что разделения достаточно: создайте несортированный, но разделенный массив со случайным содержимым. Измерьте время. Сортировать. Снова измерить время. Эти два измерения должны быть в основном неразличимы. (Эксперимент 2: создайте случайный массив. Измерьте время. Разделите его. Измерьте время еще раз. Вы должны увидеть такое же ускорение, как и сортировка. Вы можете объединить два эксперимента в один.)
Кстати. на Apple M1 код выполняется за 17 секунд без сортировки и за 7 секунд после сортировки, так что штраф за предсказание ветвления не так уж плох для рисковой архитектуры.
@RomanYavorskyi: Это зависит от компилятора. Если они сделают asm без ответвлений для этого конкретного теста (например, как часть векторизации с помощью SIMD, как в ) Почему обработка несортированного массива такая же скорость, как и обработка отсортированного массива с помощью современных x86-64 clang? или просто с скаляр
cmov
(флаг оптимизации gcc -O3 делает код медленнее, чем -O2), то отсортированный или нет не имеет значения. Но непредсказуемые ветви все еще очень реальны, когда это не так просто, как подсчет, так что было бы безумием удалять этот вопрос.@screwnut: Однако, честно говоря, все равно не стоит сначала размечать разделы, потому что разделение требует условного копирования или подкачки на основе того же сравнения
array[i] > 128
. (Если вы не собираетесь считать несколько раз и хотите разделить большую часть массива, чтобы он оставался быстрым, только неверное предсказание в неразмеченной части после некоторых добавлений или модификаций). Если вы можете заставить компилятор сделать это, в идеале просто векторизуйте с помощью SIMD или, по крайней мере, используйте скаляр без ветвей, если данные непредсказуемы. (Ссылки см. В предыдущем комментарии.)