оптимизированный вариант
Компилятор 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: шелушит
оптимизированный вариант — четыре потока данных на итерацию
Все три рассматриваемых компилятора поддерживают данную стратегию оптимизацию.
* msvc: фальцует
* gcc: фальцует
* icl: фальцует
оптимизированный вариант, только одна проверка
Из всех трех компиляторов, совмещать проверки умет только icl, да и то не всегда.
пример с лишними обращениями к памяти, от которых можно избавиться вручную
Компилятор не может (не имеет права) выносить переменную dst за пределы цикла и обращения к памяти будут происходить на каждой итерации. Чтобы этого избежать, программист должен переписать код так:
f(char *x, int *dst, int n)
{
int i,t =0;
for
(i=0;i<n;i++) t+=x[i]; // сохранение суммы во временной переменной
*dst+=t; // запись конечного результата в память
}
оптимизированный вариант
Разумеется, оператор goto необязательно должен присутствовать в программном коде в явном виде и он вполне можно быть "растворен" в цикле:
while(a) // lab_1: if (a) goto lab_4
{
while(b) // lab_2: if (b) goto lab_3 /* переход на безусловный переход */
{
/* код цикла */
} // goto lab_2
} // lab_3: goto lab_1
// lab_4:
тот же цикл, записанный в векторной нотации
Старшие представители процессоров Pentium могут обрабатывать до 8 порций данных параллельно, и если N превышает это число, приходится поступать так:
// обрабатываем первые (N-N%VF) ячеек векторным способом
// VF –кол-во порций данных, которые процессор будет обрабатывать за один раз
for (i=0; i<XXL; i+=VF)
a[i:i+VF] = a[i:i+VF] + b[i:i+VF];
// обрабатываем оставшийся "хвост" обычным способом
for (XXL -= VF ; i < XXL; i++)
a[i] = a[i] + b[i];
цикл после векторизации
Однако, это методика срабатывает далеко не всегда. Вот пример цикла, который нельзя векторизовать:
for (i=1; i<XXL; i++)
a[i] = a[i-1] + b[i];
не оптимизированный вариант
После оптимизации этот код будет выглядеть так:
while(a) // lab_1: if (a) goto lab_4
{
while(b) // lab_2: if (b) goto lab_1 /* оптимизировано */
{
/* код цикла */
} // goto lab_2
} // lab_3: goto lab_1
// lab_4:
оптимизированный вариант
Аналогичным способом осуществляется и оптимизация условных/безусловных переходов, указывающих на другой условный переход. Вот, посмотрите:
jmp lab_1 ; // переход на условный переход
…
lab_1: jnz lab_2
не оптимизированный вариант
jnz lab_2 ; // оптимизировано
…
lab_1: jnz lab_2
нерптимизированный вариант
Поскольку зависимость по данным отсутствует, цикл можно разбить на два. Первый будет обрабатывать ячейки от 0 до XXL/2, а второй — от XXL/2 до XXL. Тогда на двухпроцессорной машине скорость выполнения цикла практически удвоится.
/* поток 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];
размножение переменной a устраняет зависимость по данным
Простейшие зависимости по данным процессоры от Pentium Pro и выше устраняют самостоятельно. Ручное размножение переменных здесь только вредит — количество регистров общего назначения ограничено и компиляторам их катастрофически не хватает. Но это только снаружи. Внутри процессора содержится здоровый регистровый файл, автоматически "расщепляющий" регистры по мере необходимости.
Сложные зависимости по данным на микро-уровне уже неразрешимы и чтобы справится с ними, необходимо иметь доступ к исходному тексту программы. Компилятор icl устраняет большинство зависимостей, остальные же оставляют все как есть.
оптимизированный вариант
Компилятор icl – единственный из всех трех, способный на "параллелизацию" циклов. Чтобы ее задействовать используйте ключ –parallel, только помните, что при выполнении кода на однопроцессорных машинах, оптимизация дает обратный эффект (накладные расходы на организацию потоков дают о себе знать).
* msvc: авто-параллелизм не поддерживается
* icl: авто-параллелизм поддерживается
* gcc: авто-параллелизм не поддерживается
Заметим, что в силу ограниченной "дальнобойности" условных переходов, в некоторых случаях длину цепочки приходится не только уменьшать, но и увеличивать, прибегая к следующему трюку:
jz far_far_away jnz next_lab
———трансформация—————>
jmp far_far_away
next_lab:
трансформация условных переходов, до которых процессор не может "дотянуться"
Условный или безусловный переход, указывающий на выход из функции, всеми тремя компиляторами заменяется на непосредственный выход из функции, при условии, что код эпилог достаточно мал и накладные расходы на его дублирование невелики:
f(int a, int b)
{
while(a--)
{
if (a == b) break; // условный переход на return a;
}
return a;
}
не оптимизированный вариант
f(int a, int b)
{
while(a--)
{
if (a == b) return a; //непосредственный return a;
}
return a;
}
оптимизированный вариант — счетчик цикла совмещен с указателем на массив
Эксперимент показывает, что ни vc, ни gcс не выполняют регистровых реассоциаций ни в сложных, ни даже в простейших случаях. С приведенным примером справился один лишь icl, впрочем, это его все равно не спасает и vc распределяет регистры намного лучше.
индуктивный цикл после оптимизации
Компилятор msvc всегда пытаются предычислить значение индуктивного цикла, однако, далеко не всегда это ему удается, особенно если индуктивное выражение представляет собой сложную математическую формулу. Два остальных компилятора оставляют индуктивные циклы такими какие они есть, даже не пытаясь их оптимизировать!
* msvc: предвычисляет некоторые индуктивные циклы
* icl: не предвычисляет индуктивные циклы
* gcc: не предвычисляет индуктивные циклы
неоптимизированный кандидат на алгебраическое упрощение
Компилятор vc выбрасывает лишь часть операций, но чем он руководствуется при этом— непонятно. Оптимизатор легко раскрывает скобки ((cs.y*3) – cs.y), но дальше этого он не идет, послушно выполняя бессмысленную операцию (cs.y*2 / 2). И тут же, словно одумавшись, принудительно обнуляет регистр EAX, возвращая ноль. Судя по всему, результат выражения вычисляется компилятором еще на стадии трансляции, но он словно не решается им воспользоваться:
mov eax, [esp+arg_0]
; загрузка n
add eax, eax
; n *= 2; ( без учета знака)
cdq
; преобразовать двойное знаковое слово
sub eax, edx
; учесть знак
sar eax, 1
; n /= 2;
xor eax, eax
; n = 0;
оптимизированный вариант
Оператор goto необязательно должен присутствовать в тексте явно, он вполне может быть частью do/while/break/continue. Вот, например:
while(1)
{
if
(a==0x66) break; // условный переход
a=a+rand();
}; // скрытый безусловный переход на начало цикла
загадочный код, сгенерированный компилятором vc
Компилятор icl выбрасывает мусорный код полностью, генерируя честный XOR EAX,EAX, а вот gcc вообще не выполняет никаких упрощений! Однако, могущество icl очень переменчиво. Возьмем такой пример:
main(int n, char *v)
{
int x,y;
x = n-n; y = n+n;
return x+y-2*n+(n/n);
}
индуктивный цикл после оптимизации
Расплатой за отказ от индукции становится появление "лишней" инструкции умножения, однако, накладные расходы на ее выполнение с лихвой окупаются конвейеризацией (а при желании и векторизацией!) цикла. Такая техника оптимизации называется "разбивка длинных цепочек зависимостей" (breaks long dependency chains) и реализована только в последних версиях gcc (за это отвечает ключ -fsplit-ivs-in-unroller), а все остальные рассматриваемые компиляторы на это, увы, не способны.
* msvc: не разбивает длинные цепочки зависимостей
* icl: не разбивает длинные цепочки зависимостей
* gcc: разбивает длинные цепочки зависимостей
не оптимизированный вариант, 2 ветвления
if (a!=0x66) // "сдирание" одной итерации цикла
do{
a=a+rand();
}while(a!=0x66);
// инвертируем переход, только одно ветвление
хвостовая рекурсия после оптимизации
Компиляторы msvc и gcc всегда разворачивают хвостовую рекурсию в цикл, а вот icl этого делать не умеет.
msvc: устраняет хвостовую рекурсию
icl: не устраняет хвостовую рекурсию
gcc: устраняет хвостовую рекурсию
сравнение двух чисел на языке высокого уровня
Дизассемблирование показывает, что компилятору msvc потребовалось целых два сравнения, а вот icl было достаточно и одного. Компилятор gcc не заметил подвоха и честно выполнил все три сравнения.
циклы после объединения (оптимизированный вариант)
А вот более сложный пример:
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 одну итерацию:
for(i = 0; i < XXL; i++)
{
a[i] = b[i] + 1;
d[i] = у[i] -1;
} a[i] = b[i] + 1;
не оптимизированный вариант с ветвлениями
может быть переписан так:
Is16vec4 a, b, c
c
= select_gt(a, b, a, b);
// функция векторного поиска максимума без ветвлений
полностью оптимизированный вариант (ручная оптимизация)
Компилятор vc успешно удалил лишнее выражение (i*n), избавившись от одного умножения и сгенерировал довольно туманный и тормознутый код, не оправдывающий возлагаемых на него надежд. Аналогичным образом поступил и gcc. Его основной конкурент — icl хоть и сократил количество умножений наполовину, сгенерировал очень громоздкий код, сводящий на нет весь выигрыш от оптимизации. Короче говоря, с предложенным примером в полной мере не справился никто и для достижения наивысшей производительности программист должен выполнять все преобразования самостоятельно. По крайней мере необходимо добиться, чтобы все совместно используемые выражения в исходном тексте присутствовали в явном виде.
А как обстоят дела с удалением частичной избыточности? Добавим в нашу программу ветвление и перекомпилируем пример:
if (n) a = x*y + n; else a = x*y - n;
случай удаления частичной избыточности
Компилятор vc уже не справляется и генерирует две операции умножения, вместо одной. А вот компиляторы icl и gcc поступают правильно, вычисляя выражение (x*y) всего один раз.
устранение ветвлений путем использования функции select_gt библиотеки классов Intel SIMD
Естественно, такой код непереносим и на других компиляторах он работать не будет, поэтому, прежде чем подсаживаться на Intel следует все взвесить и тщательно обдумать. Тем более, что альтернативные мультимедийные библиотеки имеются и на других компиляторах.
частичное объединение циклов путем "трепки" (оптимизированный вариант)
Ни msvc, ни icl, ни gcc способностью к "трепке" циклов не обладают, однако, это умеют делать, например, компиляторы от Hewlett-Packard.
* msvc: не треплет циклы
* icl: не треплет циклы
* gcc: не треплет циклы
дизассемблерный листинг оптимизированного варианта оператора switch
Создавать таблицы переходов умеют все три рассматриваемых компилятора, даже если элементы прогрессии некоторым образом перемешаны:
switch (a)
{
case
11 : /* код обработчика */ break;
case
2 : /* код обработчика */ break;
case
13 : /* код обработчика */ break;
case
4 : /* код обработчика */ break;
case
15 : /* код обработчика */ break;
case
6 : /* код обработчика */ break;
case
17 : /* код обработчика */ break;
case
8 : /* код обработчика */ break;
case
19 : /* код обработчика */ break;
case
10 : /* код обработчика */ break;
case
21 : /* код обработчика */ break;
}
не оптимизированный
Если один или один или несколько элементов прогрессии отсутствуют, соответствующие им значения дополняются фиктивными переходниками к default-обработчику. Таблица переходов от этого, конечно, распухает, однако, на скорости выполнения оператора switch это практически никак не отображается.
Однако, при достижении некоторой пороговой величины "разрежения", таблица переходов внезапно трансформируется в двоичное/троичное дерево. Компилятор msvc единственный из всех трех, способный комбинировать таблицы переходов с логическими деревьями. Разряженные участки, с далеко отстоящими друг от друга значениями, монтируется в виде дерева, а густо населенные области упаковываются в таблицы переходов.
Вернемся к листингу 26. Значения 9, 11 22, 74, 666, 777 упорядочиваются в виде дерева, а 0, 3, 4, 7, 9 ложатся в таблицу переходов, благодаря чему достигается предельно высокая скорость выполнения, далеко опережающая конкурентов.
оптимизированный вариант
Компилятор icl, кстати говоря, именно так и поступает, снимая это бремя с плеч программиста. Остальные рассматриваемые компиляторы этой способностью, увы, не обладают.
* msvc: не расщепляет циклы
* icl: расщепляет циклы
* gcc: не расщепляет циклы
нормализованный цикл
Легко показать, что нормализация дает выигрыш только на циклах с заранее известным количеством итераций, позволяющих вычислить значение выражения (upper ? lower + incre)/incre еще на стадии компиляции.
Все три рассматриваемых компилятора поддерживают нормализацию циклов (см. раздел loop normalization в документации на icl и описание ключа –fivcanon компилятора gcc), но не всегда ею пользуются.
Рассмотрим следующий пример:
int i, x[0х10];
for(i=1; i<0х10; i++)
x[i]=i-1;
ненормализованный цикл
Очевидно, что его можно нормализовать, одним махом избавившись от нескольких "лишних" инструкций (кстати говоря, XOR reg,reg — обнуление регистра reg — намного более компактно, чем MOV reg, const — инициализация регистра константой):
int i, x[10]; int *p; p = &x[1];
for(i=0; i<9; i++)
p[i]=i;
нормализованный цикл
Поразительно, но ни один из трех рассматриваемых компиляторов этого не делает, поэтому все они получают незачет.
* msvc: нормализует некоторые циклы
* icl: нормализует некоторые циклы
* gcc: нормализует некоторые циклы
цикл после масштабирования (оптимизированный вариант)
В времена XT/AT такая оптимизация еще имела смысл, но начиная с 80386, в процессорах появилась аппаратная поддержка масштабирования на 2х, 4х, 8х и с некоторыми ограничениями на 3х, 5х и 9х, поэтому масштабировать такие циклы уже не нужно.
Масштабирование поддерживают все три рассматриваемых компилятора, но пользуются им довольно неумело, оставляя цикл несмаштабированным даже тогда, когда это ему явно не помешало бы.
* msvc: масштабирует некоторые циклы
* icl: масштабирует некоторые циклы
* icl: масштабирует некоторые циклы
не оптимизированный вариант
Поскольку, никаких обращений к счетчику цикла здесь нет, его можно развернуть в обратном направлении. Это легко. А вот пример посложнее:
for(i=0;i<n; i++) sum+=a[i];
не оптимизированный вариант
В этом случае, за трансформацию цикла приходится расплачиваться усложнением его тела, однако, выигрыш по-прежнему остается на нашей стороне:
i=n; do
{
sum+=*a;
a++;
} while(--i);
оптимизированный вариант
Компилятор msvc всегда стремится генерировать циклы, стремящиеся к нулю, icl этого не делает вообще, а gcc прибегает к трансформации циклов только в тех в некоторых, наиболее очевидных случаях. В частности, он избегает трогать циклы, содержащие ссылки на память.
* msvc: всегда стремит циклы к нулю
* icl: никогда не стремит циклы к нулю
* gcc: стремит некоторые циклы к нулю
цикл с инвариантным ветвлением (не оптимизированный вариант)
Поскольку, ветвление if (n < 0x669) инвариантно по отношению к циклу j, мы от него избавляемся:
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
оптимизированный вариант
Из всех трех рассматриваемых компиляторов удалять лишние ветвления умеет лишь один лишь msvc.
* msvc: выполняет ротацию ветвлений
* icl: не выполняет ротацию ветвлений
* gcc: не выполняет ротацию ветвлений
обработка массивов по столбцам (оптимизированный вариант)
Все три рассматриваемых компилятора поддерживают данную стратегию оптимизации, однако их интеллектуальные способности очень ограничены и со следующим примером не справился ни один.
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 оптимизируют этот цикл так (хвост цикла для упрощения понимания не показан):
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: частично упорядочивает обращения к памяти
Масштабирование циклов
Масштабированием (scaling) в общем случае называется умножение индекса массива на некоторое, как правило, целочисленное значение, например, x= a[4*i]. Идея масштабирования циклов заключается в выносе множителя в индуктивный инкремент счетчика цикла.
Допустим, исходный цикл выглядел так:
for(i=0; i < XXL; i++)
a[4*i]= b[i];
>>> Мини-врезка советы
* избегайте использования глобальных и статических переменных — локальные переменные намного проще оптимизируются;
* не используйте переменные, там где можно использовать константы;
* везде используйте беззнаковые переменные где это только возможно, они намного легче оптимизируются, особенно в тех случаях, когда компилятор пытается избавиться от ветвлений;
* заменяйте int a; if ((a >= 0) && (a < MAX)) на if ((unsigned int)a < MAX), — последняя конструкция на одно ветвление короче;
* ветвление с проверкой на нуль оптимизируется намного проще, чем на любое другое значение;
* конструкции типа x = (flag?sin:cos)(y) не избавляют от ветвлений, но сокращают объем кодирования;
* не пренебрегайте оператором goto – зачастую он позволяет проектировать более компактный и элегантный код;
Нормализация циклов
Нормализованным называется цикл, начинающийся с нуля, и в каждой итерации увеличивающий свое значение на единицу, а приведение произвольного цикла к указанной форме называется его нормализацией (loopnormalization). Принято считать, что на большинстве архитектур нормализованный цикл компилируется в более компактный и быстродействующий код, однако, в отношении x86-процессоров это совсем не так и более компактным оказывается цикл, стремящийся к нулю (см. "стремление циклов к нулю"). Тем не менее, нормализация бывает полезной, например, при объединении двух циклов с различными заголовками. Если эти циклы предварительно нормализовать, тогда они будут отличаться друг от друга всего лишь числом итераций, а как объединять циклы с несовпадающим количеством итераций мы уже знаем (см. "трепание циклов").
Возьмем произвольный цикл:
for (i = lower; i < upper; i+=(-incre))
{
// тело цикла
}
