Это тот случай, когда сравнения подразумевают ответвление?
Я читал страницу википедии по оптимизации:
http://en.wikibooks.org/wiki/Optimizing_C%2B%2B/Code_optimization/Pipeline
и я наткнулся на линию:
Для конвейерных процессоров сравнения медленнее, чем различия, потому что они подразумевают ветвление.
Почему в этом случае сравнение подразумевает ответвление?
Например, если:
int i = 2;
int x = i<5;
В этом есть ветка? Для меня имеет смысл переходить для операторов if с условными выражениями, но я не понимаю, почему только сравнение приводит к переходу.
Решение
Преамбула: Современные компиляторы способны удалять ветки различными способами. Таким образом, ни один из примеров не обязательно приводит к переходу в конечном коде (ассемблер или машинный код).
Так почему логика в основном подразумевает ветви?
Код
bool check_interval_branch(int const i, int const min_i, int const max_i)
{
return min_i <= i && i <= max_i;
}
можно логически переписать так:
bool check_interval_branch(int const i, int const min_i, int const max_i)
{
if (min_i <= i)
{
if (i < max_i) return true;
}
return false;
}
Здесь у вас, очевидно, есть две ветви (вторая выполняется только в том случае, если первая верна — короткое замыкание), который может быть неверно предсказан предсказателем ветвления, что, в свою очередь, приводит к повторному выполнению конвейера.
Visual Studio 2013 (с включенной оптимизацией) генерирует следующую сборку, содержащую две ветви для check_interval_branch:
push ebp
mov ebp, esp
mov eax, DWORD PTR _i$[ebp]
cmp DWORD PTR _min_i$[ebp], eax // comparison
jg SHORT $LN3@check_inte // conditional jump
cmp eax, DWORD PTR _max_i$[ebp] // comparison
jg SHORT $LN3@check_inte // conditional jump
mov al, 1
pop ebp
ret 0
$LN3@check_inte:
xor al, al
pop ebp
ret 0
Код
bool check_interval_diff(int const i, int const min_i, int const max_i)
{
return unsigned(i - min_i) <= unsigned(max_i - min_i);
}
логически идентичен
bool check_interval_diff(int const i, int const min_i, int const max_i)
{
if (unsigned(i – min_i) <= unsigned(max_i – min_i)) { return true; }
return false;
}
которая содержит только одну ветвь, но выполняет две разницы.
Сгенерированный код для check_interval_diff Visual Studio 2013 даже не содержит условного перехода.
push ebp
mov ebp, esp
mov edx, DWORD PTR _i$[ebp]
mov eax, DWORD PTR _max_i$[ebp]
sub eax, DWORD PTR _min_i$[ebp]
sub edx, DWORD PTR _min_i$[ebp]
cmp eax, edx // comparison
sbb eax, eax
inc eax
pop ebp
ret 0
(Хитрость в том, что вычитание сделано sbb отличается на 1 в соответствии с флагом переноса, который в свою очередь устанавливается на 1 или 0 cmp инструкция).
На самом деле вы видите три различия здесь (2x sub, 1x sbb).
Вероятно, это зависит от ваших данных / варианта использования, который быстрее.
Увидеть Мистики отвечают здесь о отраслевом прогнозе.
Ваш код int x = i<5; логически идентичен
int x = false;
if (i < 5)
{
x = true;
}
который снова содержит ветку (x = true выполняется только если i < 5.)
Другие решения
Это включает только одну ветку:
unsigned(i – min_i) <= unsigned(max_i – min_i)
Хотя это включает в себя два:
min_i <= i && i <= max_i
Когда ЦП встречает ветвь, он обращается к своему предиктору и следует по наиболее вероятному пути. Если прогноз верен, ветвь в основном свободна с точки зрения производительности. Если прогноз неверен, процессор должен очистить конвейер и начать все сначала.
Этот вид оптимизации является обоюдоострым мечом — если ваши ветви очень предсказуемы, то первая может работать медленнее, чем вторая. Это полностью зависит от того, сколько вы знаете о ваших данных.
Несмотря на то, что приведенные здесь ответы являются хорошими, не все сравнения преобразуются в инструкции ветвления (они вводят зависимости данных, которые могут также снизить производительность).
Например, следующий код C
int main()
{
volatile int i;
int x = i<5;
return x;
}
Компилируется gcc (x86-64, оптимизация включена) в:
movl -4(%rbp), %eax
cmpl $5, %eax
setl %al
movzbl %al, %eax
setl инструкция устанавливает значение AL согласно результату предшествующей инструкции сравнения.
Конечно, это очень простой пример — и cmp/setl комбинация, вероятно, вводит зависимости, которые мешают процессору выполнять их параллельно или могут даже стоить вам нескольких циклов.
Тем не менее, на современном процессоре не все сравнения превращаются в инструкции ветвления.
Кто когда-либо писал эту страницу, не компетентен как программист. Первый,
сравнения не обязательно подразумевать ветку; это зависит от того, что вы
делать с ними. И подразумевает ли это ветвь или нет, зависит от
процессор и компилятор. if как правило требует ветки, но
даже тогда хороший оптимизатор иногда может этого избежать. while или
for как правило, потребуется ветвь, если компилятор не может раскрутить
цикл, но эта ветвь очень предсказуема, так что даже когда ветвь
прогноз — это проблема, это может не иметь значения.
В целом, если вы беспокоитесь о чем-либо на этом уровне при написании
ваш код, вы тратите свое время и делаете обслуживание гораздо больше
сложно. Единственный раз, когда вы должны быть обеспокоены, когда у вас есть
проблема с производительностью, и профилировщик показывает, что это место, где
Вы теряете производительность. В этот момент вы можете поэкспериментировать с
несколько разных способов написания кода, чтобы определить, какой из них будет
привести к более быстрому коду для вашей комбинации компилятора и оборудования.
(Измените компилятор или аппаратное обеспечение, и оно может не совпадать.)