Замена условных переходов арифметическими операциями
Суперконвейерные процессоры, коими как раз и являются все старшие представители серии Intel 80x86, крайне болезненно относятся к ветвлениям. При нормальном ходе исполнения программы в то время, покуда обрабатывается текущий код, блок упреждающей выборки успевает считать и декодировать следующую партию инструкций, не допуская простоя шины памяти. Ветвления же отправляют всю эту работу насмарку, очищая конвейер. А конвейер у поздних моделей микропроцессоров Pentium очень длинный и быстро его не заполнишь – на это может уйти не один десяток тактов процессора, в течение которых вся "кухня" будет простаивать. Нехорошо! Программа, критичная к производительности, должна содержать минимум ветвлений.
Сказать-то просто, – трудно сделать. Как, скажем, избавиться от ветвлений в следующем примере: "if (a>b) a=b"? Непосредственно ликвидировать условный переход невозможно, попытка переписать код так: "a =((a>b)?b:a)" ничего не даст – оператор "?" с точки зрения компилятора – точно такой же условный переход, как и "if". Но вот спустившись на уровень ассемблера, мы можем кое-что предпринять (увы, в данном случае обращение к языку ассемблера – вынужденное, да пусть простят меня те, кто с ним не в ладах):
SUB b, a
; Отнять от содержимого 'b' значение 'a', записав результат в 'b'
; Если a > b, то процессор установит флаг заема в единицу
SBB c, c
; Отнять от содержимого 'c' значение 'c' с учетом флага заема,
; записав результат обратно в 'c' ('c' – временная переменная)
; Если a <= b, то флаг заема сброшен, и 'c' будет равно 0,
; Если a > b, то флаг заема установлен и 'c' будет равно –1.
AND c, b
; Выполнить битовую операцию (c & b), записав результат в 'c'
; Если a <= b, то флаг заема равен нулю, 'c' равно 0,
; значит, с =(c & b) == 0, в противном случае: c == b - a
;
ADD a, c
; Выполнить сложение содержимого 'a' со значением 'c', записав
; результат в 'a'.
; Если a <= b, то c = 0 и a = a
; Если a > b, то c = b - a, и a = a + (b-a) == b
Таким образом, данный код находит наименьшее из двух чисел, прекрасно обходясь без ветвлений. Аналогичным образом решаются и другие задачи. Специально для этой цели в старших процессорах серии Intel 80x86 был введен ряд команд, упрощающих программирование без условных переходов и уменьшающих количество математических преобразований.
К сожалению, ни один из трех рассматриваемых компиляторов не умеет избавляться от ветвлений и потому код, критичный к производительности, приходится вычищать от условных переходов вручную.
