Избегайте останова конвейера, вычисляя условно рано
Говоря о производительности ifs, мы обычно говорим о том, как неправильные прогнозы могут остановить конвейер. Рекомендованные решения, которые я вижу:
- Доверяйте предсказателю ветвления условия, которые обычно имеют один результат; или же
- Избегайте ветвления с небольшим количеством волшебства, если это возможно; или же
- Условные ходы, где это возможно.
Что я не смог найти, так это то, можем ли мы рассчитать условие раньше, чтобы помочь, где это возможно. Итак, вместо:
... work
if (a > b) {
... more work
}
Сделайте что-то вроде этого:
bool aGreaterThanB = a > b;
... work
if (aGreaterThanB) {
... more work
}
Может ли что-то подобное вообще избежать остановок по этому условию (в зависимости от длины конвейера и объема работы, которую мы можем поставить между bool и if)? Это не должно быть так, как я написал, но есть ли способ оценить условности на ранних этапах, чтобы ЦП не пытался предсказывать переходы?
Кроме того, если это поможет, это то, что компилятор, вероятно, все равно будет делать?
3 ответа
Несоблюдение порядка выполнения - это определенно вещь (не только компиляторы, но даже сами микросхемы процессора могут переупорядочивать инструкции), но оно помогает в случае останова конвейера, вызванного зависимостями данных, а не из-за неправильных предсказаний.
Преимущество в сценариях потока управления несколько ограничено тем фактом, что на большинстве архитектур команды условного перехода принимают решение только на основе регистра флагов, а не на регистре общего назначения. Трудно настроить регистр флагов заранее, если только промежуточная "работа" не очень необычна, потому что большинство инструкций изменяют регистр флагов (на большинстве архитектур).
Возможно выявление комбинации
TST (reg)
J(condition)
может быть разработан, чтобы свести к минимуму стойло, когда (reg) установлен достаточно далеко заранее. Это, конечно, требует большой помощи со стороны процессора, а не только компилятора. И разработчики процессоров, вероятно, оптимизируют для более общего случая раннего (не по порядку) выполнения инструкции, которая устанавливает флаги для ветви, с результирующими флагами, перенаправляемыми по конвейеру, заканчивая остановку досрочно.
Да, может быть полезно позволить вычислить условие ветвления как можно раньше, чтобы любое неправильное прогнозирование могло быть устранено досрочно, и входная часть конвейера могла начать пополнение рано. В лучшем случае неправильное предсказание может быть бесплатным, если в полете уже достаточно работ, чтобы полностью скрыть пузырьки переднего конца.
К сожалению, для процессоров с неупорядоченным порядком раннее имеет несколько тонкое определение, и поэтому заставить ветвь разрешить рано не так просто, как просто перемещать строки в источнике - вам, вероятно, придется изменить способ условие рассчитывается.
Что не работает
К сожалению, ранее не ссылается на положение условия / ветви в исходном файле и не ссылается на позиции инструкций сборки, соответствующих сравнению или ветви. Так что на фундаментальном уровне, это в основном 7 не работает, как в вашем примере.
Даже если позиционирование на уровне источника имело значение, оно, вероятно, не сработает в вашем примере, потому что:
Вы переместили оценку состояния и присвоили ее bool, но это не тест (< оператор), который может неправильно предсказать, это последующая условная ветвь: в конце концов, это ошибочное предсказание ветвления. В вашем примере ветка находится в одном и том же месте в обоих местах: ее форма просто изменилась с if (a > b) в if (aGreaterThanB),
Кроме того, то, как вы преобразовали код, вряд ли обманет большинство компиляторов. Оптимизирующие компиляторы не выводят код построчно в том порядке, в котором вы его написали, а скорее планируют все по своему усмотрению, основываясь на зависимостях исходного уровня. Поднятие условия раньше, скорее всего, будет просто проигнорировано, так как компиляторы захотят поставить проверку в том месте, в котором она, естественно, находится: примерно перед веткой на архитектурах с регистром флагов.
Например, рассмотрим следующие две реализации простой функции, которые следуют предложенному вами шаблону. Вторая функция перемещает условие наверх функции.
int test1(int a, int b) {
int result = a * b;
result *= result;
if (a > b) {
return result + a;
}
return result + b * 3;
}
int test2(int a, int b) {
bool aGreaterThanB = a > b;
int result = a * b;
result *= result;
if (aGreaterThanB) {
return result + a;
}
return result + b * 3;
}
Я проверил gcc, clang 2 и MSVC, и все они скомпилировали обе функции одинаково (выходные данные отличались для разных компиляторов, но для каждого компилятора выходные данные были одинаковыми для двух функций). Например, компиляция test2 с gcc привело к:
test2(int, int):
mov eax, edi
imul eax, esi
imul eax, eax
cmp edi, esi
jg .L4
lea edi, [rsi+rsi*2]
.L4:
add eax, edi
ret
cmp инструкция соответствует a > b условие, и gcc переместил его обратно через всю "работу" и поместил его прямо рядом с jg которая является условной ветвью.
Что работает
Так что, если мы знаем, что простое манипулирование порядком операций в источнике не работает, что работает? Оказывается, что все, что вы можете сделать, переместить условие ветвления "вверх" в графе потока данных, может повысить производительность, позволяя разрешить неправильное предсказание раньше. Я не собираюсь углубляться в то, как современные процессоры зависят от потока данных, но вы можете найти здесь краткий обзор с указаниями для дальнейшего чтения в конце.
Обход связанного списка
Вот реальный пример, включающий обход связанного списка.
Рассмотрим задачу суммирования всех значений в конце связанного списка с нулевым символом в конце, который также хранит его длину 1 в качестве члена структуры заголовка списка. Связанный список реализован как один list_head объект и ноль или более узлов списка (с одним int value полезная нагрузка), определяется так:
struct list_node {
int value;
list_node* next;
};
struct list_head {
int size;
list_node *first;
};
Канонический цикл поиска будет использовать node->next == nullptr часовой в последнем узле, чтобы определить, что он достиг конца списка, вот так:
long sum_sentinel(list_head list) {
int sum = 0;
for (list_node* cur = list.first; cur; cur = cur->next) {
sum += cur->value;
}
return sum;
}
Это так просто, как вы можете.
Тем не менее, это ставит ветвь, которая заканчивает суммирование (тот, который первым cur == null) в конце поиска указателя от узла к узлу, который является самой длинной зависимостью в графе потока данных. Если эта ветвь неверно предсказывает, разрешение ошибочного прогноза произойдет "поздно", и интерфейсный пузырь будет добавлен непосредственно к среде выполнения.
С другой стороны, вы можете выполнить суммирование путем явного подсчета узлов, например:
long sum_counter(list_head list) {
int sum = 0;
list_node* cur = list.first;
for (int i = 0; i < list.size; cur = cur->next, i++) {
sum += cur->value;
}
return sum;
}
Сравнивая это с часовым решением, кажется, что мы добавили дополнительную работу: теперь нам нужно инициализировать, отслеживать и уменьшать счет 4. Ключевым моментом, однако, является то, что эта цепочка зависимостей декремента очень короткая, и поэтому она "опережает" работу по отслеживанию указателей, и неправильное прогнозирование произойдет рано, в то время как все еще остается действительная работа по отслеживанию указателей, возможно, с большое улучшение во время выполнения.
Давайте на самом деле попробуем это. Сначала мы рассмотрим сборку для двух решений, чтобы убедиться, что ничего неожиданного не происходит:
<sum_sentinel(list_head)>:
test rsi,rsi
je 1fe <sum_sentinel(list_head)+0x1e>
xor eax,eax
loop:
add eax,DWORD PTR [rsi]
mov rsi,QWORD PTR [rsi+0x8]
test rsi,rsi
jne loop
cdqe
ret
<sum_counter(list_head)>:
test edi,edi
jle 1d0 <sum_counter(list_head)+0x20>
xor edx,edx
xor eax,eax
loop:
add edx,0x1
add eax,DWORD PTR [rsi]
mov rsi,QWORD PTR [rsi+0x8]
cmp edi,edx
jne loop:
cdqe
ret
Как и ожидалось, дозорный подход несколько проще: на одну инструкцию меньше во время установки и на одну инструкцию меньше в цикле 5, но в целом этапы поиска и добавления указателя ключа идентичны, и мы ожидаем, что в этом цикле будет доминировать задержка последующего узла указатели.
Действительно, циклы работают практически одинаково при суммировании коротких или длинных списков, когда влияние на прогноз незначительно. Для длинных списков влияние предсказания ветвления автоматически становится небольшим, поскольку единственное неверное предсказание при достижении конца списка амортизируется по многим узлам, и время выполнения асимптотически достигает почти ровно 4 цикла на узел для списков, содержащихся в L1, что мы ожидаем, что у Intel будет наилучшая 4-тактная задержка загрузки для использования.
Для коротких списков ошибочное прогнозирование ветвлений является незначительным, если шаблон списков предсказуем: либо всегда один и тот же, либо циклический с некоторым умеренным периодом (который может быть 1000 или более с хорошим прогнозом!). В этом случае время на узел может составлять менее 4 циклов при суммировании многих коротких списков, поскольку несколько списков могут быть запущены одновременно (например, если суммируется массив списков). В любом случае обе реализации работают практически одинаково. Например, когда списки всегда имеют 5 узлов, время суммирования одного списка составляет около 12 циклов с любой реализацией:
** Running benchmark group Tests written in C++ **
Benchmark Cycles BR_MIS
Linked-list w/ Sentinel 12.19 0.00
Linked-list w/ count 12.40 0.00
Давайте добавим предсказание ветвления в смесь, изменив код генерации списка, чтобы создать списки со средней длиной 5, но с фактической длиной, равномерно распределенной в [0, 10], Код суммирования не изменяется: отличается только вход. Результаты со случайными длинами списка:
** Running benchmark group Tests written in C++ **
Benchmark Cycles BR_MIS
Linked-list w/ Sentinel 43.87 0.88
Linked-list w/ count 27.48 0.89
BR_MIS В столбце показано, что мы получаем почти одно неверное предсказание ветвления на список 6, как и ожидалось, поскольку выход из цикла непредсказуем.
Тем не менее, теперь часовой алгоритм занимает ~44 цикла против ~27.5 циклов алгоритма подсчета. Алгоритм подсчета примерно на 16,5 циклов быстрее. Вы можете поиграть с длинами списка и другими факторами, а также изменить абсолютные тайминги, но дельта почти всегда составляет около 16-17 циклов, что не совпадает примерно с штрафом за неверное предсказание ветвлений в недавнем Intel! Решая условие ветвления на ранней стадии, мы избегаем появления внешнего пузыря, где вообще ничего не происходит.
Расчет количества итераций заблаговременно
Другим примером может быть что-то вроде цикла, который вычисляет значение с плавающей запятой, скажем, приближение ряда Тейлора, где условие завершения зависит от некоторой функции вычисленного значения. Это имеет тот же эффект, что и выше: условие завершения зависит от зависимости, переносимой по медленному циклу, поэтому его разрешение так же медленно, как и вычисление самого значения. Если выход непредсказуем, вы будете терпеть неудачу при выходе.
Если бы вы могли изменить это для вычисления счетчика итераций заранее, вы могли бы использовать разъединенный счетчик целых чисел в качестве условия завершения, избегая пузыря. Даже если предварительное вычисление добавляет некоторое время, оно все равно может обеспечить общее ускорение (и в любом случае вычисление может выполняться параллельно с первыми итерациями цикла, поэтому оно может оказаться намного менее затратным, чем вы ожидаете, если посмотреть при его задержке).
1 MIPS - интересное исключение, здесь нет регистров флагов - результаты теста сохраняются непосредственно в регистрах общего назначения.
2 Clang скомпилировал этот и многие другие варианты без ветвления, но это все еще интересно, потому что у вас все еще есть та же структура тестовой инструкции и условный ход (вместо ветки).
3 Как в C++11 std::list,
4 Как оказалось, на x86 работа для каждого узла на самом деле очень похожа между двумя подходами из-за способа, которым dec неявно установить нулевой флаг, поэтому нам не нужны дополнительные test инструкция, в то время как mov используемый в погоне за указателем не делает, поэтому у встречного подхода есть дополнительная dec в то время как у дозорного подхода есть дополнительный тест, заключающийся в мытье.
5 Хотя эта часть только потому, что gcc не удалось преобразовать увеличивающийся цикл for в убывающий цикл, чтобы воспользоваться dec установка нулевого флага, избегая cmp, Может быть, новые версии GCC лучше. Смотрите также сноску 4.
6 Полагаю, что это ближе к 0,9, чем к 1,0, поскольку, возможно, предикторы ветвления все еще получают правильный регистр длины = 10, так как после того, как вы зациклились 9 раз, следующая итерация всегда завершится. Менее синтетическое / точное распределение не продемонстрировало бы это.
7 Я говорю в основном потому, что в некоторых случаях вы можете сохранить цикл или два с помощью такого переупорядочения на уровне источника или сборки, потому что такие вещи могут незначительно повлиять на порядок выполнения в процессорах вне порядка, порядок выполнения также зависит от порядка сборки, но только в пределах ограничений графа потока данных. Смотрите также этот комментарий.
Основная проблема с неправильным предсказанием ветвлений заключается не в нескольких циклах, которые он получает в качестве штрафа при сбрасывании младших операций (что относительно быстро), а в том, что это может произойти очень поздно по конвейеру, если существуют зависимости данных, которые должно решить сначала условие ветвления.,
С ветвями, основанными на предыдущих вычислениях, зависимость работает так же, как и с другими операциями. Кроме того, ветвь проходит через предсказание очень рано вдоль канала, так что машина может продолжать извлекать и распределять дальнейшие операции. Если прогноз был неверным (что чаще всего случается с зависимыми от данных ветвями, в отличие от элементов управления циклами, которые обычно демонстрируют более предсказуемые шаблоны), то сброс будет происходить только тогда, когда зависимость будет разрешена и прогноз окажется неверным. Чем позже это произойдет, тем больше штраф.
Поскольку выполнение не по порядку планирует операции, как только зависимость разрешена (при условии отсутствия нагрузки на порт), продвижение операции вперед, вероятно, не поможет, поскольку это не изменит цепочку зависимостей и не повлияет на время планирования слишком сильно. Единственное потенциальное преимущество - если вы переместите его достаточно далеко вверх, чтобы окно OOO могло видеть его намного раньше, но современные процессоры обычно запускают сотни команд вперед, и поднять инструкции так далеко, не нарушая программу, сложно. Однако, если вы выполняете какой-то цикл, может быть просто вычислить условия будущих итераций, если это возможно.
Ничто из этого не изменит процесс прогнозирования, который является полностью ортогональным, но как только ветвь достигнет части ООО, относящейся к машине, она будет немедленно решена, очищена при необходимости и понесет минимальное наказание.