Мощь и беспомощность автоматической оптимизации

         

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


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

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

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

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



Что надо оптимизировать


Теперь поговорим о том, с чем оптимизирующие компиляторы не справляются и начинают буксовать, резко снижая эффективность целевого кода. Помочь им выбраться из болота— наша задача! Чип и Дейл уже спешат! Ну а мыщщъх вращает хвостом. Руководит, значит.

Начнем с функций. Из всех рассматриваемых компиляторов только Intel C++ поддерживает глобальную оптимизацию, а остальные — транслируют функции по отдельности, задействую "сквозную" оптимизацию только на встраиваемых (inline) функциях. Отсюда: чем выше степень дробления программы на функции (и чем меньше средний размер одной функции), тем ниже качество оптимизации, не говоря уже о накладных расходах на передачу аргументов, открытие кадра стека и т. д.

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

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



Что не надо оптимизировать


Начнем с того, что _не_ _надо_ оптимизировать, позволяя транслятору сделать это за нас (нехай делает). В частности, практически все оптимизирующие компиляторы умеют вычислять константы на стадии трансляции. В различных русскоязычных источниках этот прием оптимизации называется как "сверткой", так и "размножением" констант, что соответствует английским терминам "constant folding/propagation". Еще один английский термин из той же кучи: "constant elimination" (буквально— "изгнание констант"). Все это синонимы и описывают один и тот же механизм вычисления константных выражения (как целочисленных, так и вещественных), в результате чего a = 2 * 2

превращается в a = 4, а x = 4*y/2 в x = 2*y.

Побочным эффектом оптимизации становится потеря переполнения (если таковое имело место быть). С точки зрения математика выражения foo = bar/4*4 и foo = bar

полностью эквиваленты, но если переменные foo и bar

целые, то не оптимизированный вариант обнуляет два младших бита bar! Некоторые программисты умышленно используют этот примем, вместо того, чтобы воспользоваться "foo = bar & (~3)", а ругаются на "глючный" оптимизатор!

За исключением Intel C++ все рассматриваемые компиляторы поддерживают "улучшенную свертку констант" ("advanced constant folding/propagation"), заменяя все константные переменные их непосредственным значением, в результате чего выражение: a = 2; b = 2 * a; c = b ? a;

превращается в c = 2, а переменные a

и b

(если они нигде более не используются) уничтожаются.



Константная подстановка в условиях


В операторах ветвления ("if", "?" и "switch") константные условия встречаются редко и обычно являются следствием чрезмерного увлечение #define, вот, например, как здесь:

#define MAX_SIZE     1024

#define REQ_SIZE     512

#define HDR_SIZE     16

int a = REQ_SIZE + HDR_SIZE;

if (a <= MAX_SIZE) foo(a); else return ERR_SIZE;



переменные a и b — лишнее


После оптимизации переменные a и b исчезают, а return

возвращает значение выражения (2*n+1):

main(int n, char** v)

{

       return

2*n+1;

}



хвостовая рекурсия до оптимизации


Вызов функции — достаточно "дорогостоящая" (в плане процессорных тактов) операция и за исключением Intel C++ все рассматриваемые компиляторы трансформирует рекурсивный вызов в цикл:

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



не оптимизированный вариант с инвариантом в теле цикла


Если только компилятор не заинлайнит функцию strlen, она будет вычисляется на каждой итерации цикла, что приведет к значительному снижению производительности. Но если вынести инвариант за пределы цикла, все будет ОК:

t = strlen(s);

for(a=0;a<t;a++) b+=s[a];



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


Алгоритм нормализации выглядит так:

for (NCL = 0; i < (to - from + step)/step  - 1; 1)

{

       i = step*NLC + from;

       // тело

цикла

}

i =  step * _max((to - from + step)/step, 0) + from;



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


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);



не оптимизированный вариант


Поскольку зависимость по данным отсутствует, цикл можно разбить на два. Первый будет обрабатывать ячейки от 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];



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


Здесь три массива обрабатываются по столбцам, что крайне непроизводительно и для достижения наивысшей эффективности циклы 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];



пример с лишними обращениями к памяти, от которых нельзя избавиться


Компилятор не имеет права на размещение содержимого ячейки *a в регистровой переменной, поскольку если ячейки *a и *b

частично или полностью перекрываются, модификация ячейки *b

приводит к неожиданному изменению ячейки *a! Бред, конечно, но ведь Стандарт этого не запрещает, а компилятор _обязан_ следовать Стандарту, иначе, его место — на свалке.

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

