Основные машинно-независимые приемы оптимизации программ.




Виды оптимизации

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

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

 

Выбор оптимизируемого участка

При оптимизации кода вручную существует еще одна проблема: нужно знать не только, каким образом проводить оптимизацию, но и в каком месте её применить. Обычно из-за разных факторов (медленные операции ввода, разница в скорости работы человека-оператора и машины и т.д.) лишь 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. В результате выполнения процедуры сжатия циклов из тела цикла удаляется логический оператор перехода и сокращается число выполнений тела цикла.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-04-29 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: