Автор: (c)Крис Касперски ака мыщъх
Большое тестовое сравнение Linux-компиляторов продолжается! Тема сегодняшнего исследования - циклы и их оптимизация. В основном мы будем говорить о трех наиболее популярных компиляторах - GCC 3.3.4, Intel C++ 8.0 и Microsoft Visual C++ 6.0, к которым теперь присоединился и GCC 4.0.0 со своим новым оптимизатором циклов.
По статистике до 90% времени исполнения программ приходится на глубоко вложенные циклы, от качества оптимизации которых зависит быстродействие всей программы в целом. Современные компиляторы поддерживают множество прогрессивных технологий оптимизации и способны буквально на чудеса!
Стратегия оптимизации циклов тесно связана с архитектурой процесса, кэш-контроллера и контроллера оперативной памяти. Это слишком объемная, можно даже сказать - монументальная тема и в рамках настоящей статьи она не обсуждается. Читайте документацию, распространяемую фирмами Intel и AMD (причем не только по процессорам, но и по чипсету) или мою "Технику оптимизации программ - эффективная работа с оперативной памяти", электронная версия которой свободно распространяется через файлообменные сети. Там эти вопросы описаны достаточно подробно.
Выравнивание циклов (loop alignment) имеет много общего с выравниванием ветвлений, о котором мы уже говорили в предыдущей статье. Кратно опишем ситуацию для тех, кто не в курсе. Компиляторы msvc и icl вообще не выравнивают циклы, располагая их в памяти как бог на душу положит. В худшем случае это приводит к трех-четырехкратному падению производительности и в среднем теряется порядка 30% быстродействия.
Компилятор gcc позволяет выравнивать циклы на величину, кратную степени двойки. За это отвечает ключ -falign-loops=n (по умолчанию n равен двум, что, как уже отмечалось, далеко не самая лучшая стратегия выравнивания и предпочтительнее использовать n, равный четырем). Ключ -fno-align-loops (аналогичный ключу -falign-loops=1) отключает выравнивание. На уровнях оптимизации -O2 и -O3 выравнивание циклов по умолчанию включено и отключать его было бы неразумно.
Итоги:
msvc: не выравнивает
icl: не выравнивает
gcc: выравнивает по границе степени двойки
Микропроцессоры с конвейерной архитектурой (а к таковым относятся все современные x86-процессоры), плохо приспособлены для работы с циклами. Для достижения наивысшей производительности процессору необходим достаточно протяженный участок "трассы выполнения", свободный от ветвлений. Компактные циклы вида for (a = 0; a < n; a++) *dst ++= *src++; исполняются очень медленно и для увеличения быстродействия приходится прибегать к их развороту (unrolling). Под "разворотом" в общем случае понимается многократное дублирование цикла, которое реализуется приблизительно так:
Листинг 1. Цикл до разворота.
Листинг 2. Цикл после разворота (меньший размер, большая скорость).
Листинг 3. Цикл после разворота (меньший размер, меньшая скорость - машинное представление i++ намного более компактно, чем (i + const). Однако, если выражения ...(n % i + const_1) + (n % i + const_2) ... могут выполняться одновременно, то ...(n % i++) + (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 итераций, циклы с const <= 32 разворачивает полностью: циклы с const > 32 разворачивает на величину, кратную const, но не больше 10h, учитывает количество инструкций в цикле; циклы разворачиваются по сценарию "больший размер - большая скорость"
gcc: на уровне O3 по умолчанию не разворачивает; циклы с переменным кол-вом итераций никогда не разворачиваются; циклы с постоянным кол-вом итераций разворачиваются на ~4x (но тут все зависит от числа инструкций)
Идея шелушения циклов (по-английски "peeling") заключается в "сдирании" с цикла одной или нескольких итераций с последующей трансформацией в линейный код. Фактически, шелушение циклов является частным случаем разворота, однако область его применения одним лишь разворотом не ограничивается.
Рассмотрим следующий код:
Листинг 4. Кандидат на оптимизацию.
Чтобы объединить оба цикла в один (см. "объединение циклов"), необходимо "содрать" с цикла j одну "лишнюю" итерацию:
Листинг 5. Оптимизированный вариант.
Компилятор msvc шелушить циклы не умеет, icl и gcc - умеют, но особой радости от этого никто не испытывает, поскольку они никогда не комбинируют "шелушение" с другими приемами оптимизации, что обеспечивает выигрыш (а вот компиляторы от SUN или Hewlett-Packard - комбинируют!).
Компилятор gcc содержит специальный ключ -fpeel-loops, полностью разворачивающий циклы с небольшим количеством итераций. Пороговое значение назначается ключами max-peel-times (сколько итераций можно сдирать с одного цикла), max-completely-peel-times (максимальное количество итераций цикла, который еще может быть развернут), max-completely-peeled-insns (максимальное количество инструкций, при которых цикл еще может быть развернут) и max-peeled-insns (максимальное количество инструкций развернутого цикла) .
Итоги:
msvc: не шелушит
gcc: шелушит
icl: шелушит
Фальцевание циклов (fold loops) внешне очень похоже на разворот, но преследует совсем другие цели, а именно - увеличение количества потоков данных на одну итерацию. Чем выше плотность (strength) потоков, тем выше параллелизм обработки данных, а значит и скорость выполнения цикла.
Рассмотрим следующий пример:
Листинг 6. Неоптимизированный вариант - один поток данных на итерацию.
Чтобы сократить время выполнения цикла, необходимо увеличить количество потоков, переписав наш код так:
Листинг 7. Оптимизированный вариант - четыре потока данных на итерацию.
Все три рассматриваемых компилятора поддерживают данную стратегию оптимизации.
Итоги:
msvc: фальцует
gcc: фальцует
icl: фальцует
Начиная с Pentium MMX, в x86-процессорах появилась поддержка векторных команд (они же "мультимедийные"). К сожалению, в ANSI Си векторные операции отсутствуют, а нестандартные языковые расширения создают проблему переносимости, поэтому вся забота по векторизации циклов ложится на компилятор. Он должен проанализировать исходный код и определить, какие операции могут выполняться параллельно, а какие нет.
Допустим, исходный цикл выглядел так:
Листинг 8. Цикл до векторизации.
Используя общепринятую векторную нотацию, его можно переписать так:
a[0:N] = a[0:N] + b[0:N];
Листинг 9. Тот же цикл, записанный в векторной нотации.
Старшие представители процессоров Pentium могут обрабатывать до 8 порций данных параллельно и если N превышает это число, то приходится поступать так:
Листинг 10. Цикл после векторизации.
Однако это методика срабатывает далеко не всегда. Вот пример цикла, который нельзя векторизовать:
Листинг 11. Цикл который нельзя векторизовать.
Поскольку последующая ячейка (a[i]) вычисляется на основе предыдущей (a[i - 1]) данные не могут обрабатываться параллельно.
Компилятор msvc не поддерживает векторизацию, а icl поддерживает, но задействует ее только в том случае, если указан ключ -ax. Компилятор gcc поддерживает векторизацию только начиная с версии 3.4.3, да и то, если присутствует флаг -ftree-vectorize.
Итоги:
msvc: не векторизует
icl: векторизует
gcc: векторизует начиная с версии 3.4.3
Многопроцессорные машины на рабочем столе - это не утопия, а объективная данность и с каждым годом их количество будет только расти. В операционных системах семейства LINUX многозначность заканчивается на уровне потоков (в старых ядрах - процессах). Всякий поток в каждый момент времени может выполняться только на одном процессоре. Программы, состоящие целиком из одного потока, на многопроцессорной машине исполняются с той же скоростью, что и на однопроцессорной.
Некоторые компиляторы автоматически разбивают большие (с их точки зрения) циклы на несколько циклов меньшего размера, помещая каждый из них в свой поток. Такая техника оптимизации называется авто-параллелизмом (auto-parallelization). Продемонстрируем ее на следующем примере:
Листинг 12. Неоптимизированный вариант.
Поскольку зависимость по данным отсутствует, цикл можно разбить на два. Первый будет обрабатывать ячейки от 0 до XXL/2, а второй - от XXL/2 до XXL. Тогда на двухпроцессорной машине скорость выполнения цикла практически удвоится.
Листинг 13. Оптимизированный вариант.
Компилятор icl - единственный из всех трех, способный на "параллелизацию" циклов. Чтобы ее задействовать, используйте ключ -parallel, только помните, что при выполнении кода на однопроцессорных машинах оптимизация дает обратный эффект (накладные расходы на организацию потоков дают о себе знать).
Итоги:
msvc: авто-параллелизм не поддерживается
icl: авто-параллелизм поддерживается
gcc: авто-параллелизм не поддерживается
Разворот цикла традиционными методами (см. "Разворот циклов") порождает зависимость по данным. Вернемся к листингу 3. Смотрите - хотя загрузка обрабатываемых ячеек происходит параллельно (ну... практически параллельно - они будут ползти по конвейеру, находясь на различных стадиях готовности), следующая операция сложения не может быть начата до тех пор, пока не будет завершена предыдущая.
Для усиления параллелизма, необходимо суммировать все ячейки в своих переменных, как показано ниже:
Листинг 15. Оптимизированный вариант.
Такая техника оптимизации называется программной конвейеризацией (software pipelining) и из трех рассматриваемых компиляторов ею не обладает ни один. Только gcc робко пытается ослабить зависимость по sum, используя два регистра при развороте на четыре итерации. Остальные же компиляторы грузят все ячейки в один и тот же регистр, очевидно, руководствуясь принципом экономии. Регистров общего назначения всего семь и их постоянно не хватает. К сожалению, компилятор не отличает ситуацию действительного дефицита регистров от их избытка, вынуждая нас прибегать к ручной оптимизации.
Итоги:
msvc: программная конвейеризация не поддерживается
icl: программная конвейеризация не поддерживается
gcc: программная конвейеризация частично поддерживается
Цикл называется индуктивным, если его тело целиком состоит из выражения, последующее значение которого вычисляется на основе предыдущего. Легко доказать, что значение индуктивного цикла зависит только от количества итераций и начального значения аргументов выражения, благодаря чему оно может быть вычислено еще на стадии компиляции.
Рассмотрим следующий пример:
Листинг 16. Индуктивный цикл до оптимизации.
Очевидно, что конечное значение sum равно:
sum += XXL;
Листинг 17. Индуктивный цикл после оптимизации.
Компилятор msvc всегда пытается предвычислить значение индуктивного цикла, однако далеко не всегда это ему удается, особенно если индуктивное выражение представляет собой сложную математическую формулу. Два остальных компилятора оставляют индуктивные циклы такими, какие они есть, даже не пытаясь их оптимизировать!
Итоги:
msvc: предвычисляет некоторые индуктивные циклы
icl: не предвычисляет индуктивные циклы
gcc: не предвычисляет индуктивные циклы
Если индуктивный цикл предвычислить не удалось, необходимо, по крайней мере, ослабить зависимость между итерациями, чтобы они могли исполняться параллельно. Рассмотрим следующий код:
Листинг 18. Индуктивный цикл до оптимизации.
Выражение (a[i] = x) не может быть выполнено до тех пор, пока не будет вычислено (x += 2), а оно, в свою очередь, должно дожидаться завершения предыдущей итерации. Индукция, однако! Но от нее можно избавиться, вычисляя значение n-й итерации на "лету":
Листинг 19.. Индуктивный цикл после оптимизации.
Расплатой за отказ от индукции становится появление "лишней" инструкции умножения, однако, накладные расходы на ее выполнение с лихвой окупаются конвейеризацией (а при желании - и векторизацией!) цикла. Такая техника оптимизации называется "разбивка длинных цепочек зависимостей" (breaks long dependency chains) и реализована только в последних версиях gcc (за это отвечает ключ -fsplit-ivs-in-unroller), а все остальные рассматриваемые компиляторы на это, увы, не способны.
Итоги:
msvc: не разбивает длинные цепочки зависимостей
icl: не разбивает длинные цепочки зависимостей
gcc: разбивает длинные цепочки зависимостей
Хвостовой рекурсией (tail recursion) называется такой тип рекурсии, при котором вызов рекурсивной функции следует непосредственно за оператором return. Классическим примером хвостовой тому является алгоритм вычисления факториала:
Листинг 20. Хвостовая рекурсия до оптимизации.
Вызов функции - достаточно "дорогостоящая" операция и от него лучше избавится. Это легко! Хвостовая рекурсия легко трансформируется в цикл. Смотрите:
Листинг 21.Хвостовая рекурсия после оптимизации.
Компиляторы msvc и gcc всегда разворачивают хвостовую рекурсию в цикл, а вот icl этого делать не умеет.
Итоги:
msvc: устраняет хвостовую рекурсию
icl: не устраняет хвостовую рекурсию
gcc: устраняет хвостовую рекурсию
Несколько циклов с одинаковым заголовком могут быть объедены в один, сокращая накладные расходы на его организацию. Эта методика имеет множество названий - loops fusion, merge loops, jam loops, создающих большую путаницу и вводящих программистов в заблуждение. В действительности же, это не три различных стратегии оптимизации, а всего лишь одна, но какая! Продемонстрируем ее на следующем примере:
Листинг 22. Циклы до объединения (неоптимизированный вариант).
Поскольку заголовки обоих циклов абсолютно идентичны, нам достаточно лишь объединить их содержимое:
Листинг 23. Циклы после объединения (оптимизированный вариант).
А вот более сложный пример:
Листинг 24. Кандидат на оптимизацию путем объединения.
Непосредственно объединить циклы невозможно, поскольку цикл j на одну итерацию короче. Чтобы уравнять оба заголовка в правах, предварительно необходимо "содрать" (см. "loop peeling") с цикла i одну итерацию:
Листинг 25. Оптимизированный вариант.
Документация на компилятор icl утверждает, что объединение циклов как будто бы поддерживается (см. главу "loop transformation" фирменного руководство), однако дизассемблирование показывает, что это не так. Остальные компиляторы объединение циклов также не выполняют и на это способен только компилятор от Hewlett-Packard и другие "серьезные" компиляторы для больших машин.
Итоги:
msvc: не объединяет циклы
icl: не объединяет циклы
gcc: не объединяет циклы
Трепание циклов (loop spreading) представляет собой разновидность шелушения, при котором "содранные" итерации упаковываются в самостоятельный цикл, что бывает полезным, например, при объединении двух циклов с "разнополыми" заголовкам.
Рассмотрим следующий код:
Листинг 26. Два цикла с различным количеством итераций (неоптимизированный вариант).
Если n не равно m, полное объединение циклов i и j уже невозможно, но min(n, m) итераций мы все же можем объединить:
Листинг 27. Частичное объединение циклов путем "трепки" (оптимизированный вариант).
Ни msvc, ни icl, ни gcc способностью к "трепке" циклов не обладают, однако это умеют делать, например, компиляторы от Hewlett-Packard.
Итоги:
msvc: не треплет циклы
icl: не треплет циклы
gcc: не треплет циклы
Расщепление циклов (loop distribution, loop fission, loop splitting...) прямо противоположно их объединению. К такому трюку прибегают в тех случаях, когда оптимизируемый цикл содержит слишком много данных. Ассоциативность кэш-памяти первого уровня у большинства x86-процессоров равна четырем, реже - восьми, а это значит, что каждая обрабатывая ячейка данных может претендовать лишь на одну из четырех (восьми) возможных кэш-линеек и если они к этому времени уже заняты ячейками остальных потоков, происходит их неизбежное вытеснение из кэша, многократно снижающее производительность.
Рассмотрим следующий пример:
Листинг 28. Неоптимизированный вариант.
Чтобы сократить количество потоков данных, следует вынести выражение (c[j] = 0) в отдельный цикл, переписав код так:
Листинг 29. Оптимизированный вариант.
Компилятор icl, кстати говоря, именно так и поступает, снимая это бремя с плеч программиста. Остальные рассматриваемые компиляторы этой способностью, увы, не обладают.
Итоги:
msvc: не расщепляет циклы
icl: расщепляет циклы
gcc: не расщепляет циклы
Нормализованным называется цикл, начинающийся с нуля, и в каждой итерации увеличивающий свое значение на единицу, а приведение произвольного цикла к указанной форме называется его нормализацией (loop normalization). Принято считать, что на большинстве архитектур нормализованный цикл компилируется в более компактный и быстродействующий код, однако в отношении x86-процессоров это совсем не так и более компактным оказывается цикл, стремящийся к нулю (см. "Стремление циклов к нулю"). Тем не менее, нормализация бывает полезной, например, при объединении двух циклов с различными заголовками. Если эти циклы предварительно нормализовать, тогда они будут отличаться друг от друга всего лишь числом итераций, а как объединять циклы с несовпадающим количеством итераций мы уже знаем (см. "Трепание циклов").
Возьмем произвольный цикл:
Листинг 30. Ненормализованный цикл.
В общем случае, стратегия нормализации выглядит так:
Листинг 31. Нормализованный цикл.
Легко показать, что нормализация дает выигрыш только на циклах с заранее известным количеством итераций, позволяющих вычислить значение выражения (upper - lower + incre) / incre еще на стадии компиляции.
Все три рассматриваемых компилятора поддерживают нормализацию циклов (см. раздел loop normalization в документации на icl и описание ключа -fivcanon компилятора gcc), но не всегда ею пользуются.
Рассмотрим следующий пример:
Листинг 32. Ненормализованный цикл.
Очевидно, что его можно нормализовать, одним махом избавившись от нескольких "лишних" инструкций (кстати говоря, XOR reg,reg - обнуление регистра reg - намного более компактно, чем MOV reg, const - инициализация регистра константой):
Листинг 33. Нормализованный цикл.
Поразительно, но ни один из трех рассматриваемых компиляторов этого не делает, поэтому все они получают "незачёт".
Итоги:
msvc: нормализует некоторые циклы
icl: нормализует некоторые циклы
gcc: нормализует некоторые циклы
Масштабированием (scaling) в общем случае называется умножение индекса массива на некоторое, как правило, целочисленное значение, например, x = a[4 * i]. Идея масштабирования циклов заключается в выносе множителя в индуктивный инкремент счетчика цикла.
Допустим, исходный цикл выглядел так:
Листинг 34. Исходный цикл (неоптимизированный вариант).
После масштабирования он приобретает следующий вид:
Листинг 35. Цикл после масштабирования (оптимизированный вариант).
Во времена XT/AT такая оптимизация еще имела смысл, но начиная с 80386 в процессорах появилась аппаратная поддержка масштабирования на 2х, 4х, 8х и с некоторыми ограничениями на 3х, 5х и 9х, поэтому масштабировать такие циклы уже не нужно.
Масштабирование поддерживают все три рассматриваемых компилятора, но пользуются им довольно неумело, оставляя цикл несмаштабированным даже тогда, когда это ему явно не помешало бы.
Итоги:
msvc: масштабирует некоторые циклы
icl: масштабирует некоторые циклы
icl: масштабирует некоторые циклы
Циклы с предусловием (for, while) содержат, по меньшей мере, на одно ветвление больше, чем аналогичные им циклы с постусловием. Как нетрудно сообразить - в конце цикла с предусловием находится безусловный переход, возвращающий управление в начало, а в цикле с постусловием передача управления по "совместительству" еще выполняет и проверку условия.
Все три рассматриваемых компилятора всегда заменяют циклы с предусловиям на циклы с постусловием, когда это выгодно.
Итоги:
msvc: заменяет циклы с предусловием на циклы с постусловием
icl: заменяет циклы с предусловием на циклы с постусловием
gcc: заменяет циклы с предусловием на циклы с постусловием
На большинстве процессорных архитектур инструкция декремента (уменьшения регистра на единицу) автоматически взводит специальный флаг при достижении нуля, поэтому цикл, стремящийся к нулю (incrementing by zero, хотя правильнее было назвать его decrementing by zero), намного выгоден как с точки зрения компактности, так и с точки зрения быстродействия.
Рассмотрим следующий код:
Листинг 36. Неоптимизированный вариант.
Поскольку никаких обращений к счетчику цикла здесь нет, его можно развернуть в обратном направлении. Это легко. А вот пример посложнее:
Листинг 37. Неоптимизированный вариант.
В этом случае за трансформацию цикла приходится расплачиваться усложнением его тела, однако выигрыш по-прежнему остается на нашей стороне:
Листинг 38. Оптимизированный вариант.
Компилятор msvc всегда стремится генерировать циклы, стремящиеся к нулю, icl этого не делает вообще, а gcc прибегает к трансформации циклов только в некоторых, наиболее очевидных случаях. В частности, он избегает трогать циклы, содержащие ссылки на память.
Итоги:
msvc: всегда стремит циклы к нулю
icl: никогда не стремит циклы к нулю
gcc: стремит некоторые циклы к нулю
Многие микропроцессоры имеют специальную команду: уменьши-регистр-на-единицу-и-ветвись-если-нуль (branch-count-reg). На x86-процессорах этим занимается LOOP, часто встречающаяся в ассемблерных вставках начинающих программистов, но практически никогда в коде, сгенерированном компилятором. И вовсе не потому, что компилятор "тупой", а потому, что эта инструкция медленная, хотя и компактная.
Компиляторы msvc и icl никогда ее не используют, а gcc предоставляет специальный ключ -fbranch-count-reg, предписывающий выбирать LOOP вместо DEC reg/JNZ begin_loop, правда, до машинного когда она все равно не доживает и уничтожается оптимизатором.
Итоги:
msvc: не использует branch-count-reg
icl: не использует branch-count-reg
gcc: не использует branch-count-reg
Ветвления, инвариантные по отношению цикла, могут быть вынесены за его пределы путем расщепления одного цикла на два или более. Размеры кода при этом возрастают, но и производительность увеличивается (конечно, при условии, что цикл влезает в кэш).
Покажем это на следующем примере:
Листинг 39. Цикл с инвариантным ветвлением (неоптимизированный вариант).
Поскольку ветвление if (n < 0x669) инвариантно по отношению к циклу j, мы от него избавляемся:
Листинг 40. Оптимизированный вариант.
На суперкомпьютерных компиляторах такая техника оптимизации используется уже давно и называется loop promotion, loop interchange или loop unswitching, но на PC она впервые появилась только в последней версии компилятора gcc. Этим заведует ключ -funswitch-loops (задействовать вынос инвариантных ветвлений), max-unswitch-insns (максимальное количество инструкций, которое может иметь "расщепляемый" цикл) и max-unswitch-level (максимальное количество инвариантный ветвлений, которые может иметь "расщепляемый цикл").
Приверженцы остальных компиляторов вынуждены выносить инварианты самостоятельно.
Итоги:
msvc: не выносит инвариантные ветвления
icl: не выносит инвариантные ветвления
gcc: выносит инвариантные ветвления, начиная с версии 3.4.3
Бесконечные циклы с выходом по break могут быть преобразованы в конечные циклы с постусловием. При этом, тело цикла как бы прокручивается, чтобы оператор break переместился на место while(1), а сам while(1) сомкнулся с оператором do и "коллапсировал".
Продемонстрируем это на следующем примере:
Листинг 41. Неоптимизированный вариант.
После ротации ветвлений наш код будет выглядеть так:
Листинг 42.Оптимизированный вариант.
Из всех трех рассматриваемых компиляторов удалять лишние ветвления умеет лишь один лишь msvc.
Итоги:
msvc: выполняет ротацию ветвлений
icl: не выполняет ротацию ветвлений
gcc: не выполняет ротацию ветвлений
При обращении к одной-единственной ячейки памяти в кэш первого уровня загружается целая строка, длина которой в зависимости от типа процессора варьируется от 32 до 128 или даже 256 байт, поэтому большие массивы выгоднее всего обрабатывать по строкам, а не по столбцам. К сожалению, многие программисты об этом забывают и "отдуваться" приходится компилятору:
Листинг 44. Обработка массивов по столбцам (неоптимизированный вариант).
Здесь три массива обрабатываются по столбцам, что крайне непроизводительно и для достижения наивысшей эффективности циклы i и j следует поменять местами. Устоявшегося названия у данной методики оптимизации нет и в каждом источнике она называется по-разному: loop permutation/interchange/reversing, rearranging array dimensions и т.д. Как бы там ни было, результирующий код выглядит так:
Листинг 45. Обработка массивов по столбцам (оптимизированный вариант).
Все три рассматриваемых компилятора поддерживают данную стратегию оптимизации, однако их интеллектуальные способности очень ограничены и со следующим примером не справился ни один.
Листинг 46. Сложный случай обработки данных по столбцам.
А вот компиляторы от Hewlett-Packard оптимизируют этот цикл так (хвост цикла для упрощения понимания не показан):
Листинг 47. Оптимизированный вариант с разворотом на 4 итерации (обратите внимание, какой цикл был развернут!)
Оптимизатор скомбинировал сразу три методики: разворот, объединение и переупорядочивание циклов, благодаря чему скорость выполнения значительно возросла. К сожалению, еще долгое время PC-программистам придется оптимизировать свои программы самостоятельно, хотя стремительное совершенствование gcc дает робкую надежду на изменение ситуации.
Итоги:
msvc: частично упорядочивает обращения к памяти
icl: частично упорядочивает обращения к памяти
gcc: частично упорядочивает обращения к памяти
Действие | Microsoft Visual C++ 6 | Intel C++ 8.0 | GCC 3.3.4 |
Выравнивание циклов | Не выравнивает | Не выравнивает | Выравнивает по границе степени двойки |
Разворот циклов | Не разворачивает | Разворачивает циклы без ветвлений с переменным и постоянным кол-вом итераций | Разворачивает циклы с постоянным кол-вом итераций |
Шелушение циклов | Не шелушит | Шелушит | Шелушит |
Векторизация циклов | Не векторизует | Векторизует | Векторизует, начиная с версии 3.4.3 |
Авто-параллелизм | Не поддерживает | Поддерживает | Не поддерживает |
Программная конвейеризация | Не поддерживает | Не поддерживает | Частично поддерживает |
Предвычисление индуктивных циклов | Предвычисляет простые циклы | Не предвычисляет | Не предвычисляет |
Разбивка длинных цепочек зависимостей | Не разбивает | Не разбивает | Разбивает, начиная с версии 4.0.0 |
Устранение хвостовой рекурсии | Устраняет | Не устраняет | Устраняет |
Объединение циклов | Не объединяет | Не объединяет | Не объединяет |
Трепание циклов | Не поддерживает | Не поддерживает | Не поддерживает |
Расщепление циклов | Не расщепляет | Расщепляет | Не расщепляет |
Нормализация циклов | Нормализует некоторые циклы | Нормализует некоторые циклы | Нормализует некоторые циклы |
Масштабирование циклов | Масштабирует некоторые циклы | Масштабирует некоторые циклы | Масштабирует некоторые циклы |
Замена циклов с предусловием на циклы с постусловием | Заменяет | Заменяет | Заменяет |
Стремление циклов к нулю | Всегда стремит циклы к нулю | Никогда не стремит циклы к нулю | Стремит некоторые циклы к нулю |
Branch-count-reg | Не использует | Не использует | Не использует |
Вынос инвариантных ветвлений | Не выносит | Не выносит | Выносит, начиная с версии 3.4.3 |
Ротация ветвлений | Выполняет | Не выполняет | Не выполняет |
Упорядочивание обращение к памяти | Частично упорядочивает обращения к памяти | Частично упорядочивает обращения к памяти | Частично упорядочивает обращения к памяти |
Прогресс не стоит на месте и со времен появления msvc компиляторы сделали большой шаг вперед. Особенно порадовал gcc 4.0.0 с его новым оптимизатором циклов, который намного превосходит icl с msvc, вместе взятых. Тем не менее, до совершенства ему еще далеко. Некоторые техники, присутствующие еще в msvc, в нем не реализованы (например, ротация ветвлений), не говоря уже про "серьезные" компиляторы от Hewlett-Packard. Так что, "на компилятор надейся, а сам не плошай"!