f(char *x, int *dst, int n)

{

       int i;

       for (i = 0; i < n; i++) *dst += x[i];

}



не оптимизированный кандидат на регистровую ре-ассоциацию


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

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;

}



не оптимизированный вариант


За исключением Intel C++ все рассматриваемые компиляторы выполняют константную подстановку, оптимизируя код, избавляясь от ветвления и ликвидируя "мертвый код", который никогда не выполняется:

foo(528);



оптимизированный вариант


Выполнять эту оптимизацию вручную совершенно необязательно, поскольку оптимизированный листинг намного менее нагляден и совершенно негибок. По правилам этикета программирования, _все_ константы должны быть вынесены в #define, что значительно уменьшает число ошибок.



хвостовая рекурсия после оптимизации


Естественно, оптимизированный код менее нагляден, поэтому выполнять такое преобразование вручную — совершенно необязательно.



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


Наибольшую отдачу нормализация дает на циклах с заранее известным количеством итераций, т. е. когда выражение (to ? from + step)/step

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

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



цикл, развернутый на 4 итерации (меньшей размер, большая скорость)


За исключением Microsoft Visual C++, все остальные рассматриваемые компиляторы умеют разворачивать циклы и самостоятельно, но… делают это настолько неумело, что вместо ожидаемого увеличения производительности сплошь и рядом наблюдается ее падение, поэтому автоматический разворот лучше сразу запретить и оптимизировать программу вручную, подбирая подходящую степень разворота опытным путем (вместе с профилировщиком).

Тут ведь как — чем сильнее разворот, тем больше места занимает код и появляется риск, что в кэш первого уровня он может вообще не влезть, вызывая обвальное падение производительности! (Подробнее о влиянии степени разворота на быстродействие можно прочитать в моей "технике оптимизации", электронная копию которой как обычно лежит на моем мыщъхином ftp://nezumi.org.ru).



оптимизированный вариант


Intel C++ – единственный из всех рассматриваемых компиляторов, поддерживающий технику авто-парализации, активируемую ключом –parallel, однако, качество оптимизации оставляет желать лучшего и эту работу лучше осуществлять вручную.



обработка массивов по столбцам (оптимизированный вариант)


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

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];



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


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

f(char *x, int *dst, int n)

{

       int i,t =0;

       for

(i=0;i<n;i++) t+=x[i]; // сохранение суммы во временной переменной

       *dst+=t;                   // запись конечного результата в память

}



Мощь и беспомощность автоматической оптимизации


крис касперски ака мыщъх, no-email

к концу 90х годов компиляторы по своей эффективности вплотную приблизились к ассемблеру, однако, все еще существует множество конструкций, неподдающихся автоматической оптимизации, но легко трансформируемых вручную. покажем как надо и как не надо оптимизировать программы на примере: Microsoft Visual C++, Intel C++, Borland Builder, GCC и Hewlett-Packard C++



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


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

Рассмотрим типичный цикл:

for (a = from; a < to; i+=(-step))

{

       // тело цикла

}



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


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

Чтобы избавиться от зависимости по данным, необходимо развернуть не только цикл, но и "расщепить" переменную, используемую для суммирования. Такая техника оптимизации называется программной конвейеризацией (software pipelining) и из всех рассматриваемых компиляторов ее поддерживает только GCC, да и то лишь частично. В тоже самое время, она элементарно реализуется "руками":

// обрабатываем первые 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;



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


Процессоры с конвейерной архитектурой (к которым относится и x86) плохо справляются с ветвлениями (а циклы как раз и представляют одну из разновидностей ветвлений), резко снижая свою производительность. Образно их можно сравнить с гоночной машиной, ползущей по петляющей дороге. И у машины, и у процессора максимальная скорость достигается только на участках свободных от ветвлений.

Компактные циклы вида for(a=0;a<n;a++)*dst++= *src++;

исполняются крайне медленно и должны быть развернуты (unrolled). Под "разворотом" в общем случае понимается многократное дублирование цикла, которое в классическом случае реализуется так:

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

      k += (n % i);



Регистровые ре-ассоциации


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

Код вида "for(i = 0; I < n; i++) n+=a[i];" легко оптимизировать, если переписать его так: "for (p= a; p < &a[n]; p++) n+=*p;" Насколько известно мыщъх'у впервые эта техника использовалась в компиляторах фирмы Hewlett-Packard, где она фигурировала под термином register reassociation, а вот остальные рассматриваемые нам компиляторы этого делать, увы, не умеют.

Рассмотрим еще один пример, демонстрирующий оптимизацию цикла с тройной вложенностью:

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;

}



Удаление копий переменных


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

В англоязычной литературе данный примем называется "размножением копий" ("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)));

}



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


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

Вот, например:

f(int *a, int *b)

{

       int x;

       x = *a + *b;  // сложение содержимого двух ячеек

       *b = 0x69;    // изменение ячейки *b, адрес которой не известен компилятору

       x += *a;      // нет гарантии что запись в ячейку *b

не изменила ячейку *a

}



Удаление неиспользуемых функций


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

Функция, реализованная в одном объектном файле, может вызываться из любых других, но информацией о других модулях компилятор не обладает и потому удалять "не используемые" (с его точки зрения) функции не имеет права.

Теоретически, неиспользуемые функции должен удалять линкер, но популярные форматы объектных файлов к этому не располагают и в грубом приближении представляют собой набор секций (.text, .data и т. д.), каждая из которых с точки зрения линкера представляет монолитный блок, внутрь которого линкер не лезет, а просто объединят блоки тем или иным образом.

Вот потому-то и не рекомендуется держать весь проект в одном файле (особенно если это библиотека). Помещайте в файл только "родственные" функции, _всегда_ используемые в паре и по отдельности не имеющие никакого смысла. Посмотрите как устроена стандартная библиотека языка Си — большинство функций реализованы в "своем" собственном файле, компилируемом в obj, содержащим _только_ эту функцию и ничего сверх нее! Множество таких obj объединяются библиотекарем в один lib-файл, откуда линкер свободно достает любую необходимую функцию, не таща ничего остального! Собственно говоря, именно для этого библиотеками и придумали. Программисты, помещающие реализации всех функций своей библиотеки в один-единственный файл, совершают большую ошибку!

Из всех рассматриваемых компиляторов, только Intel C++ умеет отслеживать неиспользуемые функции, предотвращая их включение в obj (для этого ему необходимо указать ключ–ipo, активирующий режим глобальной оптимизации).



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


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

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

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

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



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


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

int fact(int n, int result)

{

       if(n == 0)

       {

              return result;

       }

              else

       {

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

       }

}



Внос инвариантных функций из циклов


Инвариантными

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

Рассмотрим типичный пример:

for(a=0;a<strlen(s);a++) b+=s[a];



С точки зрения прикладного программиста,


С точки зрения прикладного программиста, компилятор — это черный ящик, заглатывающий исходный текст и выплевывающий двоичный файл. Какие процессы протекают в его "пищеварительном тракте" — неизвестно. Разработчики компиляторов крайне поверхностно описывают механизмы оптимизации в прилагаемой документации, так и не давая ответа на вопрос: _что_ именно оптимизирует компилятор, а что нет.
Как следствие — одни разработчики пишут ужасно кривой код, надеясь, что все огрехи исправит компилятор (он же ведь "оптимизирующий!"). Другие же, наоборот, пытаются помощь компилятору, оптимизируя программу вручную и выполняя кучу глупых и ненужных действий, например, заменяя a = b/4 на a = b >> 2, хотя _любой_ компилятор сделает это и сам, а вот поместить в регистр переменную, переданную по ссылке, он уже не решается (почему — см. "удаление лишних обращений к памяти"), то же самое относится и к выносу инвариантных функций из тела цикла.
Для достижения наивысшей эффективности, необходимо помочь компилятору, придерживаясь определенных привил программирования (кстати говоря, не описанных в штатной документации). Если вы недовольны быстродействием откомпилированной программы, не спешите переписать ее на ассемблер. Попробуйте сначала оптимизировать код путем реконструкции исходного текста. В большинстве случаев, вы получите тот же самый результат, но потратите меньше времени и сохраните переносимость.

Собирать свою коллекцию как надо


Собирать свою коллекцию как надо и как не надо оптимизировать программы мыщъх начал еще давно (здесь приведена лишь крошечная ее часть). Время шло, компиляторы совершенствовались и все больше примеров перемещалось из первой категории во вторую. А затем… разработчики компиляторов поутихли и со временен Microsoft Visual C++ 6.0 новых рывков что-то не наблюдается, поэтому у статьи есть все шансы сохранить свою актуальность в течении нескольких лет. А, возможно, и нет.