К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 82
Текст из файла (страница 82)
Оптимизация арифметических операций Сложение и вычитание Старшие модели микропроцессоров !пге! Репбшп могут выполнять до двух операций целочисленного сложения (вычитания) за каждый такт, — казалось бы, все и так оптимизировано до прелела, но оказывается, что это далеко не предел! Инструкция ькл способна вычислять за один такт сумму двух регистров и одной константы, помешая результат в любой регистр, а необязательно в один из операндов, как это делает команла лес. Использование инструкции ьвл позволяет выполнить следующий кол Ыхб с=атьтсхббб; хат О=-е+Г+Ох777~ ВСЕГО За Один Такт! (КОНЕЧНО, При уСЛО- вии, что з, ь, о, а, а и г — регистровые переменные.) Весь фокус в том, что "официально" инструкция ьвх предназначена для вычисления эффективного смешения ячейки памяти и по логике применима только к ближним (пеаг) указателям. Но поскольку в силу архитектурных особенностей микропропессоров серии 1пге! х8б представление ближних указателей эквивалентно их фактическому значению, результат, возвращенный инструкцией ьвл, равен алгебраической сумме ее операнлов, и потому она может быть использована вместо лес! Все три рассматриваемых компилятора — М!сгоьой Хт!бва! С++, Вог!апг! С++ и %АТСОМ "знают" об этом трюке и активно прибегают к нему при необходи мости.
Деление Целочисленное леление — очень "лорогостояшая" операция, даже на старших молелях процессоров !пге! Репгьвпз занимающая до сорока и более тактов. Кошмар! К счастью, процесс деления подлается оптимизации. Если делитель кратен степени двойки, то инструкцию деления можно заменить более быстродействующей инструкцией битового слвига, выполняющейся всего за один такт. А что делать, если делитель отличен от степени двойки (как чаше всего и бывает)".
Тогда имеет смысл заменить деление умножением — ведь операция умножения выполняется намного быстрее, в среднем укладываясь в четыре такта, что на порядок шустрее! Существует множество формул полобных преобразований, вот, например, олна (самая а 2 „а популярная из них): — = — * —, где )х! — разрядность числа. Если дели- Ь Ь 2н тель — константа, то операция деления выполняется всего за алть тактов— два в степени 1ч — константное выражение, вычисляемое на этапе компи- Глава 4 420 а ляции, выражение —, вычисляется битовым сдвигом за один такт, еще че2н тыре такта расходуется на умножение, итого, в сумме выходит пять. К сожалению, компиляторы Вот!ап<! С++ и Ч~АТСОМ не настолько "умны", чтобы заменять деление умножением — на это способен один лишь Мьсгозой Н!зиа! С++, за что честь ему и хвала! Битовые же сдвиги используют все три рассматриваемых компилятора.
Взятие остатка Вычисление остатка происходит ничуть не быстрее деления (что и не удивительно, т. к. на машинном уровне оно посредством деления и осуществляется), поэтому было бы неплохо ускорить этот процесс. Если делитель представляет собой степень двойки 2<я = Ь, а делимое — беззнаковое число, то остаток будет равен Х младшим битам делимого числа. Если же делимое — знаковое число, то необходимо установить все бить<, кроме первых Х, равными знаковому биту для сохранения знака числа.
Причем, если )х) первых битов равно нулю, то все биты результата должны быть сброшены независимо от значения знакового бита. Таким образом, если делимое — беззнаковое число, то выражение (а % 2)х)) транслируется в конструкцию: (А)Ч0 а, 1ч), в противном случае трансляция становится неоднозначна — компилятор может вставлять явную проверку на равенство нулю с ветвлением, а может использовать хитрые математические алгоритмы, самый популярный из которых выглядит так: свс «х оа «, <ях <ис Весь фокус состоит в том, что если первые Х бит числа х равны нулю, то все биты результата кроме старшего, знакового бита, булут гарантированно равны одному, а <оа «, — ю принудительно установит в единицу и старший бит, т.
е. получится значение, равное — 1. А ывс -ы даст ноль! Напротив, если хотя бы один из )ч младших битов равен единице, то заема из старших битов не происходит и <гвс «< возвращает значению первоначальный результат. А можно ли вычислять остаток посредством умножения и битовых сдвигов? Теоретически возможно, но не для всех делителей. Делитель обязательно должен быть кратен )< *2', где )< и ! — некоторые целые числа.
Тогда остаток будет можно вычислить по следующей формуле: (<2н, а 1 а% Ь = а% )< '2' = а — — * — 8г — 2' *)<. 2 ) К сожалению, ни один из трех рассматриваемых компиляторов не использует этот трюк для оптимизации кода, но выполнять быстрый поиск остатка 42! Машинная оптимизация для делителей, кратных степени двойки, умеет каждый из них (невелика премудрость). Умножение Вообще-то, умножение — достаточно быстрая операция и особой необходимости в ее оптимизации нет. Но, как говорится, копейка рубль бережет.
Вот компиляторы и борются за каждый такт времени процессора! Если один из сомножителей представляет собой степень двойки, то в ход идут битовые сдвиги. Это очевидно, но не все знают: как быстро выполнить умножение на числа 3, 5, б, 7, 9, 1О и т. д. Оказывается, в этих случаях на помощь приходит сложение — в самом деле, выражение а*3 можно записать как: (а>>1)+а, что с легкостью укладывается в один такт (инструкция 1 ЕА может не только складывать, но и умножать один из регистров на числа 2, 4 и 8). Компиляторы М(сгозо(1 'т(вца( С++ и Вот(апг( С++ умело заменяют умножение битовыми сдвигами, при необходимости комбинируя их с операцией сложения, а вот %АТСОМ предпочитает обходиться без инструкции ьвп, проигрывая своим конкурентам один такт (точнее, с учетом спаривания машинных команд, т.
е. выполнения параллельно с другой командой, даже полтора такта). Оптимизация ветвлений Замена условных переходов арифметическими операциями Суперконвейерные процессоры, коими как раз и являются все старшие представители серии 1пге( х86, крайне болезненно относятся к ветвлениям. При нормальном ходе исполнения программы в то время, пока обрабатывается текущий код, блок упреждающей выборки успевает считать и декодировать следующую партию инструкций, не допуская простоя шины памяти.
Ветвления же отправляют всю эту работу насмарку, очищая конвейер. А конвейер у поздних моделей микропроцессоров Репйшп очень длинный и быстро его не заполнишь — на это может уйти не один десяток тактов процессора, в течение которых вся "кухня" будет простаивать. Нехорошо! Программа, критичная к производительности, должна содержать минимум ветвлений.
Сказать-то просто — трудно сделать. Как, скажем, избавиться от ветвлений в следующем примере: г ~з>ь~ з-ь? Непосредственно ликвидировать условный переход невозможно, попытка переписать код так: з =! ~з>ы ть:з! ничего не даст — оператор т с точки зрения компилятора— точно такой же условный переход, как и г.
Но вот спустившись на уровень ассемблера, мы можем кое-что предпринять (увы, в данном случае 4гг Глава 4 обращение к языку ассемблера — вынужденное, да пусть простят меня те, кто с ним не в ладах): ЭОВЬ, а Отнять от содеряимого 'Ь' значение 'а', записав результат в 'Ь' Если а > Ь, то процессор установит флаг заема в единицу ЭВВ с, с Отнять от содержимого 'с' значение 'с' с учетом флага заема, записав результат обратно в 'с' ('с' — временная переменная) Если а <= Ь, то флаг заема сброшен, и 'с' будет равно О, Если а > Ь, то флаг заема установлен и 'с' будет равно -1. лясс, Ь Выполнить битовую операцию (с ь Ь), загисав результат в 'с' Если а <= Ь, то флаг заема равен нулю, 'с' равно О, значлт, с =(с 6 Ы == О, в противном случае: с == Ь вЂ” а Песа, с Выполнить сложение содержимого 'а' со значением 'с', записав результат в 'а'.
Если а <= Ь, то с = О и а = а Если а > Ь, то с = Ь - а, и а = а (Ь а) == Ь Таким образом, данный код находит наименьшее из двух чисел, прекрасно обходясь без ветвлений. Аналогичным образом решаются и другие задачи. Специально для этой цели в старших процессорах серии 1пге1 х86 был введен ряд команд, упрощающих программирование без условных переходов и уменьшающих количество математических преобразований. К сожалению, ни один из трех рассматриваемых компиляторов не умеет избавляться от ветвлений и потому код, критичный к производительности, приходится вычищать от условных переходов вручную. Удаление лишних условий Упрощение логических условий чем-то сродни алгебраическим упрощениям.
Рассмотрим следующий пример: ьг (а>О ьа а<Ох666 66 а!=О) Очевидно, что проверка а)=О лишняя — т. к. если переменная а больше нуля, оно заведомо не равно нулю! Компилятор М!Огозо)! У!Еца! С++ умеет распознавать такие ситуации, избавляясь от избыточных проверок, а вот Вог!ап(! С++ и %АТСОМ на это не способны. Машинная оптимизация 423 Удаление заведомо ложных условий Иногда программисты допускают ошибки, создавая заведомо ложные условия, как, например, это: Гб )а)=О аа ==О) Ясно, что если переменная а не равна нулю, то равна нулю она быть никак не может, — вот компилятор М)сгоьой Ъ(ьпа! С++ и не генерирует для него код, опуская всю ветку г-тнся, правда, почему-то не выдавая никаких предупреждений.
А зря! Ведь ясно, что это — программистская ошибка. Компиляторы же Вот(апй С++ и %АТСОМ вообше не оптимизируют такой код, понимая его буквально, т. е. как есть. Впрочем, и Мгсгозой %ьаа! С++ не всегда распознает заведомую ложность условий. В частности, со следуюшим примером он уже не справляется: ае )а<О вв а>Овббб) Оптимизация зи(йсй Балансировка логического древа Оператор мнОжественного выбОра вегасе Очень пОпулярен среди программистов (особенно разработчиков %(пйо)чб-приложений). Число его ветвей может быть очень велико и их линейная обработка крайне непроизводительна. В некоторых (хотя и редких) случаях операторы множественного выбора содержат сотни (а то и тысячи) наборов значений, и если решать задачу сравнения "в лоб", то "высота" логического дерева окажется гигантской до неприличия, а его прохождение займет весьма длительное время, что не лучшим образом скажется на производительности программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
