Geum.ru

Низкоуровневое программирование для Дzenствующих

Вид материалаДокументы

Содержание


Часть 1 (продолжение)
Листинг 1.4. Удельное время выполнения машинных команд внутри профилируемого фрагмента программы
Информация о пенальти
Intel и AMD
Подобный материал:
1   ...   28   29   30   31   32   33   34   35   ...   42

Часть 1 (продолжение)

Удельное время выполнения


Если время выполнения некоторой точки программы не постоянно, а варьируется в тех или иных пределах (например, в зависимости от рода обрабатываемых данных), то трактовка результатов профилировки становится неоднозначной, а сам результат — ненадежным. Для более достоверного анализа требуется:

а) определить действительно ли в программе присутствуют подобные "плавающие" точки и, если да, то:

б) определить время их исполнения в лучшем, худшем и среднем случаях.

Очень немногие профилировщики могут похвастаться способностью определять удельное время выполнения машинных команд (иначе называемое растактовкой). К счастью, профилировщик VTune это умеет! Обратимся к сгенерированному им протоколу динамического анализа. Быть может, он поможет нам разрешить загадку "неповоротливости" загрузки указателя pswd?

Листинг 1.4. Удельное время выполнения машинных команд внутри профилируемого фрагмента программы



Line Instructions Dyn-Retirement Cycles

107 pswd[p] = '!';

107 mov edx, DWORD PTR [ebp+0ch] 13 ************

107 ; загрузить в регистр EDX указатель pswd


107 add edx, DWORD PTR [ebp-4] 2 **

107 ; сложить регистр EDX с переменной p


107 mov BYTE PTR [edx], 021h 3 ***

107 ; записать в *(pswd+p) значение '!'


109 y = y | y << 8;

109 mov eax, DWORD PTR [ebp-28] 2 **

109 ; загрузить в регистр EAX переменную y


109 shl eax, 08h 1 *

109 ; сдвинуть EAX на 8 позиций влево


109 mov ecx, DWORD PTR [ebp-28] (0,7.3,80)

109 ; загрузить в регистр ECX переменную y *******


109 or ecx, eax 1 *

109 ; ECX = ECX | EAX (tmp = y | y)


109 mov DWORD PTR [ebp-28], ecx 1 *

109 ; записать полученный результат в y


110 x -= k;

110 mov edx, DWORD PTR [ebp-24] 0

110 ; загрузить в регистр EDX переменную x


110 sub edx, DWORD PTR [ebp-36] 1 *

110 ; вычесть из регистра EDX переменную k


110 mov DWORD PTR [ebp-24], edx 1 *

110 ; записать полученный результат в x

Ну, вот опять, — все команды, как команды, а загрузка указателя pswd "разлеглась" прямо как объевшаяся свинья, "сожравшая" целых тринадцать тактов, в то время как остальные свободно укладываются в один–два такта, а некоторые и вовсе занимают ноль, ухитряясь завершиться одновременно с предыдущей инструкций.

За исключением команды, загружающей содержимое переменной y в регистр ECX, время выполнения всех остальных команд строго постоянно и не меняется от случая к случаю. Наша же "подопечная" в зависимости от еще не выясненных обстоятельств, может "отъедать" даже восемьдесят тактов, что на время делает ее самой "горячей" точкой данного фрагмента программы. Восемьдесят тактов — это вообще полный беспредел! И пускай среднеарифметическое время ее выполнения составляет всего лишь семь тактов, а минимальное — и вовсе ноль, мы не успокоимся пока не выясним: на что и при каких именно обстоятельствах уходит такое количество тактов?

Информация о пенальти


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

Возвратимся к предыдущему вопросу: почему указатель pswd загружается так долго? И при каких именно обстоятельствах загрузка переменной y "подскакивает" со своих обычных семи до восьмидесяти тактов? Судя по всему, процессору что-то не понравилось и он обложил эти две машинные команды "штрафом" (penalty), на время притормозив их исполнение. Можем ли мы узнать, когда и за какой "проступок" это произошло? Не прибегая к полной эмуляции процессора — вряд ли (хотя современные процессоры x86 с некоторыми ограничениями позволяют получить эту информацию и так).

Гранды компьютерной индустрии — Intel и AMD уже давно выпустили свои профилировщики, содержащие полноценные эмуляторы выпускаемых ими процессоров, позволяющие визуализировать нюансы выполнения каждой машинной инструкции.

Просто щелкните по строке mov ecx, DWORD PTR [ebp-28] и профилировщик VTune выдаст всю, имеющуюся у него информацию (листинг 1.5).

Листинг 1.5. Вывод профилировщиком VTune дополнительной информации о выполнении инструкции

Decoder Minimum Clocks = 1 ; Минимальное время декодирования – 1 такт
Decoder Average Clocks = 8.7 ; Эффективное время декодирования – 8,7 тактов
Decoder Maximum Clocks = 86 ; Максимальное время декодирования – 86 тактов

Retirement Minimum Clocks = 0, ; Минимальное время завершения – 0 тактов
Retirement Average Clocks = 7.3 ; Эффективное время завершения – 7,3 такта
Retirement Maximum Clocks = 80 ; Максимальное время завершения – 80 тактов

Total Cycles = 80 (00,65%) ; Всего времени исполнения – 80 тактов

Micro-Ops for this instruction = 1 ; Кол-во микроопераций в инструкции – 1

The instruction had to wait 0 cycles for it's sources to be ready
("Инструкция ждала 0 тактов пока подготавливались ее операнды, т.е. попросту она их не ждала совсем")

Dynamic Penalty: IC_miss
The instruction was not in the instruction cache, so the processor loads the instruction from the L2 cache or main memory.
("Инструкция отсутствовала в кодовом кэше, и процессор был вынужден загружать ее из кэша второго уровня или основной оперативной памяти")
Occurances = 1 ; Такое случалось 1 раз

Dynamic Penalty: L2instr_miss
The instruction was not in the L2 cache, so the processor loads the instruction from main memory.
("Инструкция отсутствовала в кэше второго уровня и процессор был вынужден загружать ее из основной оперативной памяти")
Occurances = 1 ; Такое случалось 1 раз

Dynamic Penalty: Store_addr_unknown
The load instruction stalls due to the address calculation of the previous store instruction.
("Загружающая инструкция простаивала по той причине, что адрес источника рассчитывался предыдущей инструкцией записи")
Occurances = 10 ; Такое случалось 10 раз

Так, кажется, наше расследование превращается в самый настоящий детектив, еще более запутанный, чем у Агаты Кристи. Если приложить к полученному результату даже самый скромный арифметический аппарат, получится полная чепуха и полное расхождение "дебита с кредитом". Судите сами. Полное время выполнения инструкции — 80 тактов, причем, известно, что она выполнялась 11 раз (см. в листинге 1.3 колонку count отчета профилировщика). А наихудшее время выполнения инструкции составило… 80 тактов! А наихудшее время декодирования и вовсе — 86! То есть, худшее время декодирования инструкции превышает общее время ее исполнения и при этом в десяти итерациях она еще ухитряется простаивать как минимум один такт за каждую итерацию по причине занятости блока расчета адресов. Да… тут есть от чего "поехать крышей"!

Причина такого несоответствия заключается в относительности самого понятия времени. Вы думаете время относительно только у Эйнштейна? Отнюдь! В конвейерных процессорах (в частности процессорах Pentium и AMD K6/Athlon) понятие "времени выполнения инструкции" вообще не существует в принципе (см. подразд. "Конвейеризация или пропускная способность VS-латентность" гл. 1). В силу того, что несколько инструкций могут выполняться параллельно, простое алгебраическое суммирование времени их исполнения даст значительно больший результат, нежели исполнение занимает в действительности.

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

При большом количестве итераций (а при "живом" исполнении программы оно и впрямь велико) временем начальной загрузки можно и пренебречь, но… Стоп! Ведь профилировщик исполнил тело данного цикла всего 11 раз, в результате чего среднее время выполнения этой инструкции составило 7,3 тактов, что совершенно не соответствует реальной действительности!

Ой! Оказывается, это вовсе не "горячая" точка! И тут совершенного нечего оптимизировать. Если мы увеличим количество прогонов профилировщика хотя бы в четыре раза, среднее время выполнения нашей инструкции понизится до 1,8 тактов и она окажется одним из самых "холодных" мест программы! Точнее — это вообще абсолютный ноль, поскольку эффективное время исполнения данной инструкции — ноль тактов (т. е. она завершается одновременно с предыдущей машинной командой). Словом, мы "промахнулись" по полной программе.

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

Короткое лирическое отступление на тему: почему же все так произошло. По умолчанию VTune прогоняет профилируемый фрагмент 1.000 раз. Много? Не спешите с ответом. Наш хитрый цикл устроен так, что его тело получает управление лишь каждые 'z' '!' = 0x59 итераций (см. листинг 1.2). Таким образом, за все время анализа тело цикла будет исполнено всего лишь 1.000/89 = 11 раз! Причем, ни в коем случае нельзя сказать, что это надуманный пример. Напротив! В программном коде такое встречается сплошь и рядом.

Листинг 1.6. Демонстрация кода, некоторые участки которого прогоняются профилировщиком относительно небольшое количество раз, что искажает результат профилировки

while((++pswd[p])>'z') // <- данный цикл прогоняется профилировщиком 1.000 раз
{
pswd[p] = '!'; // <- данная инструкция прогоняется всего 11 раз
…
}

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

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

Действительно, — строка pswd[p] = '!' — это первая строка тела цикла, получающая управление каждые 0x59 итераций, что намного превосходит "проницательность" динамического алгоритма предсказания ветвлений, используемого процессором для предотвращения остановки вычислительного конвейера.

Следовательно, данное ветвление всегда предсказывается ошибочно и выполнение этой инструкции процессору приходится начинать с нуля. А процессорный конвейер — длинный. Пока он заполниться… Собственно, тут виновата вовсе не команда mov edx, DWORD PTR [ebp+0ch] — любая другая команда на ее месте исполнялась бы столь же непроизводительно! "Паяльная грелка, до красна нагревающая" эту точку программы, находится совсем в другом месте!

Поднимем курсор чуть выше, на инструкцию условного перехода предшествующую этой команде, и дважды щелкнем мышкой. Профилировщик VTune выдаст следующую информацию:

Decoder Minimum Clocks = 0 ; Минимальное время декодирования – 0 тактов

Decoder Average Clocks = 0 ; Эффективное время декодирования – 0 тактов

Decoder Maximum Clocks = 4 ; Максимальное время декодирования – 4 такта


Retirement Average Clocks = 1 ; Эффективное время завершения – 1 такт


Total Cycles = 1011 (08,20%) ; Всего времени исполнения – 1010 тактов (8,2%)


Micro-Ops for this instruction = 1 ; Кол-во микроопераций в инструкции – 1


The instruction had to wait (8,11.1,113) cycles for it's sources to be ready

("Эта инструкция ждала минимально 8, максимально 113,

а в основном 11,1 тактов пока ее операнды не были готовы")


Dynamic Penalty: BTB_Miss_Penalty ; Штраф типа BTB_Miss_Penalty

This instruction stalls because the branch was mispredicted.

("Эта инструкция простаивала потому что ветвление не было предсказано")

Occurances = 13 ; Такое случалось 13 раз

Наша гипотеза полностью подтверждается. Это ветвление тринадцать раз предсказывалось неправильно, о чем VTune и свидетельствует! Постой, как тринадцать?! Ведь тело цикла исполняется только одиннадцать! Да, правильно, одиннадцать. Но ведь процессор наперед этого не знал, и дважды пытался передать на него управление, и лишь затем, "увидев", что ни одно из двух предсказаний не сбылось, "плюнул и поклялся", что никогда–никогда не поставит свои фишки на эту ветку.

ОК. Когда загадки разрешаются — это приятно. Но главный вопрос несколько в другом: как именно их разрешать? Хорошо, что в нашем случае непредсказуемый условный переход находился так близко к "горячей" точке, но ведь в некоторых (и не таких уж редких) случаях "виновник" бывает расположен даже в других модулях программы! Ну что на это сказать… Подходите к профилировке комплексно и всегда думайте головой. Пожалуй, ничего более действенного я не смогу посоветовать…

(продолжение следует)