Оптимизация: Дорогое ветвление против дешевого сравнения
Это отличная статья, в которой рассказывается о методах оптимизации низкого уровня и показывается пример, в котором автор преобразует дорогостоящие деления в дешевые сравнения.
https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920
Для тех, кто не хочет нажимать, по сути он конвертировал это:
uint32_t digits10(uint64_t v) {
uint32_t result = 0;
do {
++result;
v /= 10;
} while (v);
return result;
}
В это:
uint32_t digits10(uint64_t v) {
uint32_t result = 1;
for (;;) {
if (v < 10) return result;
if (v < 100) return result + 1;
if (v < 1000) return result + 2;
if (v < 10000) return result + 3;
// Skip ahead by 4 orders of magnitude
v /= 10000U;
result += 4;
}
}
В результате до 6 раз ускорить.
Хотя сравнение очень дешево, я всегда слышал, что ответвления очень дороги, потому что они могут привести к остановке конвейера. Из-за общепринятого подхода к ветвлению я бы никогда не подумал о таком подходе.
Почему ветвление не является узким местом в этом случае? Это потому, что мы возвращаемся сразу после каждого из сравнений? Это потому, что размер кода здесь невелик и, следовательно, процессор не может ошибиться в прогнозировании? В каких случаях это станет узким местом и начнет доминировать в стоимости подразделений? Автор никогда не говорит об этом.
Может ли кто-нибудь разрешить очевидное противоречие между дешевыми сравнениями и дорогими ветками? Конечно, золотое правило оптимизации заключается в том, что всегда нужно измерять. Однако, по крайней мере, было бы хорошо иметь некоторую интуицию по этому вопросу, чтобы можно было разумно использовать сравнения, пытаясь придумать новые подходы к ускорению кода.
Спасибо!
Решение
Филиалы не обязательно дороги — это действительно изолированных ошибочных дорогие отрасли1.
Итак, начнем с цикла. Это бесконечно, поэтому всегда берется. Так как он всегда берется, он также всегда прогнозируется как взятый, поэтому это дешево.
Только одна другая ветвь когда-либо берется для любого данного входа. То есть вы выполняете один тест за другим, и пока не достигнете того, который соответствует величине входного числа, все ветви не будут приняты (т.е. if условие будет ложным).
Предполагая (например) случайное сочетание входных чисел с максимум, скажем, 16 цифрами, мы в конечном итоге получаем примерно одну из четырех ветвей одну из четырех итераций цикла. Мы берем ветвь (в среднем) только около одного из 16 тестов, и приличный предсказатель ветвления, вероятно, будет предсказывать их все как не выполненные почти все время. В результате мы, вероятно, в конечном итоге один неправильно предсказанная ветвь во всем вычислении.
Как показывает практика, правильно предсказанная ветвь занимает около 1 часа, а неправильно предсказанная ветвь — около 20-30 часов. Таким образом, для 16-значного числа мы получаем 15 цифр + 4 итерации цикла = 19 правильно предсказанных ветвей + 1 неправильно предсказанная ветвь, что в сумме составляет примерно 39-49 тактов. Например, для двузначного числа у нас получается 1 + 20 = 21 час.
Очевидная альтернатива — делить на 10 и проверять остаток на каждой итерации. Деление является относительно дорогим — например, 64-разрядное деление может занять около 26-86 циклов на i7. Для простоты предположим, что в среднем 40. Итак, для 16-значного числа мы можем ожидать около 16 * 40 = ~ 640 часов только для делений. Даже в лучшем случае, давайте предположим, что двузначное число требует только 26 часов на деление, так что в итоге получается 52 такта.
Итог: даже в очень близком к лучшему для него случае деление все равно заканчивается медленнее, чем почти в худшем случае для сравнения. Большинство сравнений в конечном итоге предсказываются правильно, поэтому мы обычно получаем только одну дорогую (неправильно предсказанную) ветвь.
1. Это, конечно, предполагает современный, относительно высокопроизводительный процессор. На действительно старом процессоре (или низкоуровневом встроенном процессоре) у вас, вероятно, вообще нет предиктора ветвлений, поэтому все ветки имеют тенденцию быть довольно дорогими. В то же время, такой процессор может вообще не иметь команды деления, и если он есть, он, вероятно, довольно медленный. Короче говоря, и ветви, и деление занимают гораздо больше тактов, чем на современном процессоре, но ветвь обычно все же немного быстрее, чем деление.
Другие решения
первая реализация фактически разветвляется больше, даже если у нее есть только одна точка ветвления.
хотя, в порядке предпочтения в стиле кодирования, я бы использовал первую реализацию. Совокупность подобных веток вполне может работать лучше, но все же это больше кода, и похоже, что он был написан бездумно (на самом деле, почему он сохранил результат?). А что если я хочу больше пяти цифр? : |
Алгоритм в основном сравнения. Единственная явная ветвь — при возврате.
Преимущество заключается в том, чтобы избежать дорогостоящего деления на цифру, которое может занять более 100 тактов каждый. Можно привести случай, когда значение max uint64_t имеет 22 десятичных знака, и наиболее эффективным способом было бы развертывание цикла в 22 сравнения.