Авто-параллелизм
Многопроцессорные машины на рабочем столе это не утопия, а объективная данность и с каждым годом их количество будет только расти. В операционных системах семейства LINUX многозначность заканчивается на уровне потоков (в старых ядрах — процессах). Всякий поток в каждый момент времени может выполняться только на одном процессоре. Программы, состоящие целиком из одного потока, на многопроцессорной машине исполняются с той же скоростью, что и на однопроцессорной.
Некоторые компиляторы автоматически разбивают большие (с их точки зрения) циклы на несколько циклов меньшего размера, помещая каждый из них в свой поток. Такая техника оптимизации называется авто-параллелизмом (auto-parallelization). Продемонстрируем ее на следующем примере:
for (i=0; i<XXL; i++)
a[i] = a[i] + b[i] * c[i];
Балансировка логического древа
Если отвлечься от устоявшейся идиомы "оператор SWITCH дает специальный способ выбора одного из многих вариантов, который заключается в проверке совпадения значения данного выражения с одной из заданных констант в соответствующем ветвлении", легко показать, что switch представляет собой завуалированный оператор поиска соответствующего case-значения.
Последовательный перебор всех вариантов, соответствующий тривиальному линейному поиску— занятие порочное и крайне неэффективное. Допустим, наш оператор switch выглядит так:
switch (a)
{
case
98 : /* код обработчика */ break;
case
4 : /* код обработчика */ break;
case
3 : /* код обработчика */ break;
case
9 : /* код обработчика */ break;
case
22 : /* код обработчика */ break;
case
0 : /* код обработчика */ break;
case
11 : /* код обработчика */ break;
case
666: /* код обработчика */ break;
case
96 : /* код обработчика */ break;
case
777: /* код обработчика */ break;
case
7 : /* код обработчика */ break;
}
Частичное вычисление условий
"Летят два крокодила— один квадратный, другой тоже на север" — вот хороший пример техники быстрого булевского вычисления (оно же "частичное вычисление условий", "Partial evaluation of test conditions" или "short-circuiting"). Собственно, ничего "быстрого" в нем нет. Если первое из нескольких условий, связанных оператором AND, ложно (где видели квадратных крокодилов?), остальные уже не вычисляются. Соответственно, если первое из нескольких условий, связанных оператором OR, истинно, вычислять остальные нет нужды.
Кстати говоря, это отнюдь не свойство оптимизатора (как утверждают некоторые рекламные букеты), а требование языка, без которого ветвления вида: if (x && (y/x)) были бы невозможны. Все три рассматриваемых компилятора, поддерживают быстрое булево вычисление.
if ((a == b) || (c == d))…
Фальцевание циклов
Фальцевание циклов (fold loops) внешне очень похоже на разворот, но преследует совсем другие цели, а именно: увеличение количества потоков данных на одну итерацию. Чем выше плотность (strength) потоков, тем выше параллелизм обработки данных, а, значит, и скорость выполнения цикла.
Рассмотрим следующий пример:
for(i=0; i<XXL; i++)
sum += a[i];
Использование подвыражений
Хорошие оптимизаторы никогда не вычисляют значение одного и того же выражения дважды. Рассмотрим следующий пример:
a = x*y + n;
b
= x*y - n; // выражение (x*y) уже встречалось! и x,y с тех пор не менялись!
Избавление от ветвлений
Теория утверждает, что любой вычислительный алгоритм можно развернуть в линейную конструкцию, заменив все ветвления математическими операциями (как правило, запутанными и громоздкими).
Рассмотрим функцию поиска максимума среди двух целых чисел: "((a>b)?a:b)", для наглядности записанную так: "if(a<b) a=b;". Как избавиться от ветвления? В этом нам поможет машинная команда SBB, реализующая вычитание с заемом. На языке ассемблера это могло бы выглядеть, например, так:
SUB b, a
; отнять от содержимого 'b' значение 'a', записав результат в 'b'
; если a > b, то процессор установит флаг заема в единицу
SBB c, c
; отнять от содержимого 'c' значение 'c' с учетом флага заема,
; записав результат обратно в 'c' ('c' - временная переменная)
; Если a <= b, то флаг заема сброшен, и 'c' будет равно 0,
; Если a > b, то флаг заема установлен и 'c' будет равно -1.
AND c, b
; выполнить битовую операцию (c & b), записав результат в 'c'
; Если a <= b, то флаг заема равен нулю, 'c' равно 0,
; значит, с =(c & b) == 0, в противном случае: c == b - a
;
ADD a, c
; выполнить сложение содержимого 'a' со значением 'c', записав
; результат в 'a'.
; если a <= b, то c = 0 и a = a
; если a > b, то c = b - a, и a = a + (b-a) == b
Константная подстановка в функциях
Если все аргументы функции — константы, и она не имеет никаких побочных эффектов типа модификации глобальных/статических переменных, возвращаемое значение так же будет константой. Однако, компиляторы в подавляющем большинстве случаев об этом не догадываются. Поле зрения оптимизатора ограничено телом функции. "Сквозная" подстановка аргументов ("свертка функций") осуществима лишь в случае встраиваемых (inline) функций или глобального режима оптимизации.
Компилятор icl имеет специальный набор ключей –ip/-ipo, форсирующий глобальную оптимизацию в текущем файле и всех исходных текстах соответственно, что позволяет ему выполнять константную подстановку в следующем коде:
f1(int a, int b)
{
return a+b;
}
f2 ()
{
return f1(0x69, 0x96) + 0x666;
}
Константная подстановка в условиях
Переменные, использующиеся для "принятия решения" о ветвлении, в каждой из веток имеют вполне предсказуемые значения, зачастую являющееся константами. Код вида: if(a == 4) b = 2 * a;
может быть преобразован в: if (a == 4) b= 8, что компиляторы vc/gcc и осуществляют, избавляясь от лишней операции умножения, а вот icl этого сделать не догадывается.
цикл до разворота
// разворот цикла на 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);
кандидат на оптимизацию
Чтобы объединить оба цикла в один (см. "объединение циклов"), необходимо "содрать" с цикла j одну "лишнюю" итерацию:
for(i = 0; i < n; i++)
{
a[i] = b[i] + 1;
c[i] = d[i] - 1;
}
c[i] = d[i] - 1;
не оптимизированный вариант
Лишние проверки увеличивают размер кода и замедляют его выполнение (особенно если находятся глубоко в цикле), поэтому компилятор gcc поддерживает специальный ключ, ?fdelete-null-pointer-checks, вычищающий их из программы. Вся соль в том, что x86-процессоры (как и большинство других) на аппаратном уровне отслеживают обращения к нулевым указателям, автоматически выбрасывая исключение, если такое обращение действительно произошло. Поэтому, если проверке на "легитимность" указателя предшествует операция чтения/записи по этому указателю, эту проверку можно не выполнять. Допустим, наш указатель равен нулю, тогда исключение выпрыгнет при первом же обращении к нему (в нашем случае — при выполнении *p = 0x69) и до проверки дело просто не дойдет. Если же указатель не равен нулю — зачем его проверять?
Компиляторы msvc и icl такой техники оптимизации не поддерживают. Правда, в режиме глобальной оптимизации, icl может удалять несколько подряд идущих проверок (при встраивании функций это происходит достаточно часто), поскольку это является частным случаем техники удаления избыточных проверок, однако, ситуацию: "проверка/модификация-указателя/обращение-к-указателю/проверка", icl уже не осилит. А вот gcc справляется с ней без труда!
не оптимизированный вариант, 2 проверки
if (CPU_TYPE
== AMD) // только одна проверка
{
x = AMD_f1(y);
a = AMD_f2(b);
}
else
{
x = INTEL_f1(y);
a = INTEL_f2(b);
}
не оптимизированный вариант – один поток данных на итерацию
Чтобы сократить время выполнения цикла, необходимо увеличить количество потоков, переписав наш код так:
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];
пример программы с неиспользуемыми выражениями
Выражение (n+0x666) не используется, перекрываясь следующей операцией присвоения (2*n). Выражение (n-0x999) теряется при выходе из функции. Следовательно, наш код эквивалентен: return (n – 0x999).
Не всегда такая оптимизация проходит безболезненно. Компиляторы "забывают" о том, что некоторые вычисления имеют побочные эффект в виде выброса исключения. Код вида: a = b/c; a = d, можно оптимизировать в том, и только в том случае, если переменная c заведомо не равна нулю. Но ни один из трех рассматриваемых компиляторов такой проверки не выполняет! Забавно, но в сокращении арифметических выражений (о которых речь еще впереди), оптимизаторы ведут себя намного более осторожно — никто из них не рискует заменять сокращать выражение (a/a) 1 до единицы, даже если переменная a заведомо не равна нулю! Бардак в общем.
пример с лишними обращениями к памяти, от которых нельзя избавиться
Компилятор не может разместить содержимое *a во временной переменной, поскольку если ячейки *a и *b частично или полностью перекрываются, модификация ячейки *b приводит к неожиданному изменению ячейки *a!
Тоже самое относится и к следующему примеру:
f(char *x, int *dst, int n)
{
int i;
for (i = 0; i < n; i++) *dst += x[i];
}
цикл до векторизации
Используя общепринятую векторную нотацию, его можно переписать так:
a[0:N] = a[0:N] + b[0:N];
не оптимизированный вариант
goto lab_2 ; // сразу переходим к метке lab_2, минуя lab_1
….
lab_1: goto lab_2 ; // переход к метке lab_2
….
lab_2:
переменные a и b — лишнее
Очевидно, что его можно переписать как (2*n+1), избавившись сразу от двух переменных. Все три рассматриваемых компилятора именно так и поступают. (С технической точки зрения данный примем оптимизации является частным случаем более общего механизма алгебраического упрощения выражений и распределения регистров).
цикл который нельзя векторизовать
Поскольку, последующая ячейка (a[i]) вычисляется на основе предыдущей (a[i-1]) данные не могут обрабатываться параллельно.
Компилятор msvc не поддерживает векторизацию, а icl поддерживает, но задействует ее только в том случае, если указан ключ –ax. Компилятор gcc поддерживает векторизацию только начиная с версии 3.4.3, да и то если присутствует флаг -ftree-vectorize.
* msvc: не векторизует
* icl: векторизует
*gcc: векторизует начиная с версии 3.4.3
ложная зависимость по данным
Операции (x + y) и (i – j) могут быть выполнены одновременно, но чтобы сохранить результат вычислений, часть процессорных модулей вынуждена простаивать в ожидании пока не освободиться переменна a.
Чтобы устранить эту зависимость код необходимо переписать так:
a1 = x + y;
b
= a1 + 1; // b
зависит от a1
a2 = i - j;
c
= a2 – 1; // c
зависит от a2, но не зависит от a1
глубоко вложенный цикл чувствителен к качеству распределения переменных по регистрам
Компилятору vс регистров общего назначения уже не хватило и три переменных, обрабатываемых внешним циклом, "вылетели" в стек. Компилятору icl "уложился" в 14 (!) стековых переменных, 5 (!) из которых обрабатываются во внутреннем цикле! О какой производительности после этого можно говорить?! Второе место занял gcc – из 10 стековых переменных, 5 расположены во внутреннем цикле. А вы еще Microsoft ругаете…
неоптимизированный кандидат на регистровую ре-ассоциацию
Грамотный оптимизатор должен переписать его так:
int a[10][20][30];
void example (void)
{
int i, j, k;
register int (*p)[20][30];
for (k = 0; k < 10; k++)
for (j = 0; j < 10; j++)
for (p = (int (*)[20][30]) &a[0][j][k], i = 0; i < 10; i++)
*(p++[0][0]) = 1;
}
оптимизированный вариант
Такая техника оптимизации называется программной конвейеризацией (software pipelining) и из трех рассматриваемых компиляторов ею не обладает ни один. Только gcc робко пытается ослабить зависимость по sum, используя два регистра при развороте на четыре итерации. Остальные же компиляторы грузят все ячейки в один и тот же регистр, очевидно, руководствуясь принципом экономии. Регистров общего назначения всего семь и их постоянно не хватает. К сожалению, компилятор не отличает ситуацию действительно дефицита регистров от их избытка, вынуждая нас прибегать к ручной оптимизации.
* msvc: программная конвейеризация не поддерживается
* icl: программная конвейеризация не поддерживается
* gcc: программная конвейеризация частично поддерживается
индуктивный цикл до оптимизации
Очевидно, что конечное значение sum равно:
sum += XXL;
это так Microsoft нас учит писать программы
Неудивительно, что Windows так тормозит! Чтобы понять очевидное, парням из Microsoft потребовалось две операции умножения, две — деления и две — сложения. Итого: шесть операций. Проверим, сможет ли оптимизатор избавится от мусорных операций, предварительно переписав код так:
struct CS{int x;int y;};
main(int n, char *v)
{
int x,y; struct CS cs;
cs.y = n; cs.x = n;
y = ((cs.y * 3) - cs.y) / 2;
x = ((cs.x * 3) - cs.x) / 2;
return y - x;
}
не оптимизированный вариант
if (!x) goto lab_1; // одинарное ветвление
a=a*2;
b=a+1;
lab_1: c=a*10;
индуктивный цикл до оптимизации
Выражение (a[i]=x) не может быть выполнено до тех пор, пока не будет вычислено (x+=2), а оно в свою очередь должно дожидаться завершения предыдущей итерации. Индукция, однако! От нее можно избавится, вычисляя значение n'ой итерации на "лету":
for(i=0;i<XXL;i++)
{
a[i] = i*2 + x;
}
еще один кандидат на алгебраическое упрощение
Казалось бы, чего в нем сложного? Компиляторы vc и gcc выкидывают все кроме (n/n), оставляя его на тот случай, если переменная n окажется равной нулю. Поразительно, но icl выполняет все вычисления целиком, не производя никаких упрощений.
Таким образом, выполнение алгебраических упрощений — весьма капризная и непредсказуемая операция. Не надейтесь, что компилятор выполнит ее за вас!
хвостовая рекурсия до оптимизации
Вызов функции — достаточно "дорогостоящая" операция и от него лучше избавится. Это легко! Хвостовая рекурсия легко трансформируется в цикл. Смотрите:
for(i=0; i<n; i++)
result *= n;
кандидат на упрощение алгоритма
Для человека очевидно, что этот код можно записать так: (n*n). Мой любимый vc именно так и поступает, а вот icl с gcc накручивают циклы на кардан.
подвыражение (x*y) – общее
Чтобы избавиться от лишнего умножения этот код необходимо переписать так:
t
= x*y; // вычислить выражение (x*y) и запомнить результат
a
= t + n; // подстановка уже вычисленного значения
b
= t - n; // подстановка уже вычисленного значения
сравнение двух чисел на языке ассемблера
На языках высокого уровня все не так, и операцию сравнения приходится повторять несколько раз подряд, что не способствует ни компактности, ни производительности. Но, может быть, ситуацию исправить оптимизатор? Рассмотрим следующий код:
if (a < 0x69) printf("b");
if (a >
0x69) printf("g");
if (a == 0x69) printf("e");
циклы до объединения (не оптимизированный вариант)
Поскольку, заголовки обоих циклов абсолютно идентичны, нам достаточно лишь "коллективизировать" их содержимое:
for(i = 0; i < XXL; i++)
{
a[i] = b[i] + 1;
d[j] = у[j] -1;
}
оптимизированный вариант
Американцы называют это "удалением избыточности" (redundancy elimination) или "совместным использованием общих выражений" (Share Common Subexpressions). Полное удаление избыточности (оно же Full Redundancy Elimination или сокращенно FRE) предполагает, что совместное использование выражение происходит только в основных путях (path) выполнения программы. Ветвления при этом игнорируются. Частичное удаление избыточности (оно же Partial redundancy elimination или сокращенно PRE), охватывает весь программный код — как внутри ветвлений, так и снаружи. То есть, частичное удаление избыточности удаляет избыточность намного лучше, чем полное, хотя при полном программа компилируется чуть-чуть быстрее. Вот такая вот терминологическая путаница. Вся заковырка в том, что выражение "Partial redundancy elimination" переводится на русский языке отнюдь не как "частичное удаление избыточности" (хоть это и общепринятый вариант), а "удаление частичной избыточности", а "full redundancy elimination" – "удаление полной избыточности", что совсем не одно и тоже!
Все три рассматриваемых компилятора поддерживают совместное использование выражений. С приведенным примером они справляются легко. Но давайте усложним задачу, предложив им код подсчета суммы соседних элементов массива:
/* Sum neighbors of i,j */
up = a[(i-1)*n + j ];
down = a[(i+1)*n + j ];
left = a[i*n + j-1];
right = a[i*n + j+1];
sum = up + down + left + right;
поиск максимума среди двух целых чисел без использования ветвлений
Компилятор msvc поддерживает замену ветвлений математическими операциями, однако, использует несколько другую технику, отдавая предпочтение инструкции SETcc, устанавливающая переменную в единицу, если условие сс истинно. Как показывает практика, msvc оптимизирует только ветвления константного типа, т. е. "if (n >
m) a = 66; else a = 99;" еще оптимизируется, а "if (n >
m) a = x; else a = y;" уже нет.
Компилятор gcc, использующий инструкцию условного присвоения CMOVcc, оптимизирует все конструкции типа min, max, set flags, abs и т. д., что существенно увеличивает производительность, однако, требует как минимум Pentium Pro (инструкция SETcc работает и на Intel 80386). За это отвечают ключи -fif-conversion
и -fif-conversion2, которые на платформе Intel эквивалентны друг другу. (Вообще говоря, gcc поддерживает множество ключей, отвечающих за ликвидацию ветвлений, однако, на платформе Intel они лишены смысла, поскольку в лексиконе x86 процессоров просто нет соответствующих команд, это вам не PDP?11, элегантность которой остается непревзойденной до сих пор и которая имена специальную команду "пропустить следующую машинную инструкцию, если условие cc истинно/ложно", — вот где был простор для избавления от ветвлений!).
Компилятор icl – единственный из всех трех, кто не заменяет ветвления математическими операциями (что в свете активной агитации за команды SBB/CMOVcc, развернутой компаний Intel, выглядит довольно странно). Во всяком случае компилятор не делает этого явно и в качестве компенсации предлагает использовать инстриксы и функции мультимедийной библиотеки SIMD. В частности, цикл вида:
short a[4], b[4], c[4];
for (i=0; i<4; i++)
c[i] = a[i] >
b[i] ? a[i] : b[i];
пример с неочевидной разбивкой на подвыражения
Даже для человека не совсем очевидно, что его можно переписать так, сократив количество операций умножения с четырех до одного:
inj
= i*n + j; // однократное вычисление подвыражения
up
= val[inj - n]; // избавление от лишнего сложения
down
= val[inj + n]; // избавления от одного сложения и умножения
left
= val[inj - 1]; // избавление от одного сложения и умножения
right
= val[inj + 1]; // избавление от одного сложения и умножения
sum = up + down + left + right;
оптимизированный вариант
Документация на компилятор icl утверждает, объединение циклов как будто бы поддерживается (см. главу "loop transformation" фирменного руководство), однако, дизассемблирование показывает что это не так. Остальные компиляторы объединение циклов так же не выполняют и на это способен только компилятор от Hewlett-Packard и другие "серьезные" компиляторы для больших машин.
* msvc: не объединяет циклы
* icl: не объединяет циклы
* gcc: не объединяет циклы
два цикла с различным количеством итераций (не оптимизированный вариант)
Если n не равно m, полное объединение циклов i и j уже невозможно, но min(n,m) итераций мы все же можем объединить:
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];
не оптимизированный вариант оператора множественно выбора
Тогда соответствующее ему не оптимизированное логическое дерево будет достигать в высоту одиннадцати гнезд (см. рис. 1 слева). Причем, на левой ветке корневого гнезда окажется аж десять других гнезд, а на правой – вообще ни одного. Чтобы исправить "перекос", разрежем одну ветку на две и прицепим образовавшиеся половинки к новому гнезду, содержащему условие, определяющее: в какой из веток следует искать сравниваемую переменную. Например, левая ветка может содержать гнезда с четными значениями, а правая – с нечетными. Но это плохой критерий: четных и нечетных значений редко бывает поровну и вновь образуется перекос. Гораздо надежнее поступить так: берем наименьшее из всех значений и бросаем его в кучу А, затем берем наибольшее из всех значений и бросаем его в кучу B. Так повторяем до тех пор, пока не рассортируем все, имеющиеся значения. (см. рис. 1 справа)
Поскольку, оператор switch требует уникальности каждого значения, т. е. каждое число может встречаться лишь однажды, легко показать, что: а) в обеих кучах будет содержаться равное количество чисел (в худшем случае – в одной куче окажется на число больше);
б) все числа кучи A меньше наименьшего из чисел кучи B. Следовательно, достаточно выполнить только одно сравнение, чтобы определить: в какой из двух куч следует искать сравниваемое значения.
не оптимизированный
cmp eax, 0Bh ; switch 12 cases
; сравниваем a с 11
ja short loc_80483F5 ; default
; если a
>
11 выходим из оператора switch
;
jmp ds:off_804857C[eax*4] ; switch jump
; передаем управление соответствующему case-обработчику
; таким образом, мы имеем всего лишь одно сравнение и два ветвления
; // таблица смещений case-обработчиков
off_804857C dd offset loc_80483F5 ; DATA XREF: main+11^r
dd offset loc_80483E8 ; jump table for switch statement
dd offset loc_80483F9
dd offset loc_8048402
dd offset loc_804840B
dd offset loc_8048414
dd offset loc_804841D
dd offset loc_8048426
dd offset loc_804842F
dd offset loc_8048438
dd offset loc_8048441
dd offset loc_804844F
не оптимизированный вариант
Чтобы сократить количество потоков данных, следует вынести выражение (c[j] = 0) в отдельный цикл, переписав код так:
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];
ненормализованный цикл
В общем случае, стратегия нормализации выглядит так:
for (NCL = 0; i < (upper - lower + incre)/incre - 1; 1)
{
i = incre*NLC + lower;
// тело цикла
}
i = incre * _max((upper - lower + incre)/incre, 0) + lower;
исходный цикл (неоптимизированный вариант)
После масштабирования он приобретает следующий вид:
for(i=0; i < 2*XXL; i+=2)
a[i]= *b++;
неоптимизированный вариант
После ротации ветвлений наш код будет выглядеть так:
// дублируем операторы цикла, расположенные до break
printf("1й оператор цикла\n");
a--;
// а должен ли вообще выполнятся остаток цикла?
if (a>
=0)
{
a++;
do
{
// после трансформации второй оператор стал первым…
printf("2й оператор\n");
// …а первый оператор — вторым
printf("1й оператор цикла\n");
} while(–-a<0);
// сюда попало условие из if - break
}
обработка массивов по столбцам (не оптимизированный вариант)
Здесь три массива обрабатываются по столбцам, что крайне непроизводительно и для достижения наивысшей эффективности циклы i и j следует поменять местами. Устоявшегося названия у данной методики оптимизации нет и в каждом источнике она называется по-разному: loop permutation/interchange/reversing,
rearranging array dimensions и т.д. Как бы там ни было, результирующий код выглядит так:
for(i=0;i<n;i++)
for(j=0;j<m;j++)
a[i][j] = b[i][j] + c[i][j];
не оптимизированный кандидат в объединение констант
Компилятор vc "честно" генерирует все три строковые константы, а gcc и icl только две из них: "hello,world!\n"
и "i say hello, world!\n". На то, что первая строка совпадает с концом второй, ни один из компиляторов не обратил внимание. Это тем более печально, что язык Си не позволяет управлять размещением переменных в памяти и классический ассемблерный трюк с передачей указателя на середину строки здесь не проходит. Можно, конечно, поднатужиться и написать:
s[]="i say hello, world!\n"; // размещаем
строку в
памяти
printf(&s[6]);
// выводим подстроку
printf(&s[6]);
// выводим подстроку
printf(s);
// выводим всю строку целиком
частично оптимизированный вариант
Но ведь позицию подстроки в строке придется определять вручную, тупым подсчетом букв! Или использовать макросы, определяя длину строки с помощью sizeof, только… это же сколько кодить надо!
#define s1 "i say " // левая
половинка
#define s2 "hello, world!\n" // правая
половинка
char s[]=s1 s2; // конструируем всю строку целиком
printf(&s[sizeof(s1)-1]);
// автоматически вычисляем позицию
printf(&s[sizeof(s1)-1]);
// автоматически вычисляем позицию
printf(s);
// выводим всю строку
цикл после разворота (меньшей размер, большая скорость)
for(i=1; i<n;)
{
k += (n % i++) + \
(n % i++) + \
(n % i++) + \
(n % i++);
}
for(i=4; i<n;i++) k += (n % i);
цикл после разворота
Компилятор msvc вообще не разворачивает циклы и эту работу приходится выполнять вручную.
Компилятор icl разворачивает только циклы for во сценарию больший размер — большая скорость. Причем, циклы с заранее известным количеством итераций — for(a=0;a<const;a++) — где const <= 32 трансформируются в линейный код и цикл как таковой при этом исчезает (см "шелушение циклов"). Как следствие — размер программы существенно возрастает, а вместе с ним возрастает и риск "вылететь" за пределы кэша первого уровня, после чего производительность упадет так, что не поднимешь и домкратом. Если const >
32, цикл разворачивается на кол-во итераций, кратное const, но не более 10h, при этом компилятор учитывает количество инструкций в теле цикла — более компактные циклы разворачиваются на больше число итераций. Циклы, количество итераций которых компилятору неизвестно — for(a=0;a<n;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 — на ~4x (точное значение зависит от количества инструкций в теле цикла). Если внутри цикла присутствует одно или несколько ветвлений, при развороте они неизбежно дублируются, в результате чего производительность оказывается даже ниже, чем была до оптимизации! Циклы с неизвестным количеством итераций не разворачиваются вообще. Для тонкой настройки существуют ключи max-unrolled-insns
(максимальное кол- во инструкций, при котором цикл еще может быть развернут, и если он будет развернут это значение определяет величину разворота), max-average-unrolled-insns
(максимальное оценочное количество инструкций, которое цикл может иметь после разворота) и max-unroll-times (максимальная степень разворота). Разворот по всех случаях выполняется по сценарию больший размер — большая скорость.
* msvc: не разворачивает никакие циклы;
* icl: циклы с переменным кол-вом итераций разворачивает на 5 итераций,
циклы с cost <= 32 разворачивает полностью:
циклы с const >
32 разращивает на величину кратную const, но не больше 10h,
учитывает количество инструкций в цикле;
циклы разворачиваются по сценарию: больший размер — большая скорость
* gcc: на уровне O3 по учаолчанию не разворачивает,
циклы с переменным кол-вом итераций никогда не разворачиваются;
циклы с постоянным кол-вом интераций развариваются на ~4x (но тут все зависит от числа инструкций),
полностью оптимизированный вариант
Причем, в отличии от ситуации с объедением двух полностью тождественных строк (которой можно только похвастаться перед остальными компиляторами), задача объединения подстроки со строкой встречается довольно часто.
кандидат на константную подстановку
Компилятор gcc достигает аналогичного результата лишь за счет режима агрессивного "инлайнинга", а vc "честно" выполняет вызов функции, до тех пор пока программист не вставит ключевое слово "inline", но никаких гарантий, что vc не проигнорирует это предписание, у нас нет.
