Простейшие оптимизации программ

Циклы

В большинстве случаев именно циклы являются "горячими местами" программы.

Именно поэтому циклам уделяется много внимания как в архитектуре микропроцессора, так и в компиляторе.

Loop Stream Detector – позволяет отказаться от выборки и декодирования инструкций для маленьких циклов.

В компиляторе существует множество оптимизаций ориентированных именно на обработку циклов.

Распознание и классификация циклов

Такие оптимизации, как правило, могут быть выполнены только для циклов

Примеры "хороших" циклов

1.)   for(i=0;i<U;i++)
        a[i]=b[i];
2.)   i=0;
        do {
        a[i]=b[i];
        i++; } while(i<U);
3.)   for(i=0;i<U;i++) {
        a[j]=b[i];
        j+=c*i; }
4.)   i=0;
        do {
          a[i]=b[i];
          if(i++>=n) break;
        while(1);
    

Примеры "плохих" циклов:

1.)  for(i=0;i<3*i-n;i++) 
        a[i]=i;
2.)  for(i=0;i<n;i++) {
        a[i]=i;
        if(i<t)   break;       }
3.)  for(i=0;i<n;i++) {
        a[i]=i;
        if(i==t)   goto loop_skip;       }
4.)  for(i=0;i<n;i++) {
        a[i]=i;
        t=g(i);        }
    

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

Обзор оптимизаций циклических конструкций

Значительная часть оптимизаций компилятора связаны с циклами.

Вынос инвариантов цикла (Loop invariant code motion) – оптимизация, которая находит и выносит за пределы цикла выражения, независящие от индексных переменных цикла. Т.е. это выражение неизменно на каждой итерации.

while (j < maximum - 1) {
    j = j + (4+array[k])*pi+5;
 } 
 => loop invariant code motion =>
int maxval = maximum - 1;
int calcval = (4+array[k])*pi+5; 
while (j < maxval) {
   j = j + calcval;
}
    

Вынос условных переходов (Loop unswitching) – оптимизация, которая выносит условные переходы инвариантные для цикла из цикла путем дублирования тела цикла.

do i=1,1000  
  x[i] = x[i] + y[i];
  if (w) then y[i] = 0;
 end do; 
 => loop unswitching =>
if (w) then 
  do i=1,1000  
     x[i] = x[i] + y[i];
     y[i] = 0; 
  end do; 
else 
  do i=1,1000 do 
     x[i] = x[i] + y[i];
  end do 
end if;
    

Тест для оценки эффекта оптимизации loop unswitching:

Сравнение событий BR_MISSP_EXEC для оригинального и модифицированного теста:

Привязка событий процессора к строкам кода:

Разбиение, объединение циклов (Loop distribution, loop fusion) – это обратные друг другу оптимизации. Компилятор должен иметь инструмент оценки выгодности таких оптимизаций.

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

int i, a[100], b[100];
int i, a[100], b[100]; 
for (i = 0; i < 100; i++) {
  a[i] = 1;
  b[i] = 2;
 } 
=> Loop distribution =>
 for (i = 0; i < 100; i++) {
    a[i] = 1;
 }
 for (i = 0; i < 100; i++) {
    b[i] = 2; 
 }
    

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

int i, a[100], b[100];
int i, a[100], b[100]; 
for (i = 0; i < 100; i++) {
    a[i] = 1;
 }
 for (i = 0; i < 100; i++) {
    b[i] = 2; 
 }
=> Loop fusion
for (i = 0; i < 100; i++) {
  a[i] = 1;
  b[i] = 2;
 } 
    

Различные микропроцессоры имеют различные критерии выгодности применения этой оптимизации.

Расщепление цикла (Loop peeling,splitting) – оптимизация, которая пытается упростить цикл "отщеплением" крайних итераций.

p = 10; 
for (i=0; i<10; ++i) { 
   y[i] = x[i] + x[p];
   p = i;
} 
    

Здесь p=10 только в первой итерации, а в дальнейшем p=i-1

  =>Loop peeling =>
y[0] = x[0] + x[10];
 for (i=1; i<10; ++i) {
 y[i] = x[i] + x[i-1];
 }
    

Развертка цикла (Loop unrolling) – эта техника призвана уменьшить количество условных переходов в цикле. Может улучшить инструкционный параллелизм. Несколько итераций цикла объединяются в одну. Есть свои минусы. Может повыситься нагрузка на регистры, увеличивается размер кода, что также может привести к ухудшению производительности.

for (int x = 0; x < 100; x++) {
  delete(x);
}
  => Loop unrolling =>
 for (int x = 0; x < 100; x += 5) {
   delete(x);
   delete(x+1);
   delete(x+2);
   delete(x+3);
   delete(x+4);
 } 
    

Полная развертка (complete unrolling) применяется к небольшим циклам и бывает очень эффективна. Как правило в случае вложенных циклов развертываются внутренние циклы.

Перестановка циклов (Loop interchange) – оптимизация при которой меняется порядок итерационных переменных.

do i=0,10 
   do j=0,20 
     a[i,j] = i + j 
 => Loop interchange
do j=0,20
  do i=0,10
    a[i,j] = i + j
    

Для чего выполняется эта оптимизация ?

Пример эффективности оптимизации перестановки циклов

Вытеснение данных из кэш:

Разбиение цикла на блоки (Loop blocking)

Определение индукционных переменных

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

  for(i=0;i<100;i++) {
    a[i]=i*8+4;
  } 
  =>
  temp=4;
  for(i=0;i<100;i++) {
    a[i] = temp;
    temp +=8;
  }
    

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

Помимо этих оптимизаций существуют и другие, порой очень нетривиальные:

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

Нормализованный цикл

Предположим у нас есть цикл:

DO I=L,U,S
  A(I)=…
END DO
    

Для упрощения рассуждений его можно преобразовать к нормализованному циклу:

DO J=1,(U-L+S)/S,1
  A(J*S-S+L) = …
END DO
    

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

 /Qopt-report[:n]
          generate an optimization report to stderr
            0   disable optimization report output
            1   minimum report output
            2   medium output (DEFAULT when enabled)
            3   maximum report output
    

Пример диагностики:

LOOP INTERCHANGE in loops at line: 8 9 
Loopnest permutation ( 1 2 ) --> ( 2 1 )
Fusion loop partitions: (loop line numbers)
Fused Loops: ( 9 14 )