ТЕХНИКА ОПТИМИЗАЦИИ ПРОГРАММ

       

Замена условных переходов арифметическими операциями


Суперконвейерные процессоры, коими как раз и являются все старшие представители серии 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 был введен ряд команд, упрощающих программирование без условных переходов и уменьшающих количество математических преобразований.

К сожалению, ни один из трех рассматриваемых компиляторов не умеет избавляться от ветвлений и потому код, критичный к производительности, приходится вычищать от условных переходов вручную.



Содержание раздела