Виды оптимизации
Оптимизация кода может проводиться, как и вручную, программистом, так и автоматизировано. В последнем случае оптимизатор может быть как отдельным программным средством, так и быть встроенным в компилятор.
Существуют такие понятия как высокоуровневая и низкоуровневая оптимизация. Высокоуровневые оптимизации в большинстве проводятся программистом, который, оперируя абстрактными сущностями (функциями, процедурами, классами и т.д.) и представляя себе общую модель решения задачи, может оптимизировать дизайн системы. Оптимизации на уровне элементарных структурных блоков исходного кода (циклов, ветвлений и т.д.) тоже обычно относят к высокому уровню. Низкоуровневая оптимизация производится на этапе превращения исходного кода в набор машинных команд, и зачастую именно этот этап подвергается автоматизации.
Выбор оптимизируемого участка
При оптимизации кода вручную существует еще одна проблема: нужно знать не только, каким образом проводить оптимизацию, но и в каком месте её применить. Обычно из-за разных факторов (медленные операции ввода, разница в скорости работы человека-оператора и машины и т.д.) лишь 10% кода занимают целых 90% времени выполнения. Так как на оптимизацию придется расходовать дополнительное время, поэтому вместо попыток оптимизации всей программы лучше будет оптимизировать эти "критичные" ко времени выполнения 10%. Такой фрагмент кода называют узким местом или бутылочным горлышком, и для его определения используют специальные программы - профайлеры, которые позволяют замерять время работы различных частей программы.
Вред и польза оптимизаций
Практически ко всему в программировании надо относиться рационально, и оптимизации - не исключение. Считается, что неопытный программист на ассемблере обычно пишет код, который в 3-5 раз медленнее, чем код, сгенерированный компилятором.
К оптимизациям, проводимым оптимизатором, у большинства нет претензий, причем иногда некоторые оптимизации являются практически стандартными и обязательными.
Многочисленные сложные оптимизации на уровне машинного кода могут сильно замедлить процесс компиляции. Причем выигрыш от них может быть чрезвычайно мал по сравнению с оптимизациями общего дизайна системы (Вирт). Также не следует забывать, что современные, "навороченные" синтаксически и семантически языки имеют множество тонкостей, и программист, который их не учитывает, может быть удивлен последствиями оптимизации.
Требования к оптимизирующим алгоритмам:
· Оптимизация должна быть максимально машинно-независимой и переносимой на другие платформы без дополнительных затрат и существенных потерь эффективности.
· Оптимизация не должна увеличивать трудоемкость разработки приложения более чем на 10%—15%, а в идеале, все критические алгоритмы желательно реализовать в виде отдельной библиотеки, использование которой не увеличивает трудоемкости разработки вообще.
· Оптимизирующий алгоритм должен давать выигрыш не менее чем на 20%—25% в скорости выполнения.
· Оптимизация должна допускать безболезненное внесение изменений.
Правила оптимизации:
Правило 1
Прежде, чем оптимизировать код, обязательно следует иметь надежно работающий не оптимизированный. Создание оптимизированного кода "на ходу", по мере написания программы, невозможно. Такова специфика планирования команд - внесение даже малейших изменений в алгоритм практически всегда оборачивается кардинальными переделками кода.
Правило 2
Основой прирост оптимизации дает не учет особенностей системы, а алгоритмическая оптимизация. Правильное планирование команд ускорят программу в лучшем случае в несколько раз.
Правило 3
Сначала нужно убедиться, что все возможное для увеличения быстродействия кода в рамках языка высокого уровня уже сделано. В частности, следует избавиться от прожорливых арифметических операций, свести к минимуму ветвления, развернуть циклы с малым количеством итераций.
Основные машинно-независимые приемы оптимизации программ.
1. Заголовки сообщений. Если большая часть сообщений содержит пробелы (или другие повторяющиеся символы), то для экономии памяти ЭВМ следует использовать команды, выполняющие заполнение этой части сообщения пробелами
2. Инициирование переменных. Если начальные значения присваиваются переменным (или константам) одновременно с их объявлением, то экономится и память, и время выполнения программы, т.к. в этом случае переменные получают начальные значения во время компилирования программы, а не во время ее выполнения. Заодно облегчается внутреннее документирование программы и обходятся ошибки в случае, когда переменной не было присвоено начальное значение.
3. У меньшение числа переменных. Отработанная «временная» переменная на участке программы (например, управляющая переменная цикла) продолжает занимать область памяти и дальше во все время выполнения оставшейся части программы. Ее надо удалить. Но ее можно использовать в программе и дальше вместо другой «временной» переменной (например, в качестве управляющей переменной в другом цикле) в другом качестве, чтобы не создавать новую. При этом тип переменной остается неизменной.
4. Выбор типов данных. Переменные разных типов данных в ЭВМ обрабатываются с разной затратой времени и памяти.
5. Удаление излишних операторов присваивания. Рассматриваемая процедура состоит в удалении из программы некоторых операторов присваивания и замене в некоторых других операторах (присваивания или условного перехода) переменных, являющихся левой частью удаляемых операторов, выражениями, являющимися правой частью удаляемых операторов, то есть выполняется объединение операторов.
6. Отождествление переменных. Если в программе имеется оператор вида А: =В, то во всех последующих операторах программы можно заменить переменную А переменной В или числовым значением переменной В, а оператор А: = В удалить. Если переменная А является индексируемой переменной, то оператор А: = В остается в программе, а переменная А в некоторых операторах заменяется переменной В.
7. Удаление тождественных операторов. Суть этой процедуры состоит в удалении из программы тождественных операторов, т.е. операторов вида А: = А. Такие операторы могут появляться в программе в результате выполнения оптимизационных и других преобразований.
8. Устранение невыполняемых операторов. В реальных программах могут встретиться участки, содержащие невыполняемые операторы, т. е. такие операторы, которые не выполняются при любых наборах начальных данных.
9. Использования ввода-вывода. Операции ввода-вывода занимают много времени и должны быть сокращены до минимума. Данные, которые можно вычислить внутри программы, вводить не надо. Две последовательные команды ввода-вывода для одного и того же устройства можно объединить в одну команду. Это сокращает количество обращений к системным подпрограммам ввода-вывода, что, естественно, сокращает время выполнения программы.
10. Выделение процедур (функций). Если в программе имеются последовательности одинаковых операторов, которые отличаются только разными идентификаторами и значениями констант, то может быть полезно выделить их в процедуру (или функцию). Это дает значительное сокращение текста программы, но замедляет ее выполнение, т.к. вход-выход процедуры - трудоемкая операция, и работа с параметрами идет медленнее, чем с локальными переменными.
11. Сокращение числа процедур (функций). Связь процедур (функций) с основной программой обеспечивается операторами вызова в основной программе, которые замедляют работу программы. Когда критерием оптимизации является время счета программы, то нужно хорошо подумать прежде, чем выделить участок программы в отдельную процедуру (функцию). Если много операторов выполняются много раз и в разных местах программы, то, конечно, их надо выделить в отдельную процедуру. Но неразумно вызывать небольшую процедуру два раза. Сокращение числа процедур (функций) выполняется заменой операторов их вызова телами этих процедур (функций) и заменой.
12. Арифметические операции. Арифметические операции выполняются с разной скоростью. Перечислим их в порядке возрастания времени их выполнения:
1) сложение и вычитание;
2) умножение;
3) деление;
4) возведение в степень.
Иногда бывает целесообразно заменить одну операцию другой. Например, 3*1 может быть заменено 1+1+1 или Х*2 можно заменить на Х+Х. Замена возведения в степень несколькими операциями ум- ножения экономит и память, и время, если показатель степени является небольшим целым числом. Умножение выполняется почти в два раза быстрее деления. Вместо А/5 можно написать 0.2*А; Вместо А1 = B/D/E + С можно написать А1 = B/(D*E) + С.
13. Преобразование выражений. Предварительное преобразование (упрощение) выражений может привести к исключению многих арифметических операций. Например, X: = 2*У + 2*Т; можно заменить на X: = 2*(У + Т)
14. Оптимизация выражений. Суть процедуры состоит в замене всех сложных семантически эквивалентных подвыражений на одно простое.
15. Предварительное вычисление арифметических подвыражений.
Вместо, например:
А: = (M*B*C)/(D-E);
К: = D-E-B*C*M;
можно написать:
Т: = N*B*C;
U: = D-E;
А: = T/U;
К: = U-T;
Сокращается текст программы и время ее выполнения за счет сокращения количества выполняемых операций. Зато быть может чуть-чуть увеличивается память для Т и U.
16. Устранение лишних скобок. Суть этой процедуры заключается в устранении пар скобок в арифметических или логических выражениях, являющихся содержательно излишними.
17. Устранение лишних меток. По ряду причин в программах встречаются метки перед операторами, на которые нет передач управления. Такие метки являются лишними и их следует удалить из программы.
18. Устранение лишних операторов перехода. После многих оптимизационных переделок программы, в ней могут появиться операторы безусловного перехода, которые передают управление оператору с несуществующей меткой. Их надо удалить.
19. Неявные операции. Операция Т:= М(1) требует в 1,5-2 раза больше времени и памяти, чем Т: = А;, а если М — параметр или функция, то в 2,5-3 раза больше. Там, где часто используется М (1), можно использовать простую переменную MI: = M(I) и т. д.
20. Чистка циклов. Время выполнения программы в значительной мере зависит от времени выполнения многократно повторяемых участков - от циклов. Поэтому основное внимание необходимо уделять именно циклам. Процедура чистки цикла уменьшает время выполнения цикла (следовательно, и программы) путем удаления из его тела арифметических выражений или их частей, не зависящих от управляющей переменной цикла. Выражения, которые не меняют своих значений в теле цикла, должны вычисляться перед циклом. Это не меняет длины программы, но дает выигрыш в скорости ее выполнения.
21. Объединение циклов. При трансляции любого цикла с языка высокого уровня в машинные коды в объектной программе появляются операции, реализующие заголовок цикла, т. е. увеличение управляющей переменной цикла на значение его шага; сравнение управляющей переменной с граничным значением; передачу управления. Процедура объединения циклов производит соединение нескольких циклов с одинаковыми заголовками в один. Например:
FOR I: = 1 ТО 500 DO X[I]: = 0;
FOR J: = 1 ТО 500 DO Y[J]: = 0;
можно объединить в один цикл, что сокращает как время выполнения программы, так и память:
FOR I: = 1 ТО 500 DO BEGIN X[I]: = 0; У[1]: = 0 END.
22. Вынос ветвлений из цикла. Пусть исходный цикл состоит из двух частей, и в зависимости от выполнения определенного условия выполняется одна из этих частей.
FOR I = 1 ТО 200 DO
IF К = 2 THEN A(I) = B(I)*C(I) ELSE A (I) = В (I) + 2;
Тогда исходный цикл можно заменить двумя циклами, соответствующими двум частям исходного цикла:
IF К = 2 THEN FOR 1=1 ТО 200 DO A(I) = B(I)*C(I);
ELSE FOR 1=1 TO 200 DO A (I) = В (I) + 2.
В результате выноса ветвления из цикла уменьшается время счета программы благодаря сокращению числа проверок выполнения условий.
23. Удаление пустых циклов. Суть этой процедуры состоит в удалении из программы пустых циклов. Такие циклы могут появиться в программе в результате небрежности программиста, а чаще всего в результате выполнения оптимизационных и других преобразований.
24. Сжатие циклов. В ряде случаев в теле цикла встречаются условия, которые могут ограничивать область изменения управляющей переменной цикла.
FOR I = А ТО В DO IF I<= С THEN R(I) = P(I);
Процедура сжатия циклов осуществляет перенос таких ограничений в заголовок цикла:
DO I = А ТО С DO R(I) - P(I);
Здесь предполагается, что А <: С < B. В результате выполнения процедуры сжатия циклов из тела цикла удаляется логический оператор перехода и сокращается число выполнений тела цикла.