Оптимизация циклов

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

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

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

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

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

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

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

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

for i:=l to 10 do

begin

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

end;

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

D:= В * С;

for i:=l to 10 do

begin

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

end;

если значения В и С не изменяются нигде в теле цикла.

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

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

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

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

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

S:= 10;

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

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

S:= 10;

T:= S; i:= 1;

While I<=10 do

Begin

A[i]:= T;

T:= T+10;

i:= i +1;

End;

В другом примере

s:=10;

for i:=l to n do

begin

R:= R + F(S);

S:= S + 10;

end.

две индуктивных переменных — i и S. Если заменить их на одну, то выяснится, что переменная i вовсе не имеет смысла, тогда этот цикл можно заменить на по­следовательность операций

S:= 10;

М:= 10 + N*10;

while S <= М do

begin

R:= R + F(S);

S:- S + 10;

end.

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

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

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 1:=1 to 3 do A[i]:= i;

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

A[1]:= 1;

A[2]:= 2;

A[3]:= 3;