Другие методы оптимизации программ

 

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

Операция называется предопределенной для некоторого значения операнда, если ее результат зависит только от этого операнда и остается неизменным (инвари­антным) относительно значений других операндов. Операция логического сложения (оr) является предопределенной для логиче­ского значения “истина” (true), а операция логического умножения – предопре­делена для логического значения “ложь” (false). Эти факты могут быть использованы для оптимизации логических выражений. Действительно, получив значение “истина” в последовательности логических сло­жений или значение “ложь” в последовательности логических умножений, нет никакой необходимости далее производить вычисления – результат уже опреде­лен и известен.

Например, выражение A or В or С or D не имеет смысла вычислять, если извест­но, что значение переменной А есть true (“истина”). Компиляторы строят объектный код вычисления логических выражений таким образом, что вычисление выражения прекращается сразу же, как только его зна­чение становится предопределенным. Это позволяет ускорить вычисления при выполнении результирующей программы. В сочетании с преобразованиями ло­гических выражений на основе тождеств булевой алгебры и перестановкой опе­раций эффективность данного метода может быть несколько увеличена.

He только логические операции могут иметь предопределенный результат. Не­которые математические операции и функции также обладают этим свойством. Например, умножение на 0 не имеет смысла выполнять.

Другой пример такого рода преобразований – это исключение вычислений для инвариантных операндов.

Операция называется инвариантной относительно некоторого значения операн­да, если ее результат не зависит от этого значения операнда и определяется дру­гими операндами.

Например, логическое сложение (оr) инвариантно относительно значения “ложь”, логическое умножение (and) – относительно значения “истина”; алгеб­раическое сложение инвариантно относительно 0, а алгебраическое умножение – относительно 1.

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

Оптимизация передачи параметров в процедуры и функции. Существуют методы, позволяющие снизить затраты кода и времени выполнения на передачу параметров в процедуры и функции и повысить в результате эффек­тивность результирующей программы:

· передача параметров через регистры процессора;

· подстановка кода функции в вызывающий объектный код.

Метод передачи параметров через регистры процессора позволяет разместить все или часть параметров, передаваемых в процедуру или функцию, непосредствен­но в регистрах процессора, а не в стеке. Это позволяет ускорить обработку пара­метров функции, поскольку работа с регистрами процессора всегда выполняется быстрее, чем с ячейками оперативной памяти, где располагается стек. Если все параметры удается разместить в регистрах, то сокращается также и объем кода, поскольку исключаются все операции со стеком при размещении в нем параметров.

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

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

Метод подстановки кода функции в вызывающий объектный код (так называе­мая inline-подстановка) основан на том, что объектный код функции непосредст­венно включается в вызывающий объектный код всякий раз в месте вызова функции.

Для разработчика исходной программы такая функция (называемая inline-функцией) ничем не отличается от любой другой функции, но для вызова ее в резуль­тирующей программе используется принципиально другой механизм. По сути, вызов функции в результирующем объектном коде вовсе не выполняется – про­сто все вычисления, производимые функцией, выполняются непосредственно в самом вызывающем коде в месте ее вызова.

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

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

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

Для оптимизации циклов используются следующие методы:

· вынесение инвариантных вычислений из циклов;

· замена операций с индуктивными переменными;

· слияние и развертывание циклов.

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

 

for i:=1 to 10 do

begin

A[i]:= В * С * A[i];

…

end;

 

может быть заменен на последовательность операций

 

D:= В * С;

for i:=1 to 10 do

begin

A[i]:= D * A[i];

…

end;

 

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

Замена операций с индуктивными переменными заключается в изменении сложных операций с индуктивными переменными в теле цикла на более простые опе­рации. Как правило, выполняется замена умножения на сложение.

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

Простейшей индуктивной переменной является переменная-счетчик цикла с перечислением значений (цикл типа for, который встречается в синтаксисе многих современных языков программирования). Более сложные случаи присутствия индуктивных переменных в цикле требуют специального анализа тела цикла. Не всегда выявление таких переменных является тривиальной задачей.

После того как индуктивные переменные выявлены, необходимо проанализиро­вать те операции в теле цикла, где они используются. Часть таких операций мо­жет быть упрощена. Как правило, речь идет о замене умножения на сложение.

Например, цикл

S:=10;

for i:=1 to N do A[i]:= i*S;

может быть заменен на последовательность операций

S:= 10;

Т:= S; i:=1;

while i <= 10 do

begin

A[i]:= Т; Т:=Т + 10; i:=i + 1;

end;

Здесь использован синтаксис языка Pascal, а Т – это некоторая новая временная переменная (использовать для той же цели уже существующую переменную S не вполне корректно, так как ее значение может быть использовано и после завер­шения этого цикла). В итоге удалось отказаться от выполнения N операций умножения, заменив их на N операций сложения (которые обычно выполняются быстрее). Индуктивной переменной в первом варианте цикла являлась i, а во втором варианте – i и Т.

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

Слияние и развертывание циклов предусматривает два различных варианта преобразований: слияния двух вложенных циклов в один и замена цикла на линей­ную последовательность операций.

Слияние двух циклов можно проиллюстрировать на примере следующих циклов:

 

for i:=l to N do

for j:=l to M do A[i,j]:= 0;

 

Здесь происходит инициализация двумерного массива. Но в объектном коде двумерный массив – это всего лишь область памяти размером N*M, поэтому (с точки зрения объектного кода, но не входного языка!) эту операцию можно представить так:

 

К:= N*M:

for i:=l to К do A[i]:= 0;

 

Развертывание циклов можно выполнить для циклов, кратность выполнения ко­торых известна уже на этапе компиляции. Тогда цикл, кратностью N, можно за­менить на линейную последовательность N операций, содержащих тело цикла. Например, цикл

 

for i:=l to 3 do A[i]:=i;

 

можно заменить операциями

 

А[1]:=1;

А[2]:=2;

А[3]:=3;