linux.optimization.II
техника оптимизации под LINUX\\ часть II — ветвления
крис касперски ака мыщъх, no-email
сегодня мы продолжим сравнение Linux-компиляторов, начатое в прошлом номере журнала и рассмотрим оптимизацию условных переходов и операторов типа switch. механизмы их трансформации достаточно многочисленны и разнообразны. за последнее время было предложено множество новых идей, воплощенных в компиляторах GCC 3.3.4 и Intel C++ 8.0 (сокращенно icl), однако, древний Microsoft Visual C++ 6.0 (сокращенного msvc) не сдает своих позиций, так что не спешите списывать его в утиль и сдавать на свалку.
оптимизация ветвлений/branch
Ветвления (по-английски branch, они же условные/безусловныепереходы) относятся к фундаментальным основам любого языка, без которых не обходится ни одна программа. Даже «hello, world!»! Ведь выход из функции main — это тоже ветвление, пускай и неявное (но ведь процессор синтаксисом языка не проведешь!). А сколько ветвлений содержит сама функция printf? А Библиотека времени исполнения?
Суперскалярные микропроцессоры, построенные по конвейерной архитектуре (а все современные микропроцессоры именно так и устроены), быстрее всего выполняют линейный код и ненавидят ветвления. В лучшем случае они дезориентируют процессор, слегка приостанавливая выполнение программы, в худшем же — полностью очищают конвейер. А на последних Pentium'ах он очень длинный (и с каждой последующей моделью становится все длиннее и длиннее). Быстро его не заполнишь… на это может уйти не одна сотня тактов, что вызовет обвальное падение производительности.
Оптимизация переходов дает значительный выигрыш, особенно если они расположены внутри циклов (кстати говоря, циклы это те же самые переходы), поэтому качество компилятора не в последнюю очередь определяется его умением полностью или частично избавляться от ветвлений.
выравнивание переходов
Процессоры, основанные на ядрах Intel P6 и AMD K6, не требуют выравнивания переходов, исключая тот случай, когда целевая инструкция или сама команда перехода расщепляется границей кэш-линейки напополам, в результате чего наблюдается значительное падение производительности. Наибольший ущерб причиняют переходы, находящиеся в циклах с компактным телом и большим уровнем вложения.
Чтобы этого не происходило, некоторые компиляторы прибегают к выравниванию, располагая инструкции перехода по кратным адресам и заполняют образующиеся дыры незначащими инструкциями, такими как XCHG EAX,EAX (обмен содержимого регистров EAX местами) или MOV EAX, EAX (пересылка содержимого EAX в EAX). Это увеличивает размер кода и несколько снижает его производительность, поэтому бездумное выравнивание (оно же «агрессивное») только вредит.
Легко показать, что машинная команда требует выравнивания в тех, и только тех случаях, когда условие 1) > 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 2) > cache_len)
align = cache_len – (addr % cache_len);
Листинг 1 формула для расчета оптимальной кратности выравнивания для процессоров от Intel Pentium II и выше
частичное вычисление условий
«Летят два крокодила — один квадратный, другой тоже на север» — вот хороший пример техники быстрого булевского вычисления (оно же «частичное вычисление условий», «Partialevaluationoftestconditions» или «short-circuiting»). Собственно, ничего «быстрого» в нем нет. Если первое из нескольких условий, связанных оператором AND, ложно (где видели квадратных крокодилов?), остальные уже не вычисляются. Соответственно, если первое из нескольких условий, связанных оператором OR, истинно, вычислять остальные нет нужды.
Кстати говоря, это отнюдь не свойство оптимизатора (как утверждают некоторые рекламные букеты), а требование языка, без которого ветвления вида: if (x && (y/x)) были бы невозможны. Все три рассматриваемых компилятора, поддерживают быстрое булево вычисление.
if 3)…
Листинг 2 если выражение (a == b) истинно, выражение (c == d) уже не проверяется
удаление избыточных проверок
Небрежное кодирование часто приводит к появлению избыточных или даже заведомо ложных проверок, полностью или частично дублирующих друг друга, например: «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++; elsereturn 0; заведомо ложна проверка
Листинг 3 не оптимизированный вариант
if (n > 10) a+=2; else return 0;
Листинг 4 оптимизированный вариант
удаление проверок нулевых указателей
Программисты до сих пор не могут определиться: кто должен осуществлять проверку аргументов — вызывающая или вызываемая функция. Многие стандарты кодирования предписывают выполнять такую проверку обоим:
f1(int *p)
{
if (p) return *p+1; else return –1;
}
f2(int *p)
{
if (p) *p = 0x69; else return -1;
return f1(p);
}
Листинг 5 не оптимизированный вариант
Лишние проверки увеличивают размер кода и замедляют его выполнение (особенно если находятся глубоко в цикле), поэтому компилятор gcc поддерживает специальный ключ, ‑fdelete-null-pointer-checks, вычищающий их из программы. Вся соль в том, что x86-процессоры (как и большинство других) на аппаратном уровне отслеживают обращения к нулевым указателям, автоматически выбрасывая исключение, если такое обращение действительно произошло. Поэтому, если проверке на «легитимность» указателя предшествует операция чтения/записи по этому указателю, эту проверку можно не выполнять. Допустим, наш указатель равен нулю, тогда исключение выпрыгнет при первом же обращении к нему (в нашем случае — при выполнении *p = 0x69) и до проверки дело просто не дойдет. Если же указатель не равен нулю — зачем его проверять?
Компиляторы msvc и icl такой техники оптимизации не поддерживают. Правда, в режиме глобальной оптимизации, icl может удалять несколько подряд идущих проверок (при встраивании функций это происходит достаточно часто), поскольку это является частным случаем техники удаления избыточных проверок, однако, ситуацию: «проверка/модификация-указателя/обращение-к-указателю/проверка», icl уже не осилит. А вот gcc справляется с ней без труда!
совмещение проверок
Совмещение проверок очень похоже на повторное использование подвыражений: если она и та же проверка присутствует в двух или более местах и отсутствуют паразитные зависимости по данным, все проверки можно объединить в одну:
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);
Листинг 6 не оптимизированный вариант, 2 проверки
if (CPU_TYPE == AMD) только одна проверка { x = AMD_f1(y); a = AMD_f2(b); } else { x = INTEL_f1(y); a = INTEL_f2(b); } Листинг 7 оптимизированный вариант, только одна проверка Из всех трех компиляторов, совмещать проверки умет только icl, да и то не всегда. ==== сокращение длины маршрута ==== Если один условный или безусловный переход указывает на другой безусловный переход, то все три рассматриваемых компилятора автоматически перенаправляют первый целевой адрес на последний, что и демонстрирует следующий пример: gotolab_1; переход к метке lab_1 на безусловный переход к метке lab_2
….
lab_1:gotolab_2; переход к метке lab_2 …. lab_2: Листинг 8 не оптимизированный вариант gotolab_2; сразу переходим к метке lab_2, минуя lab_1
….
lab_1:gotolab_2; переход к метке lab_2 …. lab_2: Листинг 9 оптимизированный вариант Разумеется, оператор goto необязательно должен присутствовать в программном коде в явном виде и он вполне можно быть «растворен» в цикле: while(a) lab_1:if (a) goto lab_4
{
while(b) lab_2:if (b) gotolab_3/* переход на безусловный переход */ { /* код цикла */ }gotolab_2
} lab_3:goto lab_1 lab_4:
Листинг 10 не оптимизированный вариант
После оптимизации этот код будет выглядеть так:
while(a) lab_1:if (a) goto lab_4 { while(b) lab_2:if (b) goto lab_1/* оптимизировано */
{
/* код цикла */
}goto lab_2 } lab_3:goto lab_1
lab_4: Листинг 11 оптимизированный вариант Аналогичным способом осуществляется и оптимизация условных/безусловных переходов, указывающих на другой условный переход. Вот, посмотрите: jmplab_1; переход на условный переход … lab_1: jnz lab_2 Листинг 12 не оптимизированный вариант jnzlab_2; оптимизировано … lab_1: jnz lab_2 Листинг 13 оптимизированный вариант Заметим, что в силу ограниченной «дальнобойности» условных переходов, в некоторых случаях длину цепочки приходится не только уменьшать, но и увеличивать, прибегая к следующему трюку: jz far_far_awayjnz next_lab ———трансформация—————>jmp far_far_away next_lab: Листинг 14 трансформация условных переходов, до которых процессор не может «дотянуться» Условный или безусловный переход, указывающий на выход из функции, всеми тремя компиляторами заменяется на непосредственный выход из функции, при условии, что код эпилог достаточно мал и накладные расходы на его дублирование невелики: f(int a, int b) { while(a–) { if (a == b) break; условный переход на return a; } return a; } Листинг 15 не оптимизированный вариант f(int a, int b) { while(a–) { if (a == b) return a; непосредственный return a; } return a; } Листинг 16 оптимизированный вариант ==== уменьшение кол-ва ветвлений ==== Все три компилятора просматривают код в поисках условных переходов, перепрыгивающих через безусловные (conditionalbranchesoverunconditionalbranches) и оптимизируют их: инвертируют условный переход, перенацеливая его на адрес безусловного перехода, а сам безусловный переход удаляют, уменьшая тем самым количество ветвлений на единицу: if (x) a=a*2; else goto lab_1; двойноеветвление if – else
b=a+1
lab_1:c=a*10
Листинг 17 не оптимизированный вариант
if (!x) gotolab_1; одинарное ветвление a=a*2; b=a+1; lab_1: c=a*10; Листинг 18 оптимизированный вариант Оператор goto необязательно должен присутствовать в тексте явно, он вполне может быть частью do/while/break/continue. Вот, например: while(1) { if (a==0x66) break; условный переход
a=a+rand();
}; скрытый безусловный переход на начало цикла Листинг 19 не оптимизированный вариант, 2 ветвления if (a!=0x66) «сдирание» одной итерации цикла
do{
a=a+rand();
}while(a!=0x66); инвертируем переход, только одно ветвление Листинг 20 оптимизированный вариант, 1 ветвление (ветвление перед началом цикла не считается, т.к. исполняется всего лишь раз) ==== сокращение количества сравнений ==== Процессоры семейства x86 (как и многие другие) обладают одну очень интересной концепцией, которой нет ни в одном языке высокого уровня. Операции вида if (a>b) выполняются в два этапа. Сначала из числа a вычитается число b и состояние вычислительного устройства сохраняется в регистре флагов. Различные комбинации флагов соответствуют различным отношениям чисел и за каждый из них отвечает «свой» условный переход. Например: cmpeax,ebx сравниваем eax с ebx, запоминая результат во флагах
jl lab_1 переход, если eax < ebx jg lab_2 переход, если eax > ebx
lab_3: раз мы здесь, eax == ebx Листинг 21 сравнение двух чисел на языке ассемблера На языках высокого уровня все не так, и операцию сравнения приходится повторять несколько раз подряд, что не способствует ни компактности, ни производительности. Но, может быть, ситуацию исправить оптимизатор? Рассмотрим следующий код: if (a < 0x69) printf(«b»); if (a > 0x69) printf(«g»); if (a == 0x69) printf(«e»); Листинг 22 сравнение двух чисел на языке высокого уровня Дизассемблирование показывает, что компилятору msvc потребовалось целых два сравнения, а вот icl было достаточно и одного. Компилятор gcc не заметил подвоха и честно выполнил все три сравнения. ==== избавление от ветвлений ==== Теория утверждает, что любой вычислительный алгоритм можно развернуть в линейную конструкцию, заменив все ветвления математическими операциями (как правило, запутанными и громоздкими). Рассмотрим функцию поиска максимума среди двух целых чисел: «4) на if ((unsignedint)a < MAX), — последняя конструкция на одно ветвление короче; * ветвление с проверкой на нуль оптимизируется намного проще, чем на любое другое значение; * конструкции типа x = (flag?sin:cos)(y) не избавляют от ветвлений, но сокращают объем кодирования; * не пренебрегайте оператором goto – зачастую он позволяет проектировать более компактный и элегантный код;


компилятор действие | Microsoft Visual C++ 6 | Intel C++ 8.0 | GCC 3.3.4 |
выравнивание переходов | не выравнивает | не выравнивает | выравнивает по границе степени двойки |
быстрое булево вычисление | поддерживает | поддерживает | поддерживает |
удаление избыточных проверок | не удаляет | удаляет | не удаляет |
удаление проверок нулевых указателей | не удаляет | не удаляет | удаляет |
совмещение проверок | не совмещает | совмещает | не совмещает |
сокращение длины маршрута | сокращает | сокращает | сокращает |
уменьшение кол-ва ветвлений | уменьшает | уменьшает | уменьшает |
сокращение количества сравнений | сокращает | частично сокращает | не сокращает |
избавление от ветвлений | избавляется от ветвлений константного типа | никогда не избавляется | избавляется всегда, когда это возможно |
балансировка логического древа | троичное дерево, сбалансированное улучшенным методом отрезков | двоичное, несбалансированное дерево | троичное дерево, сбалансированное методом отрезков |
создание таблицы переходов | создает | создает | создает |
поддержка разряженной таблицы переходов | поддерживает | поддерживает | поддерживает |
совмещение таблицы переходов с деревом | совмещает | не совмещает | не совмещает |