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

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

Например, при выполнении цикла на Фортране 77 (считается наиболее мощным языком для вычислительных задач)

DO 1 I = M, N, L

..........

Тело цикла

..........

1 CONTINUE,

как правило, производятся следующие шаги:

1. вычисление числа повторений K=(N-M+L)/L;

2. проверка его на нуль и если необходимо, то переход на шаг 3;

3. вычисление и запоминание значения управляющей переменной I;

4. выполнение тела цикла;

5. уменьшение счетчика повторений К=К-1 и приращение управляющей переменной I=I+L;

6. проверка на окончание цикла К=0 (и если требуется, переход на шаг 3).

Видно, что шаги с 1 по 3 составляют затраты на инициализацию цикла, а шаги 5 и 6 - затраты на завершение цикла. При этом шаги с 3 по 6 циклически повторяются.

Поэтому иногда издержки на организацию цикла сравнимы с затратами на выполнение тела цикла или больше.

Примеры на Паскале – слева неоптимизированные, справа – оптимизированные.

Правило 1.

Не следует использовать короткие циклы.

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

For I: =1 to 2 do

A[I]: =0;

лучше заменить на два оператора присваивания

A[1]: =0; A[2]: =0;

Правило 2.

Следует предусматривать (если это возможно) такую вложенность циклов, при которой циклы с наибольшим числом повторений были внутренними.

For I: =1 to 100 do Число инициализаций = 1

begin

For J: =1 to 10 do 100

begin

For K: =1 to 2 do 1000

begin

..... Всего = 1101

.....

end Число проверок на окончание = 2000

end 1000

end 100

Всего = 3100

Пример обратного вложения.

Таким образом, полное число инициализаций циклов уменьшено с 1101 до 23, а число проверок на окончание циклов с 3100 до 2022, если указанные три цикла организовать в обратном порядке

Правило 3.

Уменьшения времени на операции, не связанные с выполнением тела цикла, можно добиться путем развертки или объединения циклов.

Под разверткой цикла понимают увеличение шага цикла или удаление короткого внешнего цикла. Например:

- увеличение шага цикла

DO 1 I = I, N DO 1 I= 2, N, 2

A(I)= B(I) * C(I) A(I-1) = B(I-1) * C(I-1)

1 CONTINUE A(I) =B(I) * C(I)

1 CONTINUE

- отказ от короткого внешнего цикла

For i: =1 to 3 do For j: =1 to n do begin

For j: =1 to n do x[1, j]: =y[1, j]+z[1, j];

x[i, j]: =y[i, j]+z[i, j]; x[2, j]: =y[2, j]+z[2, j];

x[3, j]: =y[3, j]+z[3, j];

end;

- объединение циклов

For j: =1 to n do For i: =1 to n do begin

a[j]: =j*5; a[i]: =i*5;

For i: =1 to n do b[i]: =k[i]*3-6

b[i]: =k[i]*3-6; end;

Как видно из приведенных выше примеров, путем развертки или

объединения циклов, можно значительно уменьшить число повторений

тела цикла и тем самым сократить накладные расходы.