девятый. VTune – ваш персональный тренер
А теперь мы обратимся к наименее известному средству профилировщика VTune – Инструктору (в оригинале Coach так же переводимое как "тренер" или "учитель").
Фактически инструктор – это ни что иное как высококлассный интерактивный оптимизатор, поддерживающий целый ряд языков: C, C++, FORTRAN и Java. Он анализирует исходный текст программы на предмет поиска "слабых" мест, а обнаружив такие – дает подробные рекомендации по их устранению.
Разумеется, интеллектуальность Инструктора не идет ни в какое сравнение с сообразительностью живого программиста и вообще, как мы увидим в дальнейшем, Инструктор скорее туп, чем умен… все-таки рассмотреть его поближе будет небесполезно.
Несмотря на то, что Инструктор в первую очередь ориентирована на программистов-новичков (на что указывает полностью "разжеванный" стиль подсказок), и для профессионалов он под час оказывается не лишним, особенно когда приходится оптимизировать чужой код, в котором лень досконально разбираться.
Плохая новость (впрочем, ее и следовало ожидать)– при отсутствии отладочной информации в профилируемой программе инструктор не может работать с исходным текстом и опускается на уровень чистого ассемблера (см. "Шаг десятый"). Тем не менее, это обстоятельство не доставляет непреодолимых неудобств, т.к. текст программы именно анализируется, но не профилируется. Поэтому, пусть вас не смущает, что включение в исполняемый файл отладочной информации приводит к автоматическому "вырубанию" всех оптимизирующих опций компилятора. Инструктор, работая с исходным текстом программы, вообще не будет касаться скомпилированного машинного кода!
Итак, перекомпилируем нашу демонстрационный пример, добавив ключ "/Zi" в командную строку компилятора и ключ "/DEBIG" – в командную строку линкера. Загрузим полученный файл в VTune и, дождавшись появления диаграммы "Hot Spots", дважды щелкнем мышкой по самому высокому прямоугольнику, соответствующему, как мы уже знаем, функции gen_pswd, в которой программа проводит большую часть своего времени.
Loop unrolling
Examples: C, Fortran, Java*
The loop contains instructions that do not allow efficient instruction scheduling and pairing. The instructions are few or have dependencies that provide little scope for the compiler to schedule them in such a manner as to make optimal use of the processor's multiple pipelines. As a result, extra clock cycles are needed to execute these instructions.
Advice
Unroll the loop as suggested by the coach. Create a loop that contains more instructions, but is executed fewer times. If the unrolling factor suggested by the coach is not appropriate, use an unrolling factor that is more appropriate.
To unroll the loop, do the following:
– Replicate the body of the loop the recommended number of times.
– Adjust the index expressions to reference successive array elements.
–Adjust the loop control statements.
Result:
– Increases the number of machine instructions generated inside the loop.
– Provides more scope for the compiler to reorder and schedule instructions so that they pair and execute simultaneously in the processor's pipelines.
– Executes the loop fewer times.
Caution:
Be aware that increasing the number of instructions within the loop also increases the register pressure.
В переводе на русский язык все вышесказанное будет звучать приблизительно таким образом:
Разворачивание цикла:
Данный цикл содержит инструкции, которые не могут быть эффективно спланированы и распараллелены процессором, поскольку они малочисленны [то бишь кворума мы здесь не наберем – КК] или содержат зависимости, что сужает возможности компилятора в их группировке для достижения наиболее оптимального использования конвейеров процессора. В результате, на выполнение этих инструкций расходуется значительно большее количество циклов.
Совет:
Развертите цикл, согласно советам "Учителя". Создайте цикл, что содержит больше инструкций, но исполняется меньшее количество раз.
Если степень развертки, рекомендуемая "Учителем", кажется вам неподходящей, используйте более подходящую степень.
Для развертки цикла сделайте следующее:
– Продублируйте тело цикла соответствующее количество раз;
– Скорректируйте ссылки на продублированные элементы массива;
– Скорректируйте условие цикла.
Результат:
– Увеличивается количество машинных инструкций внутри цикла;
– Появляется место, где "развернуться" компилятору для переупорядочивания и планирования потока инструкций так, чтобы они спаривались и выполнялись параллельно в конвейерах процессора.
– Выполнение цикла занимает меньшее время.
Предостережение:
Знайте, что увеличение количества инструкций в теле цикла влечет за собой увеличение "регистрового давления".
Согласитесь, весьма исчерпывающее руководство по развертке циклов! Причем, если вам все равно не понятно как именно разворачиваются циклы, можно кликнуть по ссылке "Examples" (примеры) и увидеть конкретный пример "продразверстки" на Си, Java или Fortran. Давайте выберем "Си" и посмотрим, что нам еще посоветует VTune:
Original Code Optimized Code
for(i=0; i<n; i++) for(i=0; i<n-(n%3); i+=3)
a[i] = c[i] ; {
a[i] = c[i] ;
a[i+1] = c[i+1];
a[i+2] = c[i+2];
}
for(i;i < n; i++)
a[i] = c[i];
Тем не менее, мы этот цикл разворачивать не будем и пойдем дальше. Совет номер два вновь рекомендует развернуть тот же самый цикл, но уже находящийся внутри цикла while. Поскольку, этот цикл получает управление лишь при удлинении перебираемого пароля на один символ (что происходит прямо-таки скажем не часто) он, как и предыдущий, не оказывает практически никакого влияния на производительность, а потому рекомендацию по его развороту мы отправим в /dev/null.
Совет номер три придирается к с виду безобидной конструкции p++, увеличивающий переменную p на единицу:
114 p++;
115 if (!pswd[p])
116 {
117 pswd[p]='!';
118 pswd[p+1]=0;
119 length++;
120 x = -1;
121 for (b = 0; b <= length; b++)
122 x += *(int *)((int)pswd + b);
The loop whose index is incremented at line 114 should be interchanged with the loop whose index is incremented at line 121, for more efficient memory access
"Для достижения более эффективного доступа [к памяти] цикл, чей индекс увеличивается в строке 114, должен быть заменен циклом, чей индекс увеличивается в строке 121". ?! Инструктор судя по всему или пьян или от перегрева процессора спятил. Это вообще разные циклы. И индексы у них разные. И вообще они не имеют к друг другу никакого отношения, причем цикл, расположенный в строке 121, исполняется редко, так что совсем не понятно, что это VTune к нему так пристал?!
Может быть, дополнительная информация от Инструктора все разъяснит? Дважды щелкаем по строке 114 и читаем:
Loop interchange:
Loops with index variables referencing a multi-dimensional array are nested. The order in which the index variables are incremented causes out-of-sequence array referencing, resulting in many data cache misses. This increases the loop execution time.
Advice:
Do the following:
– Change the sequence of the array dimensions in the array declaration.
– Interchange the loop control statements.
Result:
The order in which the array elements are referenced is more sequential. Fewer data cache misses occur, significantly reducing the loop execution time.
Перестановка циклов:
Здесь наблюдается вложенные циклы с индексными переменными, обращающимися к многомерным массивам, Порядок, в котором увеличиваются индексные переменные, приводит к несвоевременному обращению к массивам, и как следствие этого – множественным кэш-промахам.
В результате увеличивается время выполнения цикла.
Совет:
Сделайте следующее:
– Измените последовательность измерений массивов в их объявлении;
– Поменяйте местами "измерения" управление цикла
[подразумевается: сделайте либо то, либо это, но ни в коем случае ни то и другое вместе – иначе "минус на минус даст плюс" и вы получите тот же самый результат – КК]
Результат:
Порядок, в котором обрабатываются элементы массива станет более последовательным. Меньше кэш-промахов будет происходить, от чего время выполнения цикла значительно сократиться.
Какие многомерные массивы? Какие кэш-промахи? Здесь у нас и близко нет ни того, ни другого! Судя по всему мы столкнулись с грубой ошибкой Инструктора (шаблонный поиск дает о себе знать!) но все же не поленимся, а заглянем в предлагаемый Инструктором пример, памятуя о том, что всегда в первую очередь следует искать ошибку у себя, а не у окружающих. Быть может, это мы чего-то недопонимаем…
|
Original Code |
Optimized Code |
|
|
int b[200][120]; void xmpl17(int *a) { int i, j; for (i = 0; i < 120; i++) for (j = 0; j < 200; j++) b[j][i]=b[j][i]+a[2*j]; } |
int b[200][120]; void ympl17(int *a) { int i, j; int atemp; for (j = 0; j < 200; j++) for (i = 0; i < 120;i++) b[j][i]=b[j][i]+a[2*j]; } |
Ну вот, все правильно. Приводимый VTune фрагмент кода наглядно демонстрирует, что к двухмерные массивы лучше обрабатывать по строкам, а не столбцам (см. "Часть II. Кэш"). Но ведь у нас нет двухмерных массивов, а – стало быть – и слушаться Инструктора в данном случае не надо.
Совет номер четыре и слова этот несчастный цикл подсчета контрольной суммы. Ну понравился от Инструктору – что поделаешь! Что же ему не понравилось на этот раз? Читаем…
121 for (b = 0; b <= length; b++)
122 x += *(int *)((int)pswd + b);
123 pswd[p]=' ';
124 y = 0;
125 }
126 } // end while(pswd)
Use the Intel C/C++ Compiler vectorizer to automatically generate highly optimized SIMD code. The statement on line 122 and others like it will be vectorized if the following program changes are made (double-click on any line for more information):
==> Simplify the pointer expression to indicate contiguous array accesses.
==> Restructure the loop to isolate the statement or construct that interferes with vectorization.
==> Try loop interchanging to obtain vector code in the innermost loop.
==> Simplify the pointer expression to indicate contiguous array accesses.
Используйте векторизатор компилятора Intel С/C++ для автоматической генерации высоко оптимизированного SIMD-кода. Оператор, находящийся в линии 122 и остальные подобные ему операторы, будут векторизованы при условии следующих изменений программы:
==> Упростите выражение указателя для индикации смежных доступов к массиву;
==> Реструктурируйте цикл для отделения выражения или логической конструкции, препятствующей векторизации;
==> Попытайтесь перестроить цикл для получения векторного кода во вложенном цикле;
==> Упростите выражение указателя для индикации смежных доступов к массиву;
Хорошие, однако, советы! А рекомендация упростить и без того примитивную форму адресации повторяется аж два раза! И это при том, что векторизовать данный цикл все равно не получится даже на Intel C/C++, а уж про все остальные компиляторы я и вовсе промолчу.
Тем не менее, все-таки заглянем в помощь – может быть, что-нибудь интересное скажут!
Intel C++ Compiler Vectorizer
The coach has identified an assignment or expression that is a candidate for SIMD technology code generation using Intel C++ Compiler vectorizer.
Advice
Use the Intel C++ Compiler vectorizer to automatically generate highly optimized SIMD code wherever appropriate in your application.
Use the following syntax to invoke the vectorizer from the command line: prompt> icl -O2 -QxW myprog.cpp.
The -QxW command enables vectorization of source code and provides access to other vectorization-related options.
Result
The Intel C++ Compiler vectorizer optimizes your application by processing data in parallel, using the Streaming SIMD Extensions of the Intel processors. Since the Streaming SIMD Extensions that the class library implements access and operate on 2, 4, 8, or 16 array elements at one time, the program executes much faster.
Векторизатор компилятора Intel C++
Инструктор идентифицирован присвоение или выражение, являющееся кандидатом для генерации кода по SIMD-технологии, используемой векторизатором компилятора Intel C++.
Совет:
Используйте векторизатор компилятора Intel C++ для автоматической генерации высоко оптимизированного SIMD-кода, подходящего к вашему приложению. Используйте следующий синтаксис для вызова векторизатора из командной строки: icl –O2 QxW myprog.cpp.
Ключ "-QxW" разрешает векторизацию исходного кода и предоставляет доступ к остальным векторным опциям.
Результат:
Векторизатор компилятора Intel C++ оптимизирует ваше приложение путем парализации обработки данных, с использованием поточного SIMD-расширения команд процессоров Intel. С тех пор как потоковые SIMD расширения библиотеки классов осуществляют доступ и обработку 2, 4, 8 или 16 элементов массива за один раз, скорость выполнения программы весьма значительно возрастает.
Бесспорно, векторизация – полезная штука, действительно позволяющая многократно увеличить скорость работы программы, но ее широкому внедрению в массы препятствует по меньшей мере два минуса: во-первых, подавляющее большинство x86-компилятор не умеют векторизовать код, а переход на компилятор Intel не всегда приемлем. Во-вторых, векторизация будет по настоящему эффективна лишь в том случае, если программа изначально заточена под эту технологию. И хотя в мире "больших" машин векторизация кода известна уже давно, для x86-программистов это еще тот конек!
Совет номер пять или еще один просчет Инструктора. Так, посмотрим, что за перл выдал Инструктор на этот раз.
91 if (x==validCRC)
92 {
93 // копируем шифроданные во временный буфер
94 buff = (char *) malloc(strlen(crypteddata));
95 strcpy(buff, crypteddata);
96
97 // расшифровываем
98 DeCrypt(pswd, buff);
99
The argument list for the function call to _malloc on line 94 appears to be loop-invariant. If there are no conflicts with other variables in the loop, and if the function has no side effects and no external dependencies, move the call out of the loop.
(Список аргументов функции malloc, находящейся в строке 94, вероятно, инвариантен относительно цикла. Если это не вызовет конфликта с остальными переменными цикла, и если не имеет посторонних эффектов и внешних зависимостей, вынесите ее за пределы цикла).
Вообще-то, формально Инструктор прав. Вынос инвариантных функций из тела цикла – хороший тон программирования, поскольку, находясь в теле цикла, функция вызывается множество раз, но, в силу своей независимости от параметров цикла, при каждом вызове дает один и тот же результат. Действительно, не проще ли единожды выделив память при входе в функцию, просто сохранить возращенный malloc указатель в специальной переменной, а затем использовать его по мере необходимости?
Возражения: ну и что мы в результате этого получим? Данная ветка вызывается лишь при совпадении контрольной суммы текущего перебираемого пароля с эталонной контрольной суммой, что происходит крайне редко – в лучшем случае несколько раз за все время выполнения программы.
Возражение номер два: перефразируя известный анекдот "я девушку кормил-поил, я ее и танцевать буду" можно сказать "та ветвь программы, которая выделила блок памяти, сама же его и освобождает, конечно, если это не приводит к неоправданному снижению производительности".
Таким образом, ничего за пределы цикла мы выносить не будем, что бы там нам не советовал Инструктор.
Совет номер шесть. Данный совет практически полностью повторяет предыдущий, однако, на этот раз, Инструктор посоветовал вынести за пределы цикла функцию De Crypt. Да, да! Счел ее инвариантом и посоветовал вынести куда подальше и это не смотря на то, что: а) код самой функции в принципе был в его распоряжении ("в принципе" потому, что мы приказали Инструктору анализировать только gen_pswd). б) функции De Crypt
передается указатель pswd, который явным образом изменяется в цикле! А раз так, то инвариантом De Crypt
быть ну никак не может! И как только Инструктору не стыдно давать такие советы? Или все-таки стыдно – а вы думали почему он красный такой?
Совет номер семь. Сейчас Инструктор обращает наше внимание, на то, что: "The value returned by De Crypt() on line 98 is not used…" ("Значение, возвращаемое функцией De Crypt, расположенной в строке 98, не используется..") и дает следующий совет "If the return value is being ignored, write an alternate version of the function which returns void" ("Если возвращенное значение игнорируется, создайте альтернативную версию данной функции, возвращающей значение void").
В основе данного совета лежит допущение Инспектора, что функция, не возвращающая никакого значения, будет работать быстрее функции такое значение возвращающей. На самом деле это более, чем спорно. Во-первых, возврат значения занимает не так уж много времени, во-вторых, большинство компиляторов при выходе из void
функций все равно возвращают "ноль", а вовсе ни "ничто". В-третьих, создание двух экземпляров одной функции обойдется много дороже, чем накладные расходы на возврат никому не нужного значения.
Так что игнорируем этот совет и идем дальше.
Совет номер восемь. Теперь Инспектор принял за инвариант функцию printf, распечатывающую содержимое буфера buff, только что возвращенного функцией De Crypt.
Мм… не ужели разработчикам VTune было трудно заложить в башку Инспектора смысловое значение хотя бы основных библиотечных функций? Функция printf
не зависимо от того является ли она инвариантом или нет, никогда не может быть вынесена за пределы цикла! И вряд ли стоит объяснять почему.
Совет номер девять. …Значение, возвращаемое функций printf не используется, поэтому…
Что ж! Результатами такого инструктажа трудно остаться удовлетворенным. Из девяти советов мы не воспользовались ни одним, поскольку это все равно бы не увеличило скорость выполнения программы. Тем не менее, Инструктора не стоит считать совсем уж никчемным чукчей. Во всяком случае он рассказывает о действительно интересных и эффективных приемах оптимизации, не все из которых известны новичкам.
Возможно мне возразят, что такая непроходимая тупость Инструктора объясняется тем, что мы подсунули ему уже до предела оптимизированную программу и ему ничего не осталось, как придираться к второстепенным мелочам. Хорошо, давайте напустим Инструктора на самый первый вариант программы, заставив его проанализировать весь код целиком. Он сделает нам 33 замечания, из которых полезных по прежнему не окажется ни одного!
