Правило 4.
Правило 3.
Правило 2.
Правило 1.
Оптимизация циклов
Большая часть процессорного времени в программах приходится на выполнение циклов, и здесь может достигаться самый значительный выигрыш от оптимизации.
Например, при выполнении цикла на Фортране 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 циклически повторяются.
Поэтому иногда издержки на организацию цикла сравнимы с затратами на выполнение тела цикла или больше.
Примеры на Паскале – слева неоптимизированные, справа – оптимизированные.
Не следует использовать короткие циклы.
Например, цикл
For I:=1 to 2 do
A[I]:=0;
лучше заменить на два оператора присваивания
A[1]:=0; A[2]:=0;
Следует предусматривать (если это возможно) такую вложенность циклов, при которой циклы с наибольшим числом повторений были внутренними.
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, если указанные три цикла организовать в обратном порядке
Уменьшения времени на операции, не связанные с выполнением тела цикла, можно добиться путем развертки или объединения циклов.
Под разверткой цикла понимают увеличение шага цикла или удаление короткого внешнего цикла. Например:
- увеличение шага цикла
DO 1 I = I, N DO 1 I= 2, N, 2
A(I)= B(l) * C(l) A(l-l) = B(l-1) * C(l-l)
1 CONTINUE A(l) =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;
Как видно из приведенных выше примеров, путем развертки или
объединения циклов, можно значительно уменьшить число повторений
тела цикла и тем самым сократить накладные расходы.
Большего эффекта можно добиться путем оптимизации тела цикла. К процедурам оптимизации тела цикла относятся чистка цикла и вынос ветвлений из цикла.
Чистка цикла - это вынос из тела цикла операций, не зависящих от переменной цикла. Классическим примером чистки цикла является программа, вычисляющая следующую сумму:
S = X*Аt,
sum:=0; sum:=0;
for i:=1 to n do for i:=1 to n do
sum:=sum+x*A[i]; sum:=sum+A[i]
sum:=x*sum;
В данном примере вынос из цикла одного умножения сэкономит N-1 умножение. Спедующим примером чистки цикла является программа, вычисляющая сумму
S = (L - 1)
sum:=0; sum:=0;
for i:=1 to n do for i:=1 to n do
sum:=sum+L[i]-1; sum:=sum+L[i];
sum:=sum-n;
В данном случае удается сэкономить N-1 вычитание.
Вынос ветвления из цикла применяется тогда, когда исходный цикл состоит из двух и более частей, и в зависимости от истинности определенного условия выполняется одна из этих частей. Выносом про-
верки этого условия из цикла исходный цикл заменяется двумя циклами, соответствующими двум частям исходного:
for i:=1 to 20 do if k=2 then
if k=2 then for i:=1 to 20 do
a[i]:=b[i]+2 a[i]:=b[i]+2
else else
a[i]:=b[i]*c[i]; for i:=1 to 20 do
a[i]:=b[i]*c[i];
В результате выполнения процедуры выноса ветвлений из цикла уменьшается время счета вследствии сокращения количества проверок выполнения условий, равного числу повторений цикла.
Задание. Если проанализировать следующий фрагмент программы, окажется то, что проверка условия x < 0 в цикле вообще лишняя.
for i:=1 to N do
begin
x[i]:=sqr(a[i]);
y[i]:=-b[i]+x[i];
if x[i]>=0 then
z[i]:=x[i];
end
Таким образом, основными процедурами по оптимизации циклов являются:
- чистка циклов, т.е. удаление из тела цикла операций, не зависящих от переменной цикла;
- объединение циклов;
- вынос ветвлений из циклов;
- увеличение шага изменения управляющей переменной цикла;
- удаление коротких циклов;
- оптимальное вложение циклов.