Техника оптимизации под Linux. Часть 3 – оптимизация циклов

КРИС КАСПЕРСКИ

Техника оптимизации под Linux

Часть 3

Большое тестовое сравнение Linux-компиляторов продолжается! Тема сегодняшнего исследования – циклы и их оптимизация. В основном мы будем говорить о трех наиболее популярных компиляторах – GCC 3.3.4, Intel C++ 8.0 и Microsoft Visual C++ 6.0, к которым теперь присоединился и GCC 4.0.0 со своим новым оптимизатором циклов.

По статистике до 90% времени исполнения приходится на глубоко вложенные циклы, от качества оптимизации которых зависит быстродействие всей программы в целом. Современные компиляторы поддерживают множество прогрессивных технологий оптимизации и способны буквально творить чудеса!

Стратегия оптимизации циклов тесно связана с архитектурой процессора, кэш-контроллера и контроллера оперативной памяти. Это слишком объемная, можно даже сказать, монументальная тема, и в рамках настоящей статьи она не обсуждается. Читайте документацию, распространяемую фирмами Intel и AMD (причем не только по процессорам, но и по чипсету) или мою книгу «Техника оптимизации программ – эффективная работа с оперативной памятью», в ней эти вопросы освещены достаточно подробно.

Выравнивание циклов

Выравнивание циклов (loop alignment) имеет много общего с выравниванием ветвлений, о котором мы уже говорили в предыдущей статье. Кратко опишем ситуацию для тех, кто не читал ее. Компиляторы msvc и icl вообще не выравнивают циклы, располагая их в памяти как угодно. В худшем случае это приводит к трех-четырехкратному падению производительности. В среднем же теряется порядка 30%.

Компилятор gcc позволяет выравнивать циклы на величину, кратную степени двойки. За это отвечает ключ -falign-loops=n (по умолчанию n равен двум, что, как уже отмечалось, далеко не самая лучшая стратегия выравнивания, и лучше выравнивать циклы по границе четырех байт).

Ключ -fno-align-loops (аналогичный ключу -falign-loops=1) отключает выравнивание. На уровнях оптимизации -O2 и -O3 выравнивание циклов по умолчанию включено, и отключать его было бы неразумно.

Итого:

• msvc – не выравнивает.
• icl – не выравнивает.
• gcc – выравнивает по границе степени двойки.

Разворот циклов

Микропроцессоры с конвейерной архитектурой (а к таковым относятся все современные x86-процессоры), плохо приспособлены для работы с циклами. Для достижения наивысшей производительности процессору необходим достаточно протяженный участок «трассы выполнения», свободный от ветвлений.

Компактные циклы вида:

