В статье рассматриваются приемы оптимизации программ на примере оптимизирующих возможностей компилятора командной строки Borland C++ 5.3 for Win32 (bcc32.exe).

Хороший кодировщик ассемблера может создавать более эффективные программы, чем компилятор, при наличии достаточного времени. Это в первую очередь относится к расчетным задачам, а не к программированию интерфейса пользователя. Сейчас как раз наблюдается его нехватка. Отрасль информационных технологий, пожалуй, как ни одна другая развивается наиболее динамично, требуя все новых и новых программ. Поэтому такая операция, как оптимизация, перекладывается на "плечи" компилятора.

Первый проход процесса компиляции - лексический анализ. Многие языки допускают избыточность, комментарии, пробелы. После него остаются только те символы и литеры, которые необходимы для последующей компиляции. Второй проход - синтаксический анализ и интерпретация. Отдельные предложения программы разбиваются на более простые части. Синтаксический анализатор проверяет, является ли программа грамматически правильной, т.е. удовлетворяет ли она законам данного языка. Структура программы преобразуется во внутреннее представление (дерево, матрица, польская запись), с которой впоследствие могут работать оптимизирующая и вырабатывающая объектный код части компилятора. Оптимизация может быть направлена на сокращение времени работы (быстродействие) или размера программы. Оптимизация размера не так актуальна, как несколько лет назад. Большинство прикладных программ используют "защищенный режим" работы процессора, где не сказываются ограничение в 640 Кб, да и современные модули памяти - одна из недорогих составляющих компьютера. Программа должна быть быстрой. Оптимизация не улучшит плохо спроектированный алгоритм, но ускорить отдельные модули она способна. Для проверки оптимизирующих возможностей компилятора использовался bcc32.exe из поставки C++ Builder3.0, это компилятор командной строки, удобный для получения объектных модулей (*.obj) и ассемблерных листингов, поддерживающий практически все типы задач для платформы Win32.

Методы оптимизации

Существуют различные методы машинно-зависимой и машинно-независимой оптимизации кода. Одним из простейших методов является "размножение констант". При его применении любая ссылка на константное значение заменяется самим значением. Рассмотрим фрагмент Си программы, приведенной на рисунке. Переменная i2 лишняя. Ее значение не изменяется и используется лишь в функции printf. Ее можно заменить на i1. Скомпилируем этот код в двух вариантах: с оптимизацией и без.

В оптимизированном коде компилятор использовал только два регистра для хранения переменных ecx для i3 edx для i2, тем самым заменив все вхождения i1 на i2. Регистр eax используется для вспомогательных целей. В него пересылается единица, строка 20, для инициализации edx, затем он же, после сравнения 40, используется как переменная big. Неоптимизированный код гораздо больше по своему размеру. Вместо быстрых пересылок регистр - регистр используются более медленные: регистр - память, т.к. для хранения переменных используется стек. Компилятор воспользовался принципом "как слышится, так и пишется", т.е. синтаксис Си буквально оператор за оператором переводится в ассемблерный код. Строка 10, переменная i1 инициализирована единицей, 20-30 - значение i2 приравнивается к i1, 40-50 - подготовка к команде сравнения 60. Затем присваивание переменной big наибольшего значения 80-90, если i1>i3, 110-120 - наоборот. Параметры для функции printf передаются через стек в обратном порядке, сначала - big, затем - i2.

Логические и математические выражения

Логические выражения можно оптимизировать, изменяя порядок следования в них операндов. Если A и B - булевы выражения и A чаще принимает значения "истинно", то if(A || B) выполнится быстрее, чем if(B || A). Процессор прекратит вычисление составного условного оператора, если результат уже ясен. Для математики в первую очередь важна скорость процессора и некоторые тонкости при составлении вычислений, их можно найти в любом учебнике по численным методам. Но некоторые вещи хороший компилятор должен оптимизировать сам.

В среднем операция присваивания выполняется быстрее, чем сложение или вычитание. В свою очередь сложение и вычитание осуществляются быстрее, чем умножение и деление.

Квадрат суммы будет быстрее вычисляться по формуле c = (a+b)², а не по c = (a²+ab+ab+b²). Но современным компиляторам пока еще не "по зубам" формулы сокращенного умножения, Borland C++ не распознал эту операцию, строка 110, и сгенерировал обычный набор операций. Он смог только заменить выражение 2*i1*i2 более быстрым (i1+i2)*2. Выражение в строке 30 Си листинга должно вычисляться на стадии компиляции, а не во время выполнения программы. Компилятор правильно выполнил эту операцию, преобразовал выражение в константу 33 строка 10. Выражение i1*2 можно заменить более быстрым сложением, что компилятор и сделал, сгенерировав инструкцию add eax,eax. Для Си строк 50-90 вычисления не нужны, это обычное присваивание (60, 90) или бессмысленные в рамках алгебры математические выражения. Компилятор сгенерировал код. Это характеризует его далеко не с лучшей стороны. Выражение i1+0 должно быть пропущено, компилятор поместил инструкцию add ebx,0 строка 50. i1*0 - вот тут все в порядке, сначала обнуление регистра 60, затем занесение в переменную, регистр ebx, нуля. i1*1 - можно безболезненно пропустить и не генерировать код, у компилятора получились инструкции 80-90. Команда деления на единицу (Си код 80) вызвала целый поток инструкций 100-140. Это может быть справедливо только для чисел с плавающей запятой, где 1.0 может иметь очень небольшую погрешность, и инструкция деления idiv правомерна. i1-i1 - обнуление переменной, компилятор интерпретировал ее как вычитание, поставив команду sub строка 150, хотя более выгодна команда обнуления xor ebx,ebx.

