Объединение циклов
Несколько циклов с одинаковым заголовком могут быть объедены в один, сокращая накладны расходы на его организацию. Эта методика имеет множество названий— loops fusion, merge loops, jam loops, создающих большую путаницу и вводящих программистов в заблуждение. В действительности же это не три различных стратегии оптимизации, а всего одна, но какая! Продемонстрирует ее на следующем примере:
for(i=0; i<XXL; i++)
a[i] = b[i] + 1;
for(j=0; j<XXL; j++)
d[j] = у[j] -1;
Объединение констант
Несколько строковых констант с идентичным содержимым для экономии памяти могут быть объедены ("merge") в одну. Тоже самое относится и к вещественным значениям. Целочисленные 32-битные константы объединять невыгодно, поскольку ссылка на константу занимает больше места, чем машинная команда с копией константы внутри.
Покажем технику объединения на следующем примере:
printf("hello,world!\n"); // одна строковая константа
printf("hello,world!\n"); // другая константа идентичная первой
printf("i say hello, world!\n"); // константа с идентичной подстрокой
Общие соображения по оптимизации
Качество оптимизирующих компиляторов обычно оценивают по результатом комплексных тестов (мультимедийных, "общесистемных" или математических). Что именно оптимизируется и как — остается неясным. Основной "интеллект" оптимизаторов сосредоточен в высокоуровневом препроцессоре — своеобразном "ликвидаторе" наиболее очевидных программистских ошибок. Чем качественнее исходный код, тем хуже он поддается оптимизации. Только ведь… над качественным кодом _работать_ надо! Много знать и ожесточенно думать, ломая карандаши или вгрызаясь в клавиатуру. Кому-то это в радость, а кто-то предпочитает писать кое-как. Все равно, мол, компилятор, соптимизирует!
Желание перебросить часть работы на транслятор — вполне естественно и нормально (для творчества больше времени останется), но нужно заранее знать, что именно он оптимизирует, а что только пытается. Но как это можно узнать? На фоне полнейшей терминологической неразберихи, когда одни и те же приемы оптимизации в каждом случае называются по-разному, прячась за ничего не говорящими штаммами типа "copy propagation" (размножение копий) или "redundancy elimination" (устранение избыточности), требуется очень качественная документация на компилятор, но она — увы — обычно ограничивается тупым перечислением оптимизирующих ключей с краткой пометкой за что каждый из них отвечает. Какие копии размножает компилятор и с какой целью? Какую избыточность он устраняет и зачем? Не является ли размножение внесением избыточности, которую самому же оптимизатору и приходится удалять?!
Взять хотя бы документацию на компилятор Intel C++ 7.0/8.0. Будь у меня бумажная версия, я бы ее "употребил". Все равно, ни на что другое она не пригодна. Это просто перечень ключей командной строки, разбавленный словесным мусором, в котором нет никакой конкретики. Скачайте для сравнения документацию на компилятор фирмы Hewlett-Packard (кстати, моя любимая фирма): http://docs.hp.com/en/B6056-96002/B6056-96002.pdf.
Доходчивое описание архитектуры процессора, советы по кодированию, тактика и стратегия оптимизирующей трансляции на конкретных примерах. Настоящая библия программиста!
Остальные компиляторы оптимизируют примерно таким же образом, поэтому, эта библия вполне приемлема и для них. "Эффективность оптимизации" из абстрактных цифр превращается серию простых тестов, каждый из которых можно прогнать через транслятор и потрогать руками. Дизассемблирование откомпилированных файлов позволяет однозначно установить — справился ли оптимизатор со своей задачей или нет.
Здесь сравниваются два наиболее популярных Linux-компилятора: GCC 3.3.4 (стабильная версия, проверенная временем, входящая в большинство современных дистрибьютивов), и Intel C++ 8.0 (далее по тексту icl), пропагандируемый как самый эффективный компилятор всех временен и народов, 30-дневная ознакомительная версия которого лежит на ftp-сервере фирмы. Для полноты картины в этот список включен древний, но все еще используемый Windows-компилятор Microsoft Visual C++ 6.0, для краткости обозначаемый как vc.
Если не оговорено обратное, приведенные примеры должны компилироваться со следующими ключами: -O3 –march=pentium3 (gcc), -O3 –mcpu=pentium4 (icl) и /Ox (vc).
Оптимизация switch
Оператор множественного выбора switch очень популярен среди программистов (особенно, разработчиков Windows-приложений). В некоторых (хотя и редких) случаях, операторы множественного выбора содержат сотни (а то и тысячи) наборов значений, и если решать задачу сравнения "в лоб", время выполнения оператора switch окажется слишком большим, что не лучшим образом скажется на общей производительности программы, поэтому пренебрегать его оптимизацией ни в коем случае нельзя.
Оптимизация ветвлений/branch
Ветвления (по-английски branch, они же условные/безусловные
переходы) относятся к фундаментальным основам любого языка, без которых не обходится ни одна программа. Даже "hello, world!"! Ведь выход из функции main— это тоже ветвление, пускай и неявное (но ведь процессор синтаксисом языка не проведешь!). А сколько ветвлений содержит сама функция printf? А Библиотека времени исполнения?
Суперскалярные микропроцессоры, построенные по конвейерной архитектуре (а все современные микропроцессоры именно так и устроены), быстрее всего выполняют линейный код и ненавидят ветвления. В лучшем случае они дезориентируют процессор, слегка приостанавливая выполнение программы, в худшем же — полностью очищают конвейер. А на последних Pentium'ах он очень длинный (и с каждой последующей моделью становится все длиннее и длиннее). Быстро его не заполнишь… на это может уйти не одна сотня тактов, что вызовет обвальное падение производительности.
Оптимизация переходов дает значительный выигрыш, особенно если они расположены внутри циклов (кстати говоря, циклы это те же самые переходы), поэтому качество компилятора не в последнюю очередь определяется его умением полностью или частично избавляться от ветвлений.
Отказ от branch-count-reg
Многие микропроцессоры имеют специальную команду: уменьши-регистр-на-единицу-и-ветвись-если-нуль (branch-count-reg). На x86-процессорах этим занимается LOOP, часто встречающаяся в ассемблерных вставках начинающих программистов, но практически никогда в коде, сгенерированном компилятором. И вовсе не потому, что компилятор "тупой", а потому, что эта инструкция медленная, хотя и компактная.
Компиляторы msvc и icl никогда ее не используют, а gcc предоставляет специальный ключ -fbranch-count-reg, предписывающий выбирать LOOP вместо DECreg/JNZ begin_loop, правда, до машинного когда она все равно не доживает и уничтожается оптимизатором.
* msvc: не использует branch-count-reg
* icl: не использует branch-count-reg
* gcc: не использует branch-count-reg
Предвычисление индуктивных циклов
Цикл называется индуктивным, если его тело целиком состоит из выражения, последующее значение которого вычисляется на основе предыдущего. Легко доказать, что значение индуктивного цикла зависит только от количества итераций и начального значения аргументов выражения, благодаря чему оно может быть вычислено еще на стадии компиляции.
Рассмотрим следующий пример:
for (i=0; i<XXL; i++)
sum++;
Программная конвейеризация
Разворот цикла традиционными методами (см. "разворот циклов") порождает зависимость по данным. Вернемся к листингу3. Смотрите, хотя загрузка обрабатываемых ячеек происходит параллельно (ну… практически параллельно, они будут ползти по конвейеру находясь на различных стадиях готовности), следующая операция сложения не может быть начата до тех пор, пока не будет завершена предыдущая.
Для усиления параллелизма, необходимо суммировать все ячейки в своих переменных, как показано ниже:
// обрабатываем первые 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;
Распределение переменных по регистрам
Регистров общего назначения всего семь, а чаще и того меньше. Регистр EBP используется для организации фреймов (так же называемых стековыми кадрами), регистр EAX по общепринятому соглашению используется для возращения значения функции. Некоторые команды (строковые операции, умножение/деление) работают с фиксированным набором регистров, который на протяжении всей функции приходился держать "под сукном" или постоянно гонять данные от одного регистра к другому, что так же не добавляет производительности.
Стратегия оптимального распределения переменных по регистрам (global registers allocation)— сложная задача, которую еще предстоит решить. Пусть слово "global" не вводит вас в заблуждение. Эта глобальность сугубо локального масштаба, ограниченная одной-единственной функцией, а то и ее частью.
Компиляторы стремятся помещать в регистры наиболее интенсивно используемые переменные, однако, под "интенсивностью" здесь понимается отнюдь не частота использования, а количество "упоминаний". Но ведь не все "упоминания" равнозначны! Вот, например, if (++a % 16) b++; else c++;
обращение к переменной c происходит в 16 раз чаще! Статистка обращений не всегда может быть получена путем прямого анализа исходного кода программы, так что ждать помощи со стороны машины — наивно.
Языки Си/Си++ поддерживают специальное ключевое слово "register", управляющее размещением переменных, однако, оно носит характер рекомендации, а не императива и все три рассматриваемых компилятора его игнорируют, предпочитая интеллекту программиста свой собственный машинный интеллект.
Представляет интерес сравнить распределение переменных по регистрам в глубоко вложенных циклах, поскольку его вклад в общую производительность весьма значителен. Рассмотрим следующий пример:
int *a, *b;
main(int n, char **v)
{
int i,j; int sum=0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
sum += sum*a[n*i + j] + sum/b[j] + x++;
return sum+x;
}
Расщепление циклов
Расщепление циклов (loop distribution, loopfission, loop splitting…) прямо противоположно их объединению. К такому трюку прибегают в тех случаях, когда оптимизируемый цикл содержит слишком много данных. Ассоциативность кэш-памяти первого уровня у большинства x86-процессоров равна четырем, реже — восьми, а это значит, что каждая обрабатывая ячейка данных может претендовать лишь на одну из четырех (восьми) возможных кэш-линеек и если они к этому времени уже заняты ячейками остальных потоков, происходит их неизбежное вытеснение из кэша, многократно снижающее производительность.
Рассмотрим следующий пример:
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];
}
Разбивка длинных цепочек зависимостей
Если индуктивный цикл предычислить не удалось, необходимо по крайней мере ослабить зависимость между итерациями, чтобы они могли исполнятся параллельно. Рассмотрим следующий код:
for(i=0;i<XXL;i++)
{
x += 2;
a[i] = x;
}
Размножение переменных
На процессорах с конвейерной архитектурой удаление "лишних" копий порождает ложную зависимость по данным, приводящую к падению производительности и переменные приходится не только "сворачивать", но и размножать!
Вот например:
a = x + y;
b
= a + 1; // b
зависит от a
a = i - j;
c
= a – 1; // с зависит от a… точнее от ее второй "копии"
Разворот циклов
Микропроцессоры с конвейерной архитектурой (а к таковым относятся все современные x86-процессоры), плохо приспособлены для работы с циклами. Для достижения наивысшей производительности процессору необходим достаточно протяженный участок "трассы выполнения", свободный от ветвлений. Компактные циклы вида for(a=0;a<n;a++)*dst++= *src++; исполняются очень медленно и для увеличения быстродействия приходится прибегать к их развороту (unrolling).
Под "разворотом" в общем случае понимается многократное дублирование цикла, которое реализуется приблизительно так:
for(i=1; i<n;i+)
k += (n % i);
Регистровые ре-ассоциации
Для преодоления катастрофической нехватки регистров, некоторые компиляторы стремятся совмещать счетчик цикла с указателем на обрабатываемые данные. Код вида "for(i = 0; I < n; i++) n+=a[i];" превращается ими в "for (p= a; p < &a[n]; p++) n+=*p;" Экономия налицо! Впервые (насколько мне известно) эта техника использовалась в компиляторах фирмы Hewlett-Packard, где она фигурировала под термином register reassociation. А что же конкуренты?! Возьмем следующий код (кстати, выдранный из документации на HP компилятор):
int a[10][20][30];
void example (void)
{
int i, j, k;
for (k = 0; k < 10; k++)
for (j = 0; j < 10;j++)
for (i = 0; i < 10; i++)
a[i][j][k] = 1;
}
несбалансированное (слева) и сбалансированное (справа) switch/case-дерево
Высота вновь образованного дерева будет равна , где N – количество гнезд старого дерева. Действительно, мы же делим ветвь дерева надвое и добавляем новое гнездо – отсюда и берется и +1, а (N+1) необходимо для округления результата деления в большую сторону. Т. е. если высота не оптимизированного дерева достигала 100 гнезд, то теперь она уменьшилась до 51. Что? Говорите, 51 все равно много? Но кто нам мешает разбить каждую из двух ветвей еще на две? Это уменьшит высоту дерева до 27 гнезд! Аналогично, последующее уплотнение даст 16 à 12 à 11 à 9 à 8… и все! Более плотная упаковка дерева уже невозможна. Но, согласитесь, восемь гнезд – это не сто! Оптимизированный вариант оператора switch в худшем случае потребует лишь пяти сравнений, но и это еще не предел!
Учитывая, что x86 процессоры все три операции сравнения <, =, > совмещают в одной машинной команде, двоичное логическое дерево можно преобразовать в троичное, тогда новых гнезд для его балансировки добавлять не нужно. Простейший алгоритм, называемый методом отрезков, работает так: сортируем все числа по возрастанию и делим получившийся отрезок напополам. Число находящееся посередине (в нашем случае это 11), объявляем вершиной дерева, а числа расположенные слева от него — его левыми ветвями и подветвями (в нашем случае это 0, 3, 4 и 7). Остальные числа (22, 96, 98, 666, 777) идут направо. Повторяем эту операцию рекурсивно до тех пор, пока длина подветвей не сократится до единицы. В конечном счете, вырастет следующее дерево (см. рис. 2):
троичное дерево, частично сбалансированное методом отрезков
Очевидно, что это не самое лучше дерево из всех. Максимальное количество сравнений (т. е. количество сравнений в худшем случае) сократилось с пяти до четырех, а количество ветвлений возросло вдове, в результате чего, время выполнения оператора switch только возросло. К тому же, структура построения дерева явна не оптимальна. Гнезда (a<=3), (a>=7), (a<=96), (a>=666) имеют свободные ветви, что увеличивает высоту дерева на единицу. Но, может быть, компилятор сумеет это оптимизировать?
Дизассемблирование показывает, что компилятор msvc генерирует троичное дерево, сбалансированное по улучшенному алгоритму отрезков, содержащее всего лишь 7 операций сравнения, 9 ветвлений и таблицу переходов на 10 элементов (см. "создание таблицы переходов"). В худшем случае, выполнение оператора switch требует 3 сравнений и 3 ветвлений. Троичное дерево построенное компилятором gcc, сбалансировано по классическому алгоритму отрезков и состоит из 11 сравнений и 24 ветвлений. В худшем случае, выполнение оператора switch растягивается на 4 сравнения и 6 ветвлений. Компилятор icl, работающий по принципу простого линейного поиска, строит двоичное дерево из 11 сравнений и 11 ветвлений. В худшем случае, все узлы дерева "пережевываются" целиком. Вот так "оптимизация"!
Ротация ветвлений
Бесконечные циклы с выходом по break могут быть преобразованы в конечные циклы с постусловием. При этом, тело цикла как бы прокручивается, чтобы оператор break переместился на место while(1), а сам while(1) сомкнулся с оператором do и "коллапсировал".
Продемонстрируем это на следующем примере:
do
{
printf("1й оператор цикла\n");
if (--a<0) break;
printf("2й оператор цикла\n");
} while(1);
Шелушение циклов
Идея шелушения циклов (по-английски "peeling") заключается в "сдирании" с цикла одной или нескольких итераций с последующей трансформацией в линейный код. Фактически, шелушение циклов является частным случаем разворота, однако, область его применения одним лишь разворотом не ограничивается.
Рассмотрим следующий код:
for(i=0; i<n; i++)
a[i] = b[i] + 1;
for(j=0; j<n+1; j++)
c[j] = d[j] – 1;
Сокращение длины маршрута
Если один условный или безусловный переход указывает на другой безусловный переход, то все три рассматриваемых компилятора автоматически перенаправляют первый целевой адрес на последний, что и демонстрирует следующий пример:
goto lab_1 ; // переход к метке lab_1 на безусловный переход к метке lab_2
….
lab_1: goto lab_2 ; // переход к метке lab_2
….
lab_2:
Сокращение количества сравнений
Процессоры семейства x86 (как и многие другие) обладают одну очень интересной концепцией, которой нет ни в одном языке высокого уровня. Операции вида if(a>b) выполняются в два этапа. Сначала из числа a вычитается число b и состояние вычислительного устройства сохраняется в регистре флагов. Различные комбинации флагов соответствуют различным отношениям чисел и за каждый из них отвечает "свой" условный переход. Например:
cmp eax,ebx // сравниваем eax с ebx, запоминая результат во флагах
jl lab_1 // переход, если eax < ebx
jg lab_2 // переход, если eax > ebx
lab_3: // раз мы здесь, eax
== ebx
Совмещение проверок
Совмещение проверок очень похоже на повторное использование подвыражений: если она и та же проверка присутствует в двух или более местах и отсутствуют паразитные зависимости по данным, все проверки можно объединить в одну:
if (CPU_TYPE == AMD) // проверка
x = AMD_f1(y);
else
x = INTEL_f1(y);
…
if (CPU_TYPE
== AMD) // еще одна проверка
a = AMD_f2(b);
else
a = INTEL_f2(b);
Создание таблицы переходов
Если значения ветвей выбора представляют собой арифметическую прогрессию (см.листинг 27), компилятор может сформировать таблицу переходов – массив, проиндексированный case-значениями и содержащий указатели на соответствующие им case-обработчики. В этом случае, сколько бы оператор switch ни содержал ветвей, – один или миллион – он выполняется за одну итерацию. Красота!
switch (a)
{
case
1 : /* код обработчика */ break;
case
2 : /* код обработчика */ break;
case
3 : /* код обработчика */ break;
case
4 : /* код обработчика */ break;
case
5 : /* код обработчика */ break;
case
6 : /* код обработчика */ break;
case
7 : /* код обработчика */ break;
case
8 : /* код обработчика */ break;
case
9 : /* код обработчика */ break;
case
10 : /* код обработчика */ break;
case
11 : /* код обработчика */ break;
}
Стремление циклов к нулю
На большинстве процессорных архитектур, инструкция декремента (уменьшения регистра на единицу) автоматически взводит специальный флаг при достижении нуля, поэтому, цикл, стремящийся к нулю (incrementing by zero, хотя правильнее было назвать его decrementing by zero) намного выгоден как с точки зрения компактности, так и с точки зрения быстродействия.
Рассмотрим следующий код:
for(i=0; i<n; i++) printf("hello!\n");
Свертка констант
Вычисление констант на стадии компиляции (оно же, "размножение" или "свертка" констант, constant elimination/folding/propagation или сокращенно CP)— популярный прием оптимизации, избавляющий программиста от необходимости постоянно иметь калькулятор под рукой. Все константные выражения (как целочисленные, так и вещественные) обрабатываются транслятором самостоятельно и в откомпилированный код не попадают.
Рассмотрим следующий пример: a = 2 * 2; b = 4 * с / 2; Компиляторы, поддерживающие такую стратегию оптимизации превратят его в: a = 4; b = 2 * с;
Улучшенная свертка констант, в англоязычной литературе именуемая "advanced constant folding/propagation" заменяет все константные переменные их непосредственным значением, например: a = 2; b = 2 * a; c = b - a;
превращается в c = 2;
Свертку констант в полной мере поддерживают все три рассматриваемых компилятора: vc, icl и gcc.
Свободная таблица
| компилятор
действие | Microsoft Visual C++ 6 | IntelC++ 8.0 | GCC 3.3.4 | ||||
| выравнивание переходов | не выравнивает | не выравнивает | выравнивает по границе степени двойки | ||||
| быстрое булево вычисление | поддерживает | поддерживает | поддерживает | ||||
| удаление избыточных проверок | не удаляет | удаляет | не удаляет | ||||
| удаление проверок нулевых указателей | не удаляет | не удаляет | удаляет | ||||
| совмещение проверок | не совмещает | совмещает | не совмещает | ||||
| сокращение длины маршрута | сокращает | сокращает | сокращает | ||||
| уменьшение кол-ва ветвлений | уменьшает | уменьшает | уменьшает | ||||
| сокращение количества сравнений | сокращает | частично сокращает | не сокращает | ||||
| избавление от ветвлений | избавляется от ветвлений константного типа | никогда не избавляется | избавляется всегда, когда это возможно | ||||
| балансировка логического древа | троичное дерево, сбалансированное улучшенным методом отрезков | двоичное, несбалансированное дерево | троичное дерево, сбалансированное методом отрезков | ||||
| создание таблицы переходов | создает | создает | создает | ||||
| поддержка разряженной таблицы переходов | поддерживает | поддерживает | поддерживает | ||||
| совмещение таблицы переходов с деревом | совмещает | не совмещает | не совмещает |
Свободная таблица качества оптимизации
| компилятор
действие | Microsoft Visual C++ 6 | IntelC++ 8.0 | GCC 3.3.4 | ||||
| выравнивание циклов | не выравнивает | не выравнивает | выравнивает по границе степени двойки | ||||
| разворот циклов | не разворачивает | разворачивает циклы без ветвлений с переменным и постоянным кол-вом итераций | разворачивает циклы с постоянным кол-вом итераций | ||||
| шелушение циклов | не шелушит | шелушит | шелушит | ||||
| векторизация циклов | не векторизует | векторизует | векторизует начиная с версии 3.4.3 | ||||
| авто-параллелизм | не поддерживает | поддерживает | не поддерживает | ||||
| программная конвейеризация | не поддерживает | не поддерживает | частично поддерживает | ||||
| предвычисление индуктивных циклов | предвычисляет простые циклы | не предвычисляет | не предвычисляет | ||||
| разбивка длинных цепочек зависимостей | не разбивает | не разбивает | разбивает, начиная с версии 4.0.0 | ||||
| устранение хвостовой рекурсии | устраняет | не устраняет | устраняет | ||||
| объединение циклов | не объединяет | не объединяет | не объединяет | ||||
| трепание циклов | не поддерживает | не поддерживает | не поддерживает | ||||
| расщепление циклов | не расщепляет | расщепляет | не расщепляет | ||||
| нормализация циклов | нормализует некоторые циклы | нормализует некоторые циклы | нормализует некоторые циклы | ||||
| масштабирование циклов | масштабирует некоторые циклы | масштабирует некоторые циклы | масштабирует некоторые циклы | ||||
| замена циклов с предусловием на циклы с постусловием | заменяет | заменяет | заменяет | ||||
| стремление циклов к нулю | всегда стремит циклы к нулю | никогда не стремит циклы к нулю | стремит некоторые циклы к нулю | ||||
| branch-count-reg | не использует | не использует | не использует | ||||
| вынос инвариантных ветвлений | не выносит | не выносит | выносит, начиная с версии 3.4.3 | ||||
| ротация ветвлений | выполняет | не выполняет | не выполняет | ||||
| упорядочивание обращение к памяти | частично упорядочивает обращения к памяти | частично упорядочивает обращения к памяти | частично упорядочивает обращения к памяти |
Сводная таблица качества оптимизации
| компилятор
действие | Microsoft Visual C++ 6 | IntelC++ 8.0 | GCC 3.3.4 | ||||
| свертка констант | выполняет улучшенную свертку | выполняет улучшенную свертку | выполняет улучшенную свертку | ||||
| объединение констант | никогда не объединяет | объединяет идентичные строковые и вещественные константы | объединяет идентичные строковые и вещественные константы | ||||
| константная подстановка в условиях | подставляет | не подставляет | подставляет | ||||
| свертка функций | сворачивает только встраиваемые | с ключом -ipo сворачивает все | сворачивает только встраиваемые | ||||
| удаление мертвого кода | удаляет только в основной ветке | удаляет во всех ветках | удаляет только в основной ветке | ||||
| удаление неиспользуемых функций | никогда не удаляет | удаляет с ключом –ipo | никогда не удаляет | ||||
| удаление неиспользуемых переменных | удаляет с все неявно неиспользуемые отслеживанием генетических связей | удаляет с все неявно неиспользуемые отслеживанием генетических связей | удаляет с все неявно неиспользуемые отслеживанием генетических связей | ||||
| удаление неиспользуемых выражений | удаляет | удаляет | удаляет | ||||
| удаление лишних обращений к памяти | частично | частично | частично | ||||
| удаление копий переменных | удаляет | удаляет | удаляет | ||||
| размножение переменных | не размножает | размножает | не размножает | ||||
| распределение переменных по регистрам | распределяет отлично | распределяет плохо | распределяет средне | ||||
| реассоциацирует регистры | не реассоцирует | реассоцирует | не реассоцирует | ||||
| алгебраическое упрощение выражений | в большинстве случаев выполняет упрощение | упрощает простые и некоторые сложные выражения | упрощает простые выражения | ||||
| упрощение алгоритма | упрощает некоторые операции | никогда не выполняет | никогда не выполняет | ||||
| использование подвыражений | распознает явные подвыражения только в основной ветке | распознает все явные и частично неявные подвыражения во всех ветках | распознает явные подвыражения во всех ветках |
Техника оптимизации под линуха
крис касперски ака мыщъх, no-email
…вычислительная машина – новый могущественный инструмент. Однако немногие имеют представление об источнике этого могущества.
Дж Вейценбаум Дж "Возможности вычислительных машин и человеческий разум. От суждений к вычислениям"
сегодня мы займемся исследованием двух наиболее популярных Linux-компиляторов: GCC 3.3.4 и Intel C++ 8.0, а конкретно — сравнением мощности их оптимизаторов. для полноты картины в этот список включен Microsoft Visual C++ 6.0 — один из лучших Windows-компиляторов.
(альтернативный вариант вступления на усмотрение редакции)
что находится под черной крышкой оптимизатора? чем один компилятор отличается от другого? правда ли, что Intel C++ намного круче GCC, а сам GCC бьет любой Windows-компилятор? хотите узнать как помочь оптимизатору сгенерировать намного более эффективный код?
Техника оптимизации под LINUX частьII — ветвления
крис касперски ака мыщъх, no-email
сегодня мы продолжим сравнение Linux-компиляторов, начатое в прошлом номере журнала и рассмотрим оптимизацию условных переходов и операторов типа switch. механизмы их трансформации достаточно многочисленны и разнообразны. за последнее время было предложено множество новых идей, воплощенных в компиляторах GCC 3.3.4 и Intel C++ 8.0 (сокращенно icl), однако, древний Microsoft Visual C++ 6.0 (сокращенного msvc) не сдает своих позиций, так что не спешите списывать его в утиль и сдавать на свалку.
Техника оптимизации под LINUX III оптимизация циклов
крис касперски
большое тестовое сравнение Linux-компиляторов продолжается! тема сегодняшнего исследования — циклы и их оптимизация. в основном мы будем говорить о трех наиболее популярных компиляторах —GCC 3.3.4, Intel C++ 8.0 и Microsoft Visual C++ 6.0, к которым теперь присоединился и GCC 4.0.0 со своим новым оптимизатором циклов
Трепание циклов
Трепание циклов (loopspreading) представляет собой разновидность шелушения, при котором "содранные" итерации упаковываются в самостоятельный цикл, что бывает полезным, например, при объединении двух циклов с "разнополыми" заголовкам.
Рассмотрим следующий код:
for(i=0; i<n; i++;)
a[i] = a[i] + c;
for(j=0; j<m; j++;)
s[j] = s[j] + s[j+1];
Удаление избыточных проверок
Небрежное кодирование часто приводит к появлению избыточных или даже заведомо ложных проверок, полностью или частично дублирующих друг друга, например: "if(a > 9) … if (a > 6)…". Очевидно, что вторая проверка лишняя и icl благополучно ее удаляет. Остальные рассматриваемые компиляторы такой способностью не обладают, послушно генерируя тупой код.
if (n > 10) a++; else return 0;
if (n > 5) a++; else return 0; // избыточная
проверка
if (n < 2) a++; else return 0; // заведомо ложна проверка
Удаление копий переменных
Для экономии памяти компиляторы обычно сокращают количество используемых переменных, выполняя алгебраический разворот выражений и удаляя лишние копии. В англоязычной литературе за данной техникой оптимизации закреплен термин "copy propagation", суть которого поясняется в следующем примере:
main(int n, char** v)
{
int a,b;
a
= n+1;
b
= 1-a; // избавляется от переменной a: (1 – (n + 1));
return a-b; // избавляется от переменной b: ((n + 1) – (1 – (n + 1)));
}
Удаление лишних обращений к памяти
Компиляторы стремятся размещать переменные в регистрах, избегая "дорогостоящих" операций обращения к памяти. Взять хотя бы такой код: "i=*p+c; b = *p - d;". Очевидно, что второе обращение к *p лишнее и компиляторы поступают так: t =*p; i = t+c; b = t-d, при этом неявно полагается, что содержимое ячейки *p не изменяется никаким внешним кодом, в противном случае оптимизация будет носить диверсионно-разрушительный характер. Что если переменная используется для обмена данными/синхронизации нескольких потоков? Что если какой-то драйвер возвращает через нее результат своей работы? Наконец, что если мы хотим получить исключение по обращению к странице памяти? Для усмирения оптимизатора во всех этих случаях необходимо объявлять переменную как volatile
(буквально: "изменчивый", "неуловимый"), тогда при каждом обращении она будет перечитываться из памяти.
Указатели – настоящий бич оптимизации. Компилятор никогда не может быть уверен, адресуют ли две переменных различные области памяти или обращаются к одной и той же ячейке памяти.
Вот, например:
f(int *a, int *b)
{
int x;
x = *a + *b; // сложение содержимого двух ячеек
*b = 0x69; // изменение ячейки *b, адрес которой не известен компилятору
x += *a; // нет гарантии что запись в ячейку *b
не изменила ячейку *a
}
Удаление мертвого кода
"Мертвым кодом" (dead code) называется код, никогда не получающий управления и впустую транжирящий дисковое пространство и оперативную память. В простейшем случае он представляет собой условие, ложность которых очевидна еще на стадии трансляции, или код, расположенный после безусловного возврата из функции.
Вот, например: if(0) n++; else n--; Это несложная задача и с нею успешно справляются все три рассматриваемых компилятора.
А вот в следующем случае бесполезность выражения "n++" уже не столь очевидна: for (a = 0; a < 6; a++) if (a < 0) n++;
Условие (a < 0) всегда ложно, поскольку цикл начинается с 0 и продолжается до 6. Из всех трех рассматриваемых компиляторов это по "зубам" только icl.
Удаление неиспользуемых функций
Объявленные, но ни разу не вызванные функции, компилятору не так-то просто удалить. Технология раздельной компиляции (одни файл исходного текста – один объектный модуль) предполагает, что функция, не использующаяся в текущем модуле, вполне может вызываться из остальных. Реальный расклад выявляется лишь на стадии компоновки. Выходит, неиспользуемые функции должен удалить линкер? Но "выцарапать" мертвую функцию из объектного файла еще сложнее! Для этого линкеру необходимо иметь мощный дизассемблер и нехилый искусственный интеллект в придачу.
Компилятор icl в режиме глобальной оптимизации (ключ –ipo) отслеживает неиспользуемые функции еще на этапе трансляции и в объектный модуль они не попадают. Остальные компиляторы ничем таким похвастаться не могут. Поэтому, категорически не рекомендуется держать весь проект в одном файле (особенно если вы пишите библиотеку). Помещайте в файл только "родственные" функции, которые всегда используются в паре и по отдельности не имеют никакого смысла. Одна функция на объектный файл – это вполне нормально. Две-три еще терпимо, а вот больше — уже перебор. Присмотритесь как устроены стандартные библиотеки языка Си и ваши программы сразу похудеют.
Удаление неиспользуемых переменных
Объявленные, но неиспользуемые переменные, удаляются всеми современными компиляторами. Древние оптимизаторы удаляли лишь переменные, к которым не происходило ни одного обращения, сейчас же оптимизатор строит своеобразное "абстрактное дерево" и ветви, ведущие в никуда полностью обрубаются.
В приведенном ниже примере, vc, icl и gcc удаляют все три переменных— a, b и с:
main(int n, char **v)
{
int a,b,c;
a
=n;
b
= a + 1;
c
= 6*b; // переменная c не используется, а значит переменные a
и b
лишнее
return n;
}
Удаление неиспользуемых выражений
Неиспользуемые выражения удаляются всеми тремя рассматриваемыми компиляторами.
Вот например:
main(int n, char** v)
{
int a,b;
a
= n+0x666; // не используется, перекрывается (2*n)
b
= n-0x999; // теряется при выходе их функции
a
= 2*n; // единственное используемое выражение
return a;
}
Удаление проверок нулевых указателей
Программисты до сих пор не могут определиться: кто должен осуществлять проверку аргументов— вызывающая или вызываемая функция. Многие стандарты кодирования предписывают выполнять такую проверку обоим:
f1(int *p)
{
if (p) return *p+1; else return –1;
}
f2(int *p)
{
if (p) *p = 0x69; else return -1;
return f1(p);
}
Уменьшение кол-ва ветвлений
Все три компилятора просматривают код в поисках условных переходов, перепрыгивающих через безусловные (conditional branches over unconditional branches) и оптимизируют их: инвертируют условный переход, перенацеливая его на адрес безусловного перехода, а сам безусловный переход удаляют, уменьшая тем самым количество ветвлений на единицу:
if (x) a=a*2; else goto lab_1;// двойное
ветвление
if – else
b=a+1
lab_1: c=a*10
Упорядочивание обращений к памяти
При обращении к одной-единственной ячейки памяти, в кэш первого уровня загружается целая строка, длина которой в зависимости от типа процессора варьируется от 32 до 128 или даже 256байт, поэтому большие массивы выгоднее всего обрабатывать по строкам, а не по столбцам. К сожалению, многие программисты об этом забывают и отдуваться приходится компилятору:
for(j=0;j<m;j++)
for(i=0;i<n;i++)
a[i][j] = b[i][j] + c[i][j];
Упрощение алгоритма
Наибольший прирост производительности дает именно алгоритмическая оптимизация (например, замена пузырьковой сортировки на сортировку вставками). Никакой компилятор с этим справится не в состоянии. Во всяком случае пока. Но первый шаг уже сделан. Современные компиляторы распознают (или во всяком случае пытаются распознать) смысловую нагрузку транслируемого кода и при необходимости заменяют исходный алгоритм другим, намного более эффективным.
Вот, например:
main(int n, char **v)
{
int a = 0; int b = 0;
for(i=0; i<n; i++) a++; // многократное сложение – это умножение
for(j=0; j<n; j++) b++;
return a*b;
}
Упрощение выражений
Выполнять алгебраические упрощения оптимизаторы научились лишь недавно, но эффект, как говориться превзошел все ожидания. Редкий программистский код не содержит выражений, которые было бы нельзя сократить. Откройте документацию по MFC на разделе "Changing the Styles of a Window Created by MFC" и поучитесь как нужно писать программы.
BOOL CMainFrame::PreCreateWindow(CREATESTRUCT& cs)
{
// Create a window without min/max buttons or sizable border
cs.style = WS_OVERLAPPED | WS_SYSMENU | WS_BORDER;
// Size the window to 1/3 screen size and center it
cs.cy = ::GetSystemMetrics(SM_CYSCREEN) / 3;
cs.cx = ::GetSystemMetrics(SM_CXSCREEN) / 3;
cs.y = ((cs.cy
* 3) - cs.cy) / 2;
cs.x = ((cs.cx
* 3) - cs.cx) / 2;
// Call the base-class version
return CFrameWnd::PreCreateWindow(cs);
}
Устранение хвостовой рекурсии
Хвостовой рекурсией (tail recursion) называется такой тип рекурсии, при котором вызов рекурсивной функции следует непосредственно за оператором return. Классическим примером хвостовой тому является алгоритм вычисления факториала:
int fact(int n, int result)
{
if(n == 0)
{
return result;
}
else
{
return fact(n - 1, result * n);
}
}
Векторизация
Начиная с PentiumMMX, в x86-процессорах появилась поддержка векторных команд (они же "мультимедийные"). К сожалению, в ANSI Си векторные операции отсутствуют, а нестандартные языковые расширения создают проблему переносимости, поэтому вся забота по векторизации циклов ложится на компилятор. Он должен проанализировать исходный код и определить какие операции могут выполняться параллельно, а какие нет.
Допустим, исходный цикл выглядел так:
for(i=0; i<XXL; i++)
a[i] += b[i];
По статистике, до 90% времени
По статистике, до 90% времени исполнения приходится на глубоко вложенные циклы, от качества оптимизации которых зависит быстродействие всей программы в целом. Современные компиляторы поддерживают множество прогрессивных технологий оптимизации и способны буквально на чудеса!
Стратегия оптимизации циклов тесно связана с архитектурой процесса, кэш-контроллера и контроллера оперативной памяти. Это слишком объемная, можно даже сказать, монументальная тема, и в рамках настоящей статьи она не обсуждается. Читайте документацию, распространяемую фирмами Intel и AMD (причем не только по процессорам, но и по чипсету) или "Технику оптимизации программ— эффективная работа с оперативной памяти" Криса Касперски, электронная версия которой свободно распространяется через файлообменные сети. Там эти вопросы описаны достаточно подробно.
Вынос инвариантных ветвлений
Ветвления, инвариантные по отношению цикла, могут быть вынесены за его пределы, путем расщепления одного цикла на два или более. Размеры кода при этом возрастают, но и производительность увеличивается (конечно, при условии, что цикл влезает в кэш).
Покажем это на следующем примере:
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;
}
}
Выравнивание циклов
Выравнивание циклов (loop alignment) имеет много общего с выравниванием ветвлений, о котором мы уже говорили в предыдущей статье. Кратно опишем ситуацию, для тех кто не в курсе. Компиляторы msvc и icl вообще не выравнивают циклы, располагая их в памяти как бог на душу положит. В худшем случае это приводит к трех-четырех кратному падению производительности и порядка 30% быстродействия теряется в среднем.
Компилятор gcc позволяет выравнивать циклы на величину, кратную степени двойки. За это отвечает ключ -falign-loops=n (по умолчанию n равен двум, что как уже отмечалось, далеко не самая лучшая стратегия выравнивая и предпочтительнее использовать n? равный четырем). Ключ -fno-align-loops (аналогичный ключу -falign-loops=1) отключает выравнивание. На уровнях оптимизации –O2 и ?O3 выравнивание циклов по умолчанию включено и отключать его было бы неразумно.
* msvc: не выравнивает
* icl: не выравнивает
* gcc: выравнивает по границе степени двойки
Выравнивание переходов
Процессоры, основанные на ядрах Intel P6 и AMD K6, не требуют выравнивания переходов, исключая тот случай, когда целевая инструкция или сама команда перехода расщепляется границей кэш-линейки напополам, в результате чего наблюдается значительное падение производительности. Наибольший ущерб причиняют переходы, находящиеся в циклах с компактным телом и большим уровнем вложения.
Чтобы этого не происходило, некоторые компиляторы прибегают к выравниванию, располагая инструкции перехода по кратным адресам и заполняют образующиеся дыры незначащими инструкциями, такими как XCHG EAX,EAX (обмен содержимого регистров EAX местами) или MOV EAX, EAX (пересылка содержимого EAX в EAX). Это увеличивает размер кода и несколько снижает его производительность, поэтому бездумное выравнивание (оно же "агрессивное") только вредит.
Легко показать, что машинная команда требует выравнивания в тех, и только тех случаях, когда условие ((addr
% cache_len + sizeof(ops)) > cache_len) становится истинным. Здесь: addr – линейный адрес инструкции, cache_len размер кэш-линейки (в зависимости от типа процессора равный 32-, 64- или 128 байтам), ops – сама машинная инструкция. Количество выравнивающих байт рассчитывается по формуле: (cache_len ? (addr % cache_len)).
Именно так поступают все ассеблерщики, но только не компиляторы! MSVC и icl вообще не выравнивают переходов, а gcc выравнивает целевую инструкцию на фиксированную величину, кратную степени двойки (т. е. 2, 4, 8…), что является крайне неэффективной стратегией выравнивания, однако, даже плохая стратегия все же лучше, чем совсем никакой. Кстати говоря, именно поэтому, компиляторы msvc и icl генерируют неустойчивый код, точнее код с "плавающей" производительностью, быстродействие которого главным образом зависит от того, расщепляются ли глубоко вложенные переходы или нет. А это в свою очередь зависит от множества трудно прогнозируемых обстоятельств, включая фазу луны и количество осадков.
Учитывая, что средняя длина x86-инструкций составляет 3.5 байта, целесообразнее всего выравнивать переходы по границе четырех байт (ключ -falign-jumps=4 компилятора gcc). Ключ -fno-align-jumps (или эквивалентный ему -falign-jumps=1) отключает выравнивание. Ключ ?falign-jumps=0
задействует выравнивание по умолчанию, автоматически выбираемое компилятором в зависимости от типа процессора.
if ((addr % cache_len + sizeof(ops)) > cache_len)
align = cache_len – (addr % cache_len);
Современные методики оптимизации носят довольно
Современные методики оптимизации носят довольно противоречивый характер. С одной стороны, они улучшают код, с другой— страдают непредсказуемыми побочными эффектами. Опытные программисты подобных "вольностей" не одобряют и режимом агрессивной оптимизации пользуются с большой осторожностью. Однако, полностью отказываться от машинной оптимизации даже самые закоренелые консерваторы уже не решаются. Ручное "вылизывание" кода обходится слишком дорого, правда последствия иной оптимизации выходят еще дороже. Наращивая мощь оптимизаторов, разработчики компиляторов допускают все больше ошибок и в ответственных случаях программистам приходится идти на компромисс, поручая оптимизатору только ту часть работы, в результате которой можно быть полностью уверенным (свертка констант, константная подстановка и т. д.)
Собственно говоря, наше исследование компиляторов еще не закончено и перечисленные приемы оптимизации это даже не верхушка айсберга, а небольшой его кусочек. В следующей статье этого цикла мы рассмотрим трансформацию циклов и прочие виды ветвлений. Уверяю вас, это очень интересная тема и здесь есть чему поучиться! (ну дожили… трансляторы учат программистов… [бурчание удаляющегося мыщъх'а]).
Прогресс не стоит на месте и со времени появления msvc компиляторы сделали большой шаг вперед. Особенно порадовал gcc 4.0.0 с его новым оптимизатором циклов, который намного превосходит icl и msvc всех вместе взятых. Тем не менее, до совершенства ему еще далеко. Некоторые техники, присутствующие еще в msvc, в нем не реализованы (например, ротация ветвлений), не говоря уже про "серьезные" компиляторы от Hewlett-Packard. Так что на компилятор надейся, а сам не плошай!
Справедливости ради, оливка ветвь пальмы первенства на этот раз не достанется никому. Все три компилятора показывают впечатляющий результат, но прокалываются в мелочах. Позиция icl выглядит достаточно сильной, однако, на безусловное господство никак не тянет. Как минимум ему предстоит научиться выравнивать переходы, заменять ветвления математическими операциями и переваривать оператор switch.
Компилятор gcc, с учетом его бесплатности, по-прежнему остается наилучшим выбором. Он реализует многие новомодные способы оптимизации ветвлений (в частности, использует инструкцию CMOVcc), однако, по ряду позиций проигрывает насквозь коммерческому msvc, лишний раз подтверждая основной лозунг Microsoft: "Bill always win". При переходе от ветвлений к циклам (а, циклы, как известно, "съедают" до 90% производительности программы), этот разрыв лишь усиливается. Но о циклах в другой раз. Это слишком объемная, хотя и увлекательная тема. Современные компиляторы не только выбрасывают из цикла все ненужное (например, заменяют цикл с предусловием на цикл с пост-условием который на одно ветвление короче) но и трансформируют сам алгоритм, подгоняя порядок обработки данных под особенности архитектуры конкретного микропроцессора.
Замена циклов с предусловием на циклы с пост-условием
Циклы с предусловием (for, while) содержат по меньшей мере на одно ветвление больше, чем аналогичные им циклы с постусловием. Как нетрудно сообразить— в конце цикла с предусловием находится безусловный переход, возвращающий управление в начало, а в цикле с постусловием передача управления по "совместительству" еще выполняет и проверку условия.
Все три рассматриваемых компилятора всегда заменяют циклы с предусловиям на циклы с постусловием, когда это выгодно.
* msvc: заменяет циклы с предусловием на циклы с постусловием
* icl: заменяет циклы с предусловием на циклы с постусловием
* gcc: заменяет циклы с предусловием на циклы с постусловием