for(a=0;a

исполняются очень медленно и для увеличения быстродействия приходится прибегать к их развороту (unrolling).

Под «разворотом» в общем случае понимается многократное дублирование цикла, которое реализуется приблизительно так:

Листинг 1. Цикл до разворота

for(i=1; i<n;i+)

    k += (n % i);

Листинг 2. Цикл после разворота (больший размер — большая скорость)

// разворот цикла на 4 итерации

// выполняем первые n – (n % 4) итераций

for(i=1; i<n;i+=4)

{

    k += (n % i) + \

    (n % i+1) + \

    (n % i+2) + \

    (n % i+3);

}

// выполняем оставшиеся итерации

for(i-=4; i<n;i++) k += (n % i);

Листинг 3. Цикл после разворота (меньший размер, меньшая скорость — машинное представление i++ намного более

компактно, чем i+const, однако если выражения …(n % i+const_1) + (n % i+const_2) … могут выполняться одновременно,

то …(n % i++) + (n % i++)… вычисляются последовательно, поскольку содержат зависимость по данным)

for(i=1; i<(n-3);)

{

    k += (n % i++) + \

    (n % i++) + \

    (n % i++) + \

    (n % i++);

}

for(;i<n;i++) k += (n % i);

Компилятор msvc вообще не разворачивает циклы, и эту работу приходится выполнять вручную.

Компилятор icl разворачивает только циклы for по сценарию больший размер – большая скорость. Причем циклы с заранее известным количеством итераций:

for(a=0;a

где const <= 32 трансформируются в линейный код, и цикл как таковой при этом исчезает (см. раздел «Шелушение циклов»). Как следствие – размер программы существенно возрастает, а вместе с ним возрастает и риск «вылететь» за пределы кэша первого уровня, после чего производительность упадет так, что не поднимешь и домкратом. Если const >32, цикл разворачивается на количество итераций, кратное const, но не более 16, при этом компилятор учитывает число инструкций в теле цикла – более компактные циклы разворачиваются на большее число итераций.

Циклы, количество итераций которых компилятору неизвестно:

for(a=0;a

всегда разворачиваются на 5 итераций, а оставшиеся (n % 5) итераций выполняются в отдельном неразвернутом цикле. Циклы с ветвлениями разворачиваются только при трансформации в линейный код (при этом ветвления, естественно, исчезают):

for (a=0; a<3;a++) if (a%2) x[a]++; else x[a]--;

преобразуется в:

x[0]--; x[1]++; x[2]--;

Компилятор gcc по умолчанию не разворачивает циклы даже на уровне оптимизации O3, и делает это только с ключом -funroll-all-loops, поддерживающим все виды циклов, а не только цикл for. Циклы с известным количеством итераций, где const <= 32 разворачиваются полностью, при const > 32 – приблизительно на 4 итерации (точное значение зависит от количества инструкций в теле цикла). Если внутри цикла присутствуют одно или несколько ветвлений, при развороте они неизбежно дублируются, в результате чего производительность оказывается даже ниже, чем была до оптимизации! Циклы с неизвестным количеством итераций не разворачиваются вообще. Для тонкой настройки существуют ключи max-unrolled-insns (максимальное количество инструкций, при котором цикл еще может быть развернут, и если он будет развернут, это значение определяет величину разворота), max-average-unrolled-insns (максимальное среднее количество инструкций, которое цикл может иметь после разворота) и max-unroll-times (максимальная степень разворота). Разворот по всех случаях выполняется по сценарию больший размер – большая скорость.

Итого:

• msvc:
  • не разворачивает никакие циклы.
• icl:
  • циклы с переменным количеством итераций разворачивает на 5 итераций;
  • циклы с cost <= 32 разворачивает полностью;
  • циклы с const > 32 разворачивает на величину, кратную const, но не больше 10h;
  • учитывает количество инструкций в цикле;
  • циклы разворачиваются по сценарию: больший размер – большая скорость.
• gcc:
  • на уровне O3 по умолчанию не разворачивает;
  • циклы с переменным количеством итераций никогда не разворачиваются;
  • циклы с постоянным количеством итераций развариачиваются приблизительно на 4 итерации (но тут все зависит от числа инструкций).

Шелушение циклов

Идея шелушения циклов (по-английски «peeling») заключается в «сдирании» с цикла одной или нескольких итераций с последующей трансформацией в линейный код. Фактически шелушение циклов является частным случаем разворота, однако, область его применения этим не ограничивается.

Рассмотрим следующий код:

Листинг 4. Кандидат на оптимизацию

for(i=0; i<n; i++)

    a[i] = b[i] + 1;

for(j=0; j<n+1; j++)

    c[j] = d[j] – 1;

Чтобы объединить оба цикла в один (см. раздел «Объединение циклов»), необходимо «содрать» с цикла j одну «лишнюю» итерацию:

Листинг 5. Оптимизированный вариант

for(i = 0; i < n; i++)

{

    a[i] = b[i] + 1;

    c[i] = d[i] - 1;

}

    c[i] = d[i] - 1;

Компилятор msvc шелушить циклы не умеет, icl и gcc – умеют, но особой радости от этого никто не испытывает, поскольку они никогда не комбинируют шелушение с другими приемами оптимизации, что практически полностью его обесценивает. А вот компиляторы от SUN или Hewlett-Packard – комбинируют!

Компилятор gcc содержит специальный ключ -fpeel-loops, полностью разворачивающий циклы с небольшим количеством итераций. Пороговое значение назначается ключами: max-peel-times (сколько итераций можно сдирать с одного цикла), max-completely-peel-times (максимальное количество итераций цикла, который еще может быть развернут), max-completely-peeled-insns (максимальное количество инструкций, при которых цикл еще может быть развернут) и max-peeled-insns (максимальное количество инструкций развернутого цикла).

Итого:

• msvc – не шелушит.
• gcc – шелушит.
• icl – шелушит.

Фальцевание циклов

Фальцевание циклов (fold loops) внешне очень похоже на разворот, но преследует совсем другие цели, а именно: увеличение количества потоков данных на одну итерацию. Чем выше плотность (strength) потоков, тем выше параллелизм обработки данных, а, значит и скорость выполнения цикла.

Рассмотрим следующий пример:

Листинг 6. Неоптимизированный вариант – один поток данных на итерацию

for(i=0; i<XXL; i++)

    sum += a[i];

Чтобы сократить время выполнения цикла, необходимо увеличить количество потоков, переписав наш код так:

Листинг 7. Оптимизированный вариант — четыре потока данных на итерацию

for(i=0; i<XXL; i += 4)

{

    sum += a[i];

    sum += a[i+1];

    sum += a[i+2];

    sum += a[i+3];

}

for (i -= 4; i<XXL; i++)

    sum += a[i];

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

Итого:

• msvc – фальцует.
• gcc – фальцует.
• icl – фальцует.

Векторизация

Начиная с Pentium MMX, в x86-процессорах появилась поддержка векторных команд (они же «мультимедийные команды»). К сожалению, в ANSI C векторные операции отсутствуют, а нестандартные языковые расширения создают проблему переносимости, поэтому вся забота по векторизации циклов ложится на компилятор. Он должен проанализировать исходный код и определить, какие операции могут выполняться параллельно, а какие нет.

Допустим, исходный цикл выглядел так:

Листинг 8. Цикл до векторизации

for(i=0; i<XXL; i++)

    a[i] += b[i];

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

Листинг 9. Тот же цикл, записанный в векторной нотации

a[0:N] = a[0:N] + b[0:N];

Старшие представители процессоров Pentium могут обрабатывать до 8 порций данных параллельно, и если N превышает это число, приходится поступать так:

Листинг 10. Цикл после векторизации

// обрабатываем первые (N-N%VF) ячеек векторным способом VF – количество порций данных, которые процессор будет

// обрабатывать за один раз

for (i=0; i<XXL; i+=VF)

    a[i:i+VF] = a[i:i+VF] + b[i:i+VF];

// обрабатываем оставшийся «хвост» обычным способом

for (i -= VF ; i < XXL; i++)

    a[i] = a[i] + b[i];

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

Листинг 11. Цикл, который нельзя векторизовать

for (i=1; i<XXL; i++)

    a[i] = a[i-1] + b[i];

Поскольку последующая ячейка (a[i]) вычисляется на основе предыдущей (a[i-1]), данные не могут обрабатываться параллельно.

Компилятор msvc не поддерживает векторизацию, а icl поддерживает, но задействует ее только в том случае, если указан ключ -ax. Компилятор gcc поддерживает векторизацию только начиная с версии 3.4.3, да и то если присутствует флаг -ftree-vectorize.

Итого:

• msvc – не векторизует.
• icl – векторизует.
• gcc – векторизует начиная с версии 3.4.3.

Автопараллелизм

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

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

Листинг 12. Неоптимизированный вариант

for (i=0; i

    a[i] = a[i] + b[i] * c[i];

Поскольку зависимость по данным отсутствует, цикл можно разбить на два. Первый будет обрабатывать ячейки от 0 до XXL/2, а второй – от XXL/2 до XXL. Тогда на двухпроцессорной машине скорость выполнения цикла практически удвоится. А если еще учесть, что многопроцессорные машины, как правило, имеют MMX-команды, да использовать векторизацию...

Листинг 13. Оптимизированный вариант

/* поток A */

for (i=0; i<XXL/2; i++)

    a[i] = a[i] + b[i] * c[i];

/* поток B */

for (i=XXL/2; i<XXL; i++)

    a[i] = a[i] + b[i] * c[i];

Компилятор icl – единственный из всех трех, способный на «параллелизацию» циклов. Чтобы ее задействовать, используйте ключ –parallel, только помните, что при выполнении кода на однопроцессорных машинах, оптимизация дает обратный эффект (накладные расходы на организацию потоков дают о себе знать).

Итого:

• msvc – автопараллелизм не поддерживается.
• icl – автопараллелизм поддерживается.
• gcc – автопараллелизм не поддерживается.

Программная конвейеризация

Разворот цикла традиционными методами (см. раздел «Разматывание циклов») порождает зависимость по данным. Вернемся к листингу 3. Хотя загрузка обрабатываемых ячеек происходит параллельно (практически параллельно, они будут ползти по конвейеру, находясь на различных стадиях готовности), следующая операция сложения не может быть начата до тех пор, пока не будет завершена предыдущая.

Для усиления параллелизма необходимо суммировать все ячейки в своих переменных, как показано ниже:

Листинг 14. Оптимизированный вариант

// обрабатываем первые XXL – (XXL % 4) итераций

for(i=0; i<XXL;i+=4)

{

    sum_1 += a[i+0];

    sum_2 += a[i+2];

    sum_3 += a[i+3];

    sum_4 += a[i+4];

}

// обрабатываем оставшийся «хвост»

for(i-=XXL; i<XXL;i++)

    sum += a[i];

// складываем все воедино

sum += sum_1 + sum_2 + sum_3 + sum_4;

Такая техника оптимизации называется программной конвейеризацией (software pipelining), и из трех рассматриваемых компиляторов ею не обладает ни один. Только gcc робко пытается ослабить зависимость по sum, используя два регистра при развороте на четыре итерации. Остальные же компиляторы грузят все ячейки в один и тот же регистр, очевидно, руководствуясь принципом экономии. Регистров общего назначения всего семь, и их постоянно не хватает. К сожалению, компилятор не отличает ситуацию действительно дефицита регистров от их избытка, вынуждая нас прибегать к ручной оптимизации.

Итого:

• msvc – программная конвейеризация не поддерживается.
• icl – программная конвейеризация не поддерживается.
• gcc – программная конвейеризация частично поддерживается.

Предвычисление индуктивных циклов

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

Рассмотрим следующий пример:

Листинг 15. Индуктивный цикл до оптимизации

for (i=0; i<XXL; i++)

    sum++;

Очевидно, что конечное значение sum равно:

Листинг 16. Индуктивный цикл после оптимизации

sum += XXL;

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

Два остальных компилятора оставляют индуктивные циклы такими, какие они есть, даже не пытаясь их оптимизировать!

Итого:

• msvc – предвычисляет некоторые индуктивные циклы.
• icl – не предвычисляет индуктивные циклы.
• gcc – не предвычисляет индуктивные циклы.

Разбивка длинных цепочек зависимостей

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

Листинг 17. Индуктивный цикл до оптимизации

for(i=0;i

{

    x += 2;

    a[i] = x;

}

Выражение (a[i]=x) не может быть выполнено до тех пор, пока не будет вычислено (x+=2), а оно в свою очередь должно дожидаться завершения предыдущей итерации. Индукция однако! От нее можно избавится, вычисляя значение n-ой итерации на «лету»:

Листинг 18. Индуктивный цикл после оптимизации

for(i=0;i

{

    a[i] = i*2 + x;

}

Расплатой за отказ от индукции становится появление «лишней» инструкции умножения, однако накладные расходы на ее выполнение с лихвой окупаются конвейеризацией (а при желании и векторизацией!) цикла. Такая техника оптимизации называется «разбивка длинных цепочек зависимостей» (breaks long dependency chains) и реализована только в gcc, начиная с версии 4.0 (за это отвечает ключ -fsplit-ivs-in-unroller), а все остальные рассматриваемые компиляторы на это, увы, не способны.

Итого:

• msvc – не разбивает длинные цепочки зависимостей.
• icl – не разбивает длинные цепочки зависимостей.
• gcc – разбивает длинные цепочки зависимостей.

Устранение хвостовой рекурсии

Хвостовой рекурсией (tail recursion) называется такой тип рекурсии, при котором вызов рекурсивной функции следует непосредственно за оператором return.

Классическим примером может служить алгоритм вычисления факториала:

Листинг 19. Хвостовая рекурсия до оптимизации

int fact(int n, int result)

{

    if(n == 0)

    {

           return result;

    }

    else

    {

           return fact(n - 1, result * n);

    }

}

Вызов функции – достаточно «дорогостоящая» операция, и от него лучше избавиться. Это легко! Хвостовая рекурсия легко трансформируется в цикл. Смотрите:

Листинг 20. Хвостовая рекурсия после оптимизации

for(i=0; i<n; i++)

    result *= n;

Компиляторы msvc и gcc всегда разворачивают хвостовую рекурсию в цикл, а вот icl этого делать не умеет.

Итого:

• msvc – устраняет хвостовую рекурсию.
• icl – не устраняет хвостовую рекурсию.
• gcc – устраняет хвостовую рекурсию.

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

Несколько циклов с одинаковым заголовком могут быть объединены в один, что сокращает накладные расходы на его организацию. Эта методика имеет множество названий – loops fusion, merge loops, jam loops, создающих большую путаницу и вводящих программистов в заблуждение. В действительности же это не три различные стратегии оптимизации, а всего одна, но какая! Продемонстрируем ее на следующем примере:

Листинг 21. Циклы до объединения (неоптимизированный вариант)

for(i=0; i<XXL; i++)

    a[i] = b[i] + 1;

for(j=0; j<XXL; j++)

    d[j] = у[j] -1;

Поскольку заголовки обоих циклов абсолютно идентичны, нам достаточно лишь «коллективизировать» их содержимое:

Листинг 22. Циклы после объединения (оптимизированный вариант)

for(i = 0; i < XXL; i++)

{

    a[i] = b[i] + 1;

    d[j] = у[j] -1;

}

А вот более сложный пример:

Листинг 23. Кандидат на оптимизацию путем объединения

for(i=0; i<XXL; i++)

    a[i] = b[i] + 1;

for(j=0; j<XXL-1; j++)

    d[j] = у[j] -1;

Непосредственно объединить циклы невозможно, поскольку цикл j на одну итерацию короче. Чтобы уравнять оба заголовка в правах, предварительно необходимо «содрать» (см. «loop peeling» фирменного руководства) с цикла i одну итерацию:

Листинг 24. Оптимизированный вариант

for(i = 0; i < XXL; i++)

{

    a[i] = b[i] + 1;

    d[i] = у[i] -1;

}   a[i] = b[i] + 1;

Документация на компилятор icl утверждает: объединение циклов как будто бы поддерживается (см. главу «loop transformation» фирменного руководства), однако дизассемблирование показывает, что это не так. Остальные компиляторы объединение циклов также не выполняют.

Итого:

• msvc – не объединяет циклы.
• icl – не объединяет циклы.
• gcc – не объединяет циклы.

Разматывание циклов

Разматывание циклов (loop spreading) представляет собой разновидность шелушения, при котором «содранные» итерации упаковываются в самостоятельный цикл, что бывает полезным, например, при объединении двух циклов с «разнополыми» заголовками.

Рассмотрим следующий код:

Листинг 25. Два цикла с различным количеством итераций (неоптимизированный вариант)

for(i=0; i<n; i++;)

    a[i] = a[i] + c;

for(j=0; j<m; j++;)

    s[j] = s[j] + s[j+1];

Если n не равно m, полное объединение циклов i и j уже невозможно, но min(n,m) итераций мы все же можем объединить:

Листинг 26. Частичное объединение циклов путем «разматывания» (оптимизированный вариант)

for(i=0; i<min(n,m); i++;)

{

    a[i] = a[i] + c;

    s[i] = s[i] + s[i+1];

}

for(i = min(n,m); i<max(n,m); i++;)

    s[i] = s[i] + s[i+1];

Ни msvc, ни icl, ни gcc способностью к «разматыванию» циклов не обладают, однако это умеют делать, например, компиляторы от Hewlett-Packard.

Итого:

• msvc – не разматывает циклы.
• icl – не разматывает циклы.
• gcc – не разматывает циклы.

Расщепление циклов

Расщепление циклов (loop distribution, loop fission, loop splitting…) прямо противоположно их объединению. К такому трюку прибегают в тех случаях, когда оптимизируемый цикл содержит слишком много данных. Ассоциативность кэш-памяти первого уровня у большинства x86-процессоров равна четырем, реже – восьми, а это значит, что каждая обрабатываемая ячейка данных может претендовать лишь на одну из четырех (восьми) возможных кэш-линеек и если они к этому времени уже заняты ячейками остальных потоков, происходит их неизбежное вытеснение из кэша, многократно снижающее производительность.

Рассмотрим следующий пример:

Листинг 27. Неоптимизированный вариант

for(j = 0; j < n; j++)

{

    c[j] = 0;

    for(i = 0; i<m; i++)

           a[j][i] = a[j][i] + b[j][i] * c[j];

}

Чтобы сократить количество потоков данных, следует вынести выражение (c[j] = 0) в отдельный цикл, переписав код так:

Листинг 28. Оптимизированный вариант

for(j = 0; j < n; j++)

    c[j] = 0;

for(i=0; i<m; i++)

    for(j = 0; j < n; j++)

           a[j][i] = a[j][i] + b[j][i] * c[j];

Компилятор icl именно так и поступает, снимая это бремя с плеч программиста.

Остальные рассматриваемые компиляторы этой способностью, увы, не обладают.

Итого:

• msvc – не расщепляет циклы.
• icl – расщепляет циклы.
• gcc – не расщепляет циклы.

Нормализация циклов

Нормализованным называется цикл, начинающийся с нуля, и в каждой итерации увеличивающий свое значение на единицу, а приведение произвольного цикла к указанной форме называется его нормализацией (loop normalization). Принято считать, что на большинстве архитектур нормализованный цикл компилируется в более компактный и быстродействующий код, однако в отношении x86-процессоров это совсем не так, и более компактным оказывается цикл, стремящийся к нулю (см. раздел «Стремление циклов к нулю»). Тем не менее нормализация бывает полезной, например, при объединении двух циклов с различными заголовками. Если эти циклы предварительно нормализовать, тогда они будут отличаться друг от друга всего лишь числом итераций, а как объединять циклы с несовпадающим количеством итераций, мы уже знаем (см. раздел «Разматывание циклов»).

Возьмем произвольный цикл:

Листинг 29. Ненормализованный цикл

for (i = lower; i < upper; i+=(-incre))

{

    // тело цикла

}

В общем случае стратегия нормализации выглядит так:

Листинг 30. Нормализованный цикл

for (NCL = 0; i < (upper - lower + incre)/incre - 1; 1)

{

    i = incre*NLC + lower;

    // тело цикла

}

i =  incre * _max((upper - lower + incre)/incre, 0) + lower;

Легко показать, что нормализация дает выигрыш только на циклах с заранее известным количеством итераций, позволяющих вычислить значение выражения (upper  lower + incre)/incre еще на стадии компиляции.

Все три рассматриваемых компилятора поддерживают нормализацию циклов (см. раздел «loop normalization» в документации на icl и описание ключа -fivcanon компилятора gcc), но не всегда ею пользуются.

Рассмотрим следующий пример:

Листинг 31. Ненормализованный цикл

int i, x[10];

for(i=1; i<10; i++)

    x[i]=i-1;

Очевидно, что его можно нормализовать, избавляясь от операции вычитания в выражении (i-1):

Листинг 32. Нормализованный цикл

int i, x[10]; int *p; p = &x[1];

for(i=0; i<9; i++)

    p[i]=i;

Поразительно, но ни один из трех рассматриваемых компиляторов этого не делает, поэтому все они получают незачет.

Итого:

• msvc – нормализует некоторые циклы.
• icl – нормализует некоторые циклы.
• gcc – нормализует некоторые циклы.

Масштабирование циклов

Масштабированием (scaling) в общем случае называется умножение индекса массива на некоторое, как правило, целочисленное значение, например, x = a[4*i]. Идея масштабирования циклов заключается в выносе множителя в индуктивный инкремент счетчика цикла.

Допустим, исходный цикл выглядел так:

Листинг 33. Исходный цикл (неоптимизированный вариант)

for(i=0; i < XXL; i++)

    a[4*i]= b[i];

После масштабирования он приобретает следующий вид:

Листинг 34. Цикл после масштабирования (оптимизированный вариант)

for(i=0; i < 2*XXL; i+=2)

    a[i]= *b++;

В времена XT/AT такая оптимизация еще имела смысл, но начиная с 80386, в процессорах появилась аппаратная поддержка масштабирования на 2х, 4х, 8х и с некоторыми ограничениями на 3х, 5х и 9х, поэтому масштабировать такие циклы уже не нужно.

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

Итого:

• msvc – масштабирует некоторые циклы.
• icl – масштабирует некоторые циклы.
• gcс – масштабирует некоторые циклы.

Замена циклов с предусловием на циклы с постусловием

Циклы с предусловием (for, while) содержат по меньшей мере на одно ветвление больше, чем аналогичные им циклы с постусловием. Как нетрудно сообразить – в конце цикла с предусловием находится безусловный переход, возвращающий управление в начало, а в цикле с постусловием передача управления по «совместительству» еще выполняет и проверку условия.

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

Итого:

• msvc – заменяет циклы с предусловием на циклы с постусловием.
• icl – заменяет циклы с предусловием на циклы с постусловием.
• gcc – заменяет циклы с предусловием на циклы с постусловием.

Стремление циклов к нулю

На большинстве процессорных архитектур инструкция декремента (уменьшения регистра на единицу) автоматически взводит специальный флаг при достижении нуля, поэтому, цикл, стремящийся к нулю (incrementing by zero, хотя правильнее было назвать его decrementing by zero), намного выгоден как с точки зрения компактности, так и с точки зрения быстродействия. Операция инкремента при достижении нужного нам значения (n) никаких флагов, конечно, не возводит, поэтому приходится тратить процессорное время на операцию сравнения.

Рассмотрим следующий код:

Листинг 35. Неоптимизированный вариант

for(i=0; i<n; i++) printf("hello!\n");

Поскольку никаких обращений к счетчику цикла здесь нет, его можно развернуть в обратном направлении. Это легко. А вот пример посложнее:

Листинг 36. Неоптимизированный вариант

for(i=0;i<n; i++) sum+=a[i];

В этом случае за трансформацию цикла приходится расплачиваться усложнением его тела, однако несмотря на это скорость выполнения все равно возрастает:

Листинг 37. Оптимизированный вариант

i=n; do

{

    sum+=*a;

    a++;

} while(--i);

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

Итого:

• msvc – всегда устремляет циклы к нулю.
• icl – никогда не устремляет циклы к нулю.
• gcc – устремляет некоторые циклы к нулю.

Отказ от branch-count-reg

Многие микропроцессоры имеют специальную команду: «уменьши-регистр-на-единицу-и-ветвись-если-нуль» (branch-count-reg). На x86-процессорах этим занимается LOOP, часто встречающаяся в ассемблерных вставках начинающих программистов, но практически никогда в коде, сгенерированном компилятором. И вовсе не потому, что компилятор «тупой», а потому, что эта инструкция медленная, хотя и компактная.

Компиляторы msvc и icl никогда ее не используют, а gcc предоставляет специальный ключ -fbranch-count-reg, предписывающий выбирать LOOP вместо DEC reg/JNZ begin_loop, (см. раздел «Стремление циклов к нулю»), правда, до машинного она все равно не доживает и уничтожается оптимизатором.

Итого:

• msvc – не использует branch-count-reg.
• icl – не использует branch-count-reg.
• gcc – не использует branch-count-reg.

Вынос инвариантных ветвлений

Ветвления, инвариантные по отношению к циклу, могут быть вынесены за его пределы путем расщепления одного цикла на два или более. Размеры кода при этом возрастают, но и производительность увеличивается (конечно, при условии, что цикл влезает в кэш).

Покажем это на следующем примере:

Листинг 38. Цикл с инвариантным ветвлением (неоптимизированный вариант)

for (i = 0; i < n; i++)

{

    for (j = 0; j < n; j++)

    {

           if (flag < 0x669) a[i][j]=i+j; else a[i][j]=0;

    }

}

Поскольку ветвление if (n < 0x669) инвариантно по отношению к циклу j, мы от него избавляемся:

Листинг 39. Оптимизированный вариант

if (flag < 0x669)

    for (i = 0; i < n; i++)

           for (j = 0; j < n; j++)

                 a[i][j]=i+j;

else

    for (i = 0; i < n; i++)

           for (j = 0; j < n; j++)

                 a[i][j]=0;

На суперкомпьютерных компиляторах такая техника оптимизации используется уже давно и называется loop promotion, loop interchange или loop unswitching, но на PC она впервые появилась только в последней версии компилятора gcc. Этим заведует ключ -funswitch-loops (задействовать вынос инвариантных ветвлений), max-unswitch-insns (максимальное количество инструкций, которое может иметь «расщепляемый» цикл) и max-unswitch-level (максимальное количество инвариантных ветвлений, которые может иметь «расщепляемый цикл»).

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

Итого:

• msvc – не выносит инвариантные ветвления.
• icl – не выносит инвариантные ветвления.
• gcc – выносит инвариантные ветвления, начиная с версии 3.4.3.

Ротация ветвлений

Бесконечные циклы с выходом по break могут быть преобразованы в конечные циклы с постусловием. При этом тело цикла как бы прокручивается, чтобы оператор break переместился на место while(1), а сам while(1) сомкнулся с оператором do и «коллапсировал».

Продемонстрируем это на следующем примере:

Листинг 40. Неоптимизированный вариант

do

{

    printf("1й оператор цикла\n");

    if (--a<0) break;

    printf("2й оператор цикла\n");

} while(1);

После ротации ветвлений наш код будет выглядеть так:

Листинг 41. Оптимизированный вариант

// дублируем операторы цикла, расположенные до break

printf("1-й оператор цикла\n");

a--;

// а должен ли вообще выполняться остаток цикла?

if (a>=0)

{

    a++;

    do

    {

           // после трансформации второй оператор стал первым

           printf("2-й оператор\n");

           // …а первый оператор — вторым

           printf("1-й оператор цикла\n");

    } while(–-a<0); // сюда попало условие из if - break

}

Из всех трех рассматриваемых компиляторов удалять лишние ветвления умеет лишь один msvc.

Итого:

• msvc – выполняет ротацию ветвлений.
• icl – не выполняет ротацию ветвлений.
• gcc – не выполняет ротацию ветвлений.

Упорядочение обращений к памяти

При обращении к одной-единственной ячейке памяти в кэш первого уровня загружается целая строка, длина которой в зависимости от типа процессора варьируется от 32 до 128 или даже 256 байт, поэтому большие массивы выгоднее всего обрабатывать по строкам, а не по столбцам. К сожалению, многие программисты об этом забывают и отдуваться приходится компилятору:

Листинг 42. Обработка массивов по столбцам (неоптимизированный вариант)

for(j=0;j<m;j++)

    for(i=0;i<n;i++)

           a[i][j] = b[i][j] + c[i][j];

Здесь три массива обрабатываются по столбцам, что крайне непроизводительно и для достижения наивысшей эффективности циклы i и j следует поменять местами. Устоявшегося названия у данной методики оптимизации нет, и в каждом источнике она называется по-разному: loop permutation/interchange/reversing, rearranging array dimensions и т. д. Как бы там ни было, результирующий код выглядит так:

Листинг 43. Обработка массивов по столбцам (оптимизированный вариант)

for(i=0;i<n;i++)

    for(j=0;j<m;j++)

           a[i][j] = b[i][j] + c[i][j];

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

Листинг 44. Сложный случай обработки данных по столбцам

for (i=0; i<n; i++)

    for (j=0; j<n; j++)

           for (k=0; k<n; k++)

                 a[j][i] = a[j][i] + b[k][i] * c[j][k];

А вот компиляторы от Hewlett-Packard оптимизируют этот цикл так (хвост цикла для простоты не показан):

Листинг 45. Оптимизированный вариант с разворотом на 4 итерации (обратите внимание, какой цикл был развернут!)

for(i=0; i<n; i+=4)

{

    for (j=0; j<n; j++)

    {

           for (k=0; k<n; k++)

           {

                 a[j][i] = a[j][i] + b[k][i] * c[j][k];

                 a[j][i+1] = a[j][i+1] + b[k][i+1] * c[j][k];

                 a[j][i+2] = a[j][i+2] + b[k][i+2] * c[j][k];

                 a[j][i+3] = a[j][i+3] + b[k][i+3] * c[j][k];

           }

    }

}

Оптимизатор скомбинировал сразу три методики: разворот, объединение и переупорядочение циклов, благодаря чему скорость выполнения значительно возросла. К сожалению, еще долгое время PC-программистам придется оптимизировать свои программы самостоятельно, хотя стремительное совершенствование gcc дает робкую надежду на изменение ситуации.

Итого:

• msvc – частично упорядочивает обращения к памяти.
• icl – частично упорядочивает обращения к памяти.
• gcc – частично упорядочивает обращения к памяти.

Таблица1. Свободная таблица качества оптимизации

Компилятор Действие	Microsoft Visual C++ 6	Intel C++ 8.0	GCC 3.3.4
Выравнивание циклов	Не выравнивает	Не выравнивает	Выравнивает по границе степени двойки
Разворот циклов	Не разворачивает	Разворачивает циклы без ветвлений с переменным и постоянным количеством итераций	Разворачивает циклы с постоянным количеством итераций
Шелушение циклов	Не шелушит	Шелушит	Шелушит
Векторизация циклов	Не векторизует	Векторизует	Векторизует, начиная с версии 3.4.3
Автопараллелизм	Не поддерживает	Поддерживает	Не поддерживает
Программная конвейеризация	Не поддерживает	Не поддерживает	Частично поддерживает
Предвычисление индуктивных циклов	Предвычисляет простые циклы	Не предвычисляет	Не предвычисляет
Разбивка длинных цепочек зависимостей	Не разбивает	Не разбивает	Разбивает, начиная с версии 4.0.0
Устранение хвостовой рекурсии	Устраняет	Не устраняет	Устраняет
Объединение циклов	Не объединяет	Не объединяет	Не объединяет
Разматывание циклов	Не поддерживает	Не поддерживает	Не поддерживает
Расщепление циклов	Не расщепляет	Расщепляет	Не расщепляет
Нормализация циклов	Нормализует некоторые циклы	Нормализует некоторые циклы	Нормализует некоторые циклы
Масштабирование циклов	Масштабирует некоторые циклы	Масштабирует некоторые циклы	Масштабирует некоторые циклы
Замена циклов с предусловием на циклы с постусловием	Заменяет	Заменяет	Заменяет
Стремление циклов к нулю	Всегда устремляет циклы к нулю	Никогда не устремляет циклы к нулю	Стремит устремляет циклы к нулю
Branch-count-reg	Не использует	Не использует	Не использует
Вынос инвариантных ветвлений	Не выносит	Не выносит	Выносит, начиная с версии 3.4.3
Ротация ветвлений	Выполняет	Не выполняет	Не выполняет
Упорядочивание обращение к памяти	Частично упорядочивает обращения к памяти	Частично упорядочивает обращения к памяти	Частично упорядочивает обращения к памяти

Заключение

Прогресс не стоит на месте, и со времени появления msvc компиляторы сделали большой шаг вперед. Особенно порадовал gcc 4.0.0 с его новым оптимизатором циклов, который намного превосходит icl и msvc вместе взятые. Тем не менее до совершенства ему еще далеко. Некоторые техники, присутствующие еще в msvc, в нем не реализованы (например, ротация ветвлений), не говоря уже про «серьезные» компиляторы от Hewlett-Packard. Так что на компилятор надейся, а сам не плошай!