К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 83
Текст из файла (страница 83)
Но, задумайтесь; чем собственно занимается оператор ась? Если отвлечься от устоявшейся идиомы "оператор бнттсн дает специальный способ выбора одного из многих вариантов, который заключается в проверке совпадения значения данного выражения с одной из заданных констант в соответствующем ветвлении", то можно сказать, что в тась — это оператор поиска соответствуюшего значения. В таком случае линейное ссь-дерево представляет сО- бой тривиальный алгоритм последовательного поиска — самый неэффективный алгоритм из всех.
Пусть, например, исходный текст программы выглядел так; вет бса )а) саве 99 саве 4 саве 3 Глава 4 Тогда соответствующее ему неоптимизированное логическое дерево будет достигать в "высоту" одиннадцати гнезд (рис. 4.1, слева). Причем, на левой ветке корневого гнезда окажется аж десять других гнезд, а на правой — во- обще ни одного (только соответствующий ему сабе-обработчик). а> == 0 зв г а г а==3 а==в Рис.
4.1. Логичвсков дврвво до утрамбовки [слава) и посла (справа) Исправить "перекос" можно разрезав одну ветку на две и "привив" образовавшиеся половинки к новому гнезду, содержащему условие„определяющее: в какой из веток следует искать сравниваемую переменную. Например, левая ветка может содержать гнезда с четными значениями, а правая — с нечетными. Но это плохой критерий; четных и нечетных значений редко бывает поровну и вновь образуется перекос. Гораздо надежнее поступить так: берем наименьшее из всех значений и бросаем его в кучу л, затем берем наибольшее из всех значений и бросаем его в кучу в.
Так повторяем до тех пор, пока не рассортируем все имеющиеся значения. саяе 9 саве 22 саве О саве ы саве ббб: саяе 09б: саяе 777: саяе 7 а== / 'Ъ ~~ 'Ъ а==7 а==96 а==~8 а==22 а==666 ~у "Ъ Машинная оптимизация 425 Поскольку оператор множественного выбора требует уникальности каждого значения, т. е. каждое число может встречаться в наборе (диапазоне) значений лишь однажды, легко показать, что: а) в обеих кучах будет содержаться равное количество чисел (в худшем случае — в одной куче окажется на число больше); б) все числа кучи л меньше наименьшего из чисел кучи в. Следовательно, достаточно выполнить только одно сравнение, чтобы определить: в какой из двух куч следует искать сравниваемое значение.
( (я( + 1 Высота нового дерева будет равна е!, где )Ч вЂ” количество гнезд 2 старого дерева. Действительно, мы же делим ветвь дерева надвое и добавля- 1~1 ем новое гнездо — отсюда и берется — и +1, а ()Я)+ !) необходимо для округ- 2 ления результата деления в большую сторону. Таким образом, если высота неоптимизированного дерева достигала 100 гнезд, то теперь она уменьшилась до 5!. Что? Говорите, 51 все равно много? А что нам мешает разбить каждую из двух ветвей еше на две? Это уменьшит высоту дерева до 27 гнезд! Аналогично, последующее уплотнение даст 16-з !2-з 11 з 9 -~ 8 и все! Более плотная упаковка дерева невозможна (подумайте почему — на худой конец постройте само дерево). Но, согласитесь, восемь гнезд — это же не сто! Полное прохождение оптимизированного дерева потребует менее девяти сравнений! Из всех трех рассматриваемых компиляторов "трамбовать" операторы яеь не умеет один лишь %АТСОМ, а Н15ца! С++ и Вот!ада С++ вполне справляются с этой задачей.
Создание таблицы переходов Если значения ветвей выбора представляют собой арифметическую прогрессию, то можно сформировать таблицу переходов — массив, проиндексированный сазе-значениями и содержащий указатели на соответствующие им саве-обработчики. В этом случае, сколько бы оператор л ни содержал ветвей — олин или миллион, — он выполняется за одну итерацию. Красота! Создавать таблицы переходов умеют все три рассматриваемых компилятора, и следующий пример успешно оптимизирует каждый из них. яеьясЬ !а) саяе 1 саяе 2 саве 3 саве я саяе 5 саяе б Глава 4 426 сазе 7 саяе 9 сазе 9 сазе 10 саяе 11 Однако яЧАТСОМ плохо справляется с переупорядоченной прогрессией и совсем не справляется с несколькими независимыми прогрессиями. Компиляторы М)сгозой Ч)зпа! С++ и Вог(ап() С++ успешно оптимизируют следующий пример, а ЧЧАТСОМ создаст обычное несбалансированное логическое дерево, в худшем случае выполняющееся за одиннадцать итераций, что нв порядок хуже, чем у конкурентов.
яеввса (а) саяе 11 сазе 2 саяе 13 саяе Л саяе 15 сазе 6 саяе 17 саве 8 саяе 19 саяе 10 саве 21 Оптимизация циклов Разворачивание циклов Поскольку в основе циклов лежат ветвления, а ветвления, как уже было по- КаэаНО В раэд. сОнтилииэоция ВЕтВЛЕНий'" Этюй гЛаВЫ, КрайНЕ НЕГатИВНО СКазываются на производительности, — от них прелпочтительнее избавиться, пускай даже ценой увеличения размера программы, Короткие, в три-пять итераций, циклы выгоднее разворачивать в линейный код, повторяя тело цикла заданное число раз.
Рассмотрим следующий пример: Еся(а=с;а<3)аяе) ря1аСГ("Захе", а)) Машинная оптимизация аг~ Чтобы избавиться от ветвлений, его следует переписать так: рохп<1 ( "%храп'Ь 0) ) р<1пе1 (*'тх1п", 1) ) р хпье("Ъх1п'Ьэ); Впрочем, не факт, что этот трюк увеличит производительность — вель "разбухание" кода программы может привести к тому, что она перестанет вмешаться в свободну)о оперативную память компьютера и операционная система булет вынужлена использовать очень медленный жесткий диск. Аналогично — кэш первого уровня не безразмерен и развернутый цикл может в него и не "влезть".
Наконец, микропроцессоры 1п(е! Реп(шш Р!а(п и ММХ спаривают инструкции, начиная лишь со второго прохода, и "развертка" цикла практически вдвое уменьшает скорость выполнения кода! Поэтому полобрать наиболее оптимальную стратегию в каждом конкретном случае может лишь эксперимент. А эксперимент — прерогатива разработчика и ни один из трех рассматриваемых компиляторов развертку циклов не выполняет. Слияние циклов Если два цикла имеют идентичные заголовки, их можно объединить в один обший цию).
Например, пусть исходный код программы выглядел так: Еоо(Ь = О) Ь < 10; Ь++) х(Ы = ь) еох(Ь = О) Ь < 10; Ь +) у(ь) = ьн Очевидно, что данный код можно без потери функциональности переписать так, тем самым увеличив производительность и компактность программы: топ(Ь = 01 Ь < 10; Ь-+) х(ь) = ь) уго) = )и К сожалению, ни один из трех рассматриваемых компиляторов сливать циклы не способен. Глава 4 428 Вынесение инвариантного кода за пределы цикла Инвприпнтныл( называется код, не изменяющийся в ходе выполнения цикла.
А раз так, — то какой смысл выполнять его в каждой итерации — не лучше ли вынести такой код за пределы цикла? Рассмотрим следу(оший пример: го<(а=.О:а<(Ь*2))аа~) р< аае("ахзо",а*(Ь/2)); Выражения (ь.а) и (ьл2) очевилно представляют собой инвариант, и опти- мизированный код будет выглядеть так: Ьар )=Ь 2) о~ар 2=ЬЛ2) еох(а=О)а<нар 1;а а) реаоье("Вхзо",Ьач~ 2а (оюр 2)) Это экономит одну операцию деления и две операции умножения на каждую итерацию, что очень и очень не плохо! Компиляторы М)сгогюй Чапа! С++ и %АТСОМ успешно распознают инвариантный код и выносят его за пределы цикла, а вот Вонапд С++ увы, нет.
Замена циклов с предусловием на циклы с постусловием Существуют три основных типа цикла: циклы с условием вначале (рис. 4.2, слева), циклы с условцел( в конце (см. рис. 4.2, в центре) и циклы с условием а середине (см. рис. 4.2, справа). Комбинированные циклы имеют нескодько условий в разных местах, например, в начале и в конце одновременно. Как видно, цикл с постусловием содержит всего одно ветвление, в то время как все его "собратья" — два! Все три рассматриваемых компилятора всегда заменяют циклы с предусловием на циклы с постусловием. Понятное дело — такая замена не может быть осуществлена без коррекции тела цикла, что представляет собой отнюдь нетривиальную задачу.
Но, к сожалению, рамки данной книги слишком тесны для описания этой технологии и здесь ничего не остается, как только отослать заинтересованных читателей к книге Криса Касперски "Фундаментальные основы хакерства. Искусство дизассемблирования".— Мл Изд-во "Солон-Р", 2002, в которой вопрос трансляции циклов изложен во всех подробностях. 4гв Машинная оптимизация начало цикла начало цикла начало цикла опа опе опе опе переход конец цикла конец цикла конец цикла Рис. 4.2. Логическое дерево цикла с условием вначале (слева) и условием в конец (справа) Замена инкремента цикла на декремент Поскольку машинные инструкции декремента (уменьшения значения переменной) автоматически "выбрасывают" флаг при достижении нуля, таким образом, сравнивать уменьшаемую переменную с нулем не требуется— ЭтО аатОМатИЧЕСКИ дЕЛаЕт СаМ ПрОцЕССОр.
ОтСЮда: ЦИКЛ Гсг (е=)0;е>0)е--) транслируется в более компактный и быстродействуюший код, нежели цикл Гог (а=О)а<10)аее). Если аргумент цикла не используется в самом цикле, то компилятор М)сгоаой ')Г(ьца! С++ всегда транслирует его в цикл с декрементом. Например, пусть исходный кол программы выглядел так: Гог(а=О)а<10)ее+) рггпГЙ("Не11о, Ба11ог)хп")) Поскольку переменная е не используется в теле цикла, заголовок цикла можно безболезненно переписать следуюшим образом: Гег(а=10;а>0)е †) Из всех трех рассматриваемых компиляторов на такой трюк способен один лишь М(сгохой '))(хца! С++, — ни Вог)апг) С++, ни %АТСОМ этого делать не умеют.
4ЗО Глава 4 Удаление ветвлений Ветвления внутри циклов всегда нежелательны, а на старших моделях микропроцессоров 1п1е! — особенно (кстати, большинство С-компиляторов платформы СО!х)ЧЕХ вообще отказываются компилировать программы с ветвлениями внутри циклов). Уникальной особенностью компилятора М)сгозой Чвпа! С++ является его умение избавляться от некоторых типов внутрицикловых ветвлений. Алгоритм подобной оптимизации слишком сложен, чтобы быть описанным в рамках данного раздела, поэтому просто рассмотрим пример кода до и после оптимизации, а любопытных отошлем к уже упомянутой книге Криса Касперски "Фундаментальные основы хакерства. Искусство дизассемблирования".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