Группировка подвыражений

Устранение общих подвыражений, появляющихся в одном или соседних операторах.

Предположим, что задан следующий условный оператор if(((i+j)<0) || ((i+j)>10)). В выражении (i+j) можно вынести за условие if-else, вычислить и использовать в нем конкретное значение. Компилятор так и поступает: в строке 30 он находит сумму (i+j), результат сохраняется в eax. Затем в 40 выполняется логическое И., т.е. проверка меньше ли eax нуля, если да - печать. Аналогично для второго условия > 10. Выражение не вычисляется вновь, а используется уже найденная сумма, хранящаяся в eax.

Удаление недостижимого кода

Часто в больших программных проектах накапливается много так называемого "мертвого кода". Мертвый код - это некоторая последовательность инструкций программы, которая недостижима ни по одному пути. Это могут быть команды препроцессора 20-40, операторы, попавшие в безусловный переход 50-70, или, на первый взгляд, логичные, но все же не выполняющиеся условия 80-130. Компилятор должен пропускать такие блоки, не генерируя машинных инструкций. К сожалению, bcc32 смог справиться только с условной компиляцией. В случае функции printf он сгенерировал набор инструкций и поместил перед ними команду jmp на следующий фрагмент, хотя и предупредил о нахождении в программе недостижимого кода (Unreachable code in function main). Сгенерировал он код и для switch-case, несмотря на то, что он недостижим. В такой конструкции достаточно сложно определить заранее, будет ли она выполняться. Всплывает проблема жизни переменной i. Возможно, что где-то эта переменная изменяет свое значение, и управление снова перейдет к выражению switch-case. Хотя в данном случае она помещена в ограничивающий блок и больше не вызывается.

Исключение пустых ("мертвых") переменных, объявленных, но никогда не используемых, - не такая простая задача, как кажется на первый взгляд. Переменная определяет участок памяти, и на этот участок можно ссылаться через указатель. Переменная уже не нужна - самое время ее удалить, но может существовать ссылка, указывающая на нее и используемая в дальнейшем. При удалении переменной память освобождается и может быть выделена для другой переменной. Обратившись к этой области через оставшийся указатель, получим совсем другое значение.

Совместные циклы

Цикл - это повторение какой-либо операции или группы операций определенное количество раз. Если циклы следуют друг за другом, их необязательно выполнять последовательно, гораздо эффективнее внести вторую группу операторов в первый цикл. Для совмещения циклов требуется процедурная оптимизация, т.е. код в циклах может быть достаточно объемным и компилятор не сможет корректно его слить. Простой пример: заменим операции инкремента и декремента в строках 30 и 50 на вызовы функции printf ("Hello") и printf ("world"). При слиянии циклов логика программы нарушится, вместо печати "Hello Hello...", будут выводиться фразы "Hello world". Как видно из ассемблерного листинга, BCC32 не смог объединить эти циклы. Первый цикл for - строки 20-50, второй 70-100.

Развертывание циклов

Непосредственно со слиянием связано раскрытие циклов: это увеличение числа операций, выполняемых за одну итерацию. Если цикл с управляющей переменной выполняется 1000 раз, столько же раз повторяется не только выполнение операций из тела цикла, но и наращивание управляющей переменной и проверка условий завершения. Число итераций можно существенно уменьшить, если воспользоваться "методом развертывания цикла". Он заключается в том, что один и тот же оператор, стоящий в теле цикла, записывается для нескольких различных значений управляющей переменной, и, таким образом, число итераций удается сократить в несколько раз. Возьмем следующий цикл: for(int i=0;i<1000;i++) a[i]=0; В нем неявно присутствует 1000 операций инкремента и проверок условия i<1000. Этот цикл можно развернуть в следующий: for(int i=0;i<500;i+=2) {a[i]=0; a[i+1]=0;}. Если тело цикла должно повторяться небольшое количество раз, более эффективно полностью развернуть цикл, т.е. записать непосредственно все выполняемые операторы.

Оптимизация переходов

Безусловные переходы - довольно редкая вещь в программе, но, на мой взгляд, не стоит их бояться. Некоторые программисты считают, что структурированная программа и даже язык программирования (но все же не система команд машины) не должны содержать операторов перехода, подобных goto. В этом случае вся программа будет состоять из операторов присваивания, обращения к процедурам, самих процедур, выбора одного из двух или нескольких вариантов и операторов циклического повторения до достижения определенного условия. Мне кажется это не совсем верным. Да, излишние операторы перехода служат указателем на неряшливость или низкую квалификацию программиста и затрудняют проверку. Тем не менее, насильственный отказ от goto часто отдаляет программу от естественного алгоритма решения задачи. В приведенном примере при условии x>y правильнее совершить переход не на L1 строка 50, а сразу на L2 - 70. При компиляции этого выражения компилятор так и поступил, поставив команду jb short L2 после команды сравнения.

"Машина должна работать, а человек - думать!"

Перед изменением текста программы не помешает убедиться, что эти изменения действительно необходимы. Иногда достаточно просто заменить компилятор. Оптимизацию обычно применяют, если время выполнения, объем используемой оперативной памяти, загруженность процессора, время реакции на пользовательский ввод оказываются слишком большими. При написании программы необходим компромисс между временем, памятью и ясностью представления. Нельзя жертвовать ясностью программы для того, чтобы сэкономить несколько секунд на выполнение. И если есть возможность перепоручить оптимизацию программы компилятору, лучше это сделать.

Андрей ЛАПОУХОВ,
Andrew@belsoft.vitebsk.by