Материал взят со статьи Профилировка программ жестоким, но выборочным копипастом. Ниже представлены выжимки из статьи, отредактированные, разукрашенные, которые ответили на ряд моих вопросов.
Профилировка "в малом" - измерение времени выполнения небольших фрагментов программы, а то и отдельных машинных команд. Профилировке в малом присущ ряд серьезных и практически неустранимых проблем, незнание которых зачастую приводит к грубым ошибкам интерпретации результата профилировки.
Конвейеризация или пропускная способность VS-латентность
Начнем с того, что в конвейерных системах такого понятия как "время выполнения одной команды" просто нет из-за использования в процесорах принципа конвейеризации команд.
Латентность — т. е. полное время прохождения продукции по конвейеру, может быть и не критична для неповоротливого технологического процесса производства (действительно, новые модели микросхем не возникают каждый день), но весьма ощутимо влияет на быстродействие динамичного процессора, обрабатывающего неоднородный по своей природе код. Продвижение машинных инструкций по конвейеру сопряжено с рядом принципиальных трудностей, — то не готовы операнды, то занято исполнительное устройство, то встретился условный переход (что равносильно переориентации нашего приборостроительного завода на производство новой модели) и… вместо безостановочного вращения конвейера мы наблюдаем его длительные простои, лишь изредка прерываемые короткими рывками, а затем вновь покой и тишина.
В лучшем случае время выполнения одной инструкции определяется пропускной способностью конвейера, а в худшем — его латентностью. Поскольку пропускная способность и латентность различаются где-то на порядок или около того, бессмысленно говорить о среднем времени выполнения инструкции. Оно не будет соответствовать никакой физической действительности.
Малоприятным следствием становится невозможность определения реального времени исполнения компактного участка кода (если, конечно, не прибегать к эмуляции процессора). До тех пор, пока время выполнения участка кода не превысит латентность конвейера (30 тактов для P6), мы вообще ничего не сможем сказать ни о коде, ни о времени, ни о конвейере!
Неточность измерений
А чем можно измерять время работы отдельных участков программы? В персональных компьютерах семейства IBM PC AT имеются как минимум два таких механизма: системный таймер (штатная скорость: 18,2 тика в секунду, т. е. 55 мс, максимальная скорость — 1 193 180 тиков в секунду или 0,84 мкс), часы реального времени (скорость 1024 тика в секунду т. е. 0,98 мс). В дополнении к этому в процессорах семейства Pentium появился так называемый регистр счетчик – времени (Time Stamp Counter), увеличивающийся на единицу при каждом такте процессорного ядра.
Теперь разберемся со всем этим хозяйством подробнее.
Системный таймер.
Системный таймер (с учетом времени, расходующегося на считывание показаний) обеспечивает точность порядка 5 мс, что составляет более двух десятков тысяч тактов даже в системе с частотой 500 МГц! Это — целая вечность для процессора. За это время он успевает перемолотить море данных, скажем, отсортировать сотни полторы чисел. Поэтому, системный таймер для профилирования отдельных функций непригоден. В частности, нечего и надеяться с его помощью найти узкие места функции quick sort! Да что там узкие места — при небольшом количестве обрабатываемых чисел он и общее время сортировки определяет весьма неуверенно.
Причем, прямого доступа к системному таймеру под нормальной операционной системой никто не даст, а минимальный временной интервал, еще засекаемый штатной Си-функций clock(), составляет всего лишь 1/100 сек, а это годиться разве что для измерения времени выполнения всей программы целиком.
Часы реального времени
Точность часов реального времени так же вообще не идет ни в какое сравнение с точность системного таймера (перепрограммированного, разумеется).
Time Stamp Counter
Первое знакомство с ним вызывает просто бурю восторга и восхищения "ну наконец-то Intel подарила нам то, о чем мы так долго мечтали!". Судите сами: во-первых, операционные системы семейства Windows (в том числе и "драконическая" в этом плане NT) предоставляют беспрепятственный доступ к машинной команде RDTSC, читающий содержимое данного регистра. Во-вторых, поскольку он инкрементируется каждый такт, создается обманчивое впечатление, что с его помощью возможно точно определять время выполнения каждой команды процессора. Увы! На самом же деле это далеко не так!
Начнем с того, что в конвейерных системах, как мы уже помним, вообще нет такого понятия как время выполнения команды, и следует говорить либо о пропускной способности, либо латентности. Сразу же возникает вопрос: а что же все-таки команда RDTSC измеряет? Документация Intel не дает прямого ответа, но судя по всему, RDTSC считывает содержимое регистра счетчика-времени в момент прохождения данной инструкции через соответствующее исполнительное устройство. Причем, RDTSC — это неупорядоченная команда, т. е. она может завершаться даже раньше предшествующих ей команд. Именно так и произойдет, если предшествующая ей команда простаивает в ожидании операндов.
Рассмотрим крайний случай, когда измеряется время выполнения минимальной порции кода (одна машинная команда уходит на то, чтобы сохранить считанное значение в первой итерации):
Листинг 1.8. Попытка замера времени выполнения одной машинной команды
rdtsc ; ЧИТАЕМ ЗНАЧЕНИЕ РЕГИСТРА ВРЕМЕНИ
; и помещаем его в регистры EDX и EAX
mov [clock], eax ; СОХРАНЯЕМ МЛАДШЕЕ ДВОЙНОЕ СЛОВО
; регистра времени в переменную clock
rdtsc ; ЧИТАЕМ РЕГИСТР ВРЕМЕНИ ЕЩЕ РАЗ
SUB EAX, [clock] ; ВЫЧИСЛЯЕМ РАЗНИЦУ ЗАМЕРОВ МЕЖДУ
; первым и вторым замером
При прогоне этого примера на P-III он выдаст 32 такта, вызывая тем самым риторический вопрос: "а почему, собственно, так много?" Хорошо, оставим выяснение обстоятельств "похищения процессорных тактов" до лучших времен, а сейчас попробуем измерять время выполнения какой-нибудь машинной команды, ну скажем, INC EAX, увеличивающей значение регистра EAX на единицу. Поместим ее между инструкциями RDTSC и перекомпилируем программу.
Вот это да! Прогон показывает все те же 32 такта. Странно! Добавим-ка мы еще одну INC EAX. Как это так — снова 32 такта?! Зато при добавлении сразу трех инструкций INC EAX контрольное время исполнения скачкообразно увеличивается на единицу, что составляет 33 такта. Четыре и пять инструкций INC EAX дадут аналогичный результат, а вот при добавлении шестой, результат изменений вновь возрастает на один такт.
Но ведь процессор Pentium, имея в наличии всего лишь одно арифметическое устройство, никак не может выполнять более одного сложения за такт одновременно! Полученное нами значение в три команды за такт — это скорость их декодирования, но отнюдь не исполнения! Чтобы убедиться в этом запустим на выполнение следующий цикл (листинг 1.9).
Листинг 1.9. Измерение времени выполнения 6х1000 машинных команд inc
@for: ; МЕТКА НАЧАЛА ЦИКЛА
inc eax ;\
inc eax ; +- ОДНА ГРУППА ПРОФИЛИРУЕМЫХ ИНСТРУКЦИЙ
inc eax ;/
INC EAX ;\
inc eax ; +- ВТОРАЯ ГРУППА ПРОФИЛИРУЕМЫХ ИНСТРУКЦИЙ
inc eax ;/
dec ecx ; УМЕНЬШИТЬ ЗНАЧЕНИЕ РЕГИСТРА ecx НА 1
; (здесь он используется в качестве
; счетчика цикла)
jnz @xxx ; ДО ТЕХ ПОР, ПОКА ecx НЕ ОБРАТИТСЯ В НОЛЬ
; перепрыгивать на метку @for
На P-III выполнение данного цикла займет отнюдь не ~2 000, а целых 6 781 тактов, что соответствует, по меньшей мере, одному такту, приходящемуся на каждую математическую инструкцию! Следовательно, в предыдущем случае, при измерении времени выполнения нескольких машинных команд, инструкция RDTSC "вперед батьки пролезла в пекло", сообщив нам совсем не тот результат, которого мы от нее ожидали!
Вот если бы существовал способ "притормозить" выполнение инструкции RDTSC до тех пор, пока полностью не будут завершены все предшествующие ей машинные инструкции… И такой способ есть! Достаточно поместить перед RDTSC одну из команд упорядоченного выполнения. Команды упорядоченного выполнения начинают обрабатываться только после схода с конвейера последней предшествующей ей неупорядоченной команды и, до тех пор пока команда упорядоченного выполнения не завершится, следующие за ней команды мирно дожидаются своей очереди, а не "лезут как толпа дикарей" вперед на конвейер.
Подавляющее большинство команд упорядоченного выполнения — это привилегированные команды (например, инструкции чтения/записи портов ввода-вывода) и лишь очень немногие из них доступны с прикладного уровня. В частности, к таковым принадлежит инструкция идентификации процессора CPUID.
Многие руководства (в частности и Ангер Фог в своем руководстве "How to optimize for the Pentium family of microprocessors" и технический документ "Using the RDTSC Instruction for Performance Monitoring" от корпорации Intel) предлагают использовать приблизительно такой код (листинг 1.10).
Листинг 1.10. Официально рекомендованный способ вызова инструкции RDTSC для измерения времени выполнения
xor eax,eax ; ВЫЗЫВАЕМ МАШИННУЮ КОМАНДУ cpuid,
CPUID ; после выполнения которой все
; предыдущие машинные инструкции
; гарантированно сошли к конвейера
; и потому никак не могут повлиять
; на результаты наших замеров
rdtsc ; ВЫЗЫВАЕМ ИНСТРУКЦИЮ rdtsc, КОТОРАЯ
; возвращает в регистре EAX младшее
; двойное слово текущего значения
; time stamp counter 'a
mov [clock],eax ; СОХРАНЯЕМ ПОЛУЧЕННОЕ ТОЛЬКО ЧТО
; значение в переменной clock
// … ;\
// ПРОФИЛИРУЕМЫЙ КОД ; +-ЗДЕСЬ ИСПОЛНЯЕТСЯ ПРОФИЛИРУЕМЫЙ КОД
// … ;/
xor eax,eax ; ЕЩЕ РАЗ ВЫПОЛНЯЕМ КОМАНДУ cpuid,
CPUID ; чтобы все предыдущие инструкции
; гарантированно успели покинуть
; конвейер
rdtsc ; ВЫЗЫВАЕМ ИНСТРУКЦИЮ rdtsc ДЛЯ ЧТЕНИЯ
; нового значение Time Stamp Count
sub eax,[clock] ; ВЫЧИСЛЯЕМ РАЗНОСТЬ ВТОРОГО И ПЕРВОГО
; замеров, тем самым определяя реальное
; время выполнения профилируемого
; ФРАГМЕНТА КОДА
К сожалению, даже этот, официально рекомендованный, код все равно не годится для измерения времени выполнения отдельных инструкций, поскольку полученный с его помощью результат представляет собой полное время выполнения инструкции, т. е. ее латентность, а отнюдь не пропускную способность, которая нас интересует больше всего.
Имеется и другая проблема, еще более серьезная, чем первая. Вы помните постулат квантовой физики, сводящийся к тому, что всякое измерение свойств объекта неизбежно вносит в этот объект изменения, искажающие результат измерений? Причем, эти искажения невозможно устранить простой калибровкой, поскольку изменения могут носить не только количественный, но и качественный характер.
Если профилируемый код задействует те же самые узлы процессора, что и команды RDTSC/CPUID, время его выполнения окажется совсем иным нежели в действительности! Никаким ухищрениями нам не удастся достигнуть точности измерений до одного–двух тактов!
Поэтому, минимальный промежуток времени, которому еще можно верить, составляет, как показывает практика и личный опыт автора, по меньше мере пятьдесят–сто тактов.
Отсюда следствие: штатными средствами процессора измерять время выполнения отдельных команд невозможно.
Аппаратная оптимизация
На мгновение отвлечемся от компьютеров и зададимся вопросом: можно ли с помощью обычной ученической линейки измерить толщину листа принтерной бумаги? На первый взгляд, тут без штангенциркуля ну никак не обойтись… Но, если взять с полсотни листов бумаги и плотно сложить их друг с другом… вы уже поняли куда я клоню? Пусть погрешность измерения толщины образовавшегося "кирпича" бумаги составит ± 1 мм, тогда — точность определения толщины каждого отдельно взятого листа будет не хуже чем ± 0,02 мм, что вполне достаточно для большинства повседневных целей!
Почему бы ни применить эту технику для измерения времени выполнения машинных команд? В самом деле, время выполнения одной команды так мало, что просто ничем его не измерить (см. подразд. "Неточность измерений"), но если мы возьмем сто или даже сто тысяч таких команд, то… Но, увы! Машинные команды ведут себя совсем не так, как листы бумаги. Неоднородность конвейера приводит к тому, что зависимость между количеством и временем выполнения команд носит ярко выраженный нелинейный характер.
К тому же, современные процессоры слишком умны, чтобы воспринимать переданный им на выполнение код буквально. Нет! Они подходят к этому делу весьма творчески. Вот, допустим, встретится им последовательность команд MOV EAX, 1; MOV EAX, 1; MOV EAX, 1, каждая из которых помещает в регистр EAX значение "1". Думаете, процессор как полный недоумок, исполнит все три команды? Да как бы не так! Поскольку, результат двух первых присвоений никак не используется, процессор отбросит эти команды как ненужные, затратив время лишь на их декодирование, и ощутимо сэкономит на их выполнении!
Оптимизация программного кода, выполняемая процессором на аппаратном уровне, значительно увеличивает производительность системы, занижая тем самым фактическое время выполнения машинных команд. Да, мы можем точно измерять сколько тактов выполнялся блок из тысячи таких-то команд, но следует с большой осторожностью подходить к оценке времени выполнения одной такой команды.
Низкая "разрешающая способность"
Учитывая, что пропускная способность большинства инструкций составляет всего один такт, а минимальный промежуток времени, который еще можно измерять, находится в районе пятидесяти — ста тактов, предельная разрешающая способность не эмулирующих профилировщиков не превышает полста команд.
Под "разрешающей способностью" здесь и далее понимается протяженность "горячей" точки более или менее уверенно распознаваемой профилировщиком.
Строго говоря, не эмулирующие профилировщики показывают не саму "горячую" точку, а некоторую протяжную область, к которой эта "горячая" точка принадлежит.
Фундаментальные проблемы профилировки "в большом"
Профилировкой "в большом" мы будем называть измерение времени выполнения структурных единиц программы (функций, многократно выполняемых циклов и т.д.), а то и всей программы целиком.
Профилировке "в большом" присущи свои проблемы. Это и непостоянство времени выполнения, и проблема "второго прохода", и необходимость учета наведенных эффектов… Словом, здесь есть над чем поработать!
Непостоянство времени выполнения
В статье ( Измерение времени выполнения алгоритма _ профилирование ) я сталкивался с тем , что результаты измерений времени выполнения варьируются от прогона к прогону, порой отличаясь один от другого более чем значительно.
Причины:
- программное непостоянство, связанное с тем, что в многозадачных операционных системах (в частности в Windows) профилируемая программа попадает под влияние чрезвычайно изменчивой окружающей среды;
- аппаратное непостоянство, вызванное внутренней "многозадачностью" самого железа.
Программное непостоянство
В многозадачной системе Windows, никакая программа не владеет всеми ресурсами системы единолично и вынуждена делить их с остальными задачами. А это значит, что скорость выполнения профилируемой программы не постоянна и находится в тесной зависимости от "окружающей среды". На практике разброс результатов измерений может достигать 10%—15%, а то и больше, особенно, если параллельно с профилировкой исполняются интенсивно нагружающие систему задачи.
Тем не менее, особой проблемы в этом нет, — достаточно лишь в каждом сеансе профилировки делать несколько контрольных прогонов и затем… нет, не усреднять, а выбирать замер с наименьшим временем выполнения. Дело в том, что измерения производительности — это не совсем обычные инструментальные измерения и типовые правила метрологии здесь неуместны. Процессор никогда не ошибается и каждый полученный результат точен. Другое дело, что он в той или иной степени искажен побочными эффектами, но! Никакие побочные эффекты никогда не приводят к тому, что программа начинает исполняться быстрее, нежели она исполняется в действительности, а потому, прогон с минимальным временем исполнения и представляет собой измерение в минимальной степени испорченное побочными эффектами.
Кстати, во многих руководствах утверждается, что перед профилировкой целесообразно выходить из сети ("что бы машина не принимала пакеты"), завершать все-все приложения, кроме самого профилировщика и вообще лучше даже "на всякий случай" перегрузиться. Все это чистейшей воды бред! Автор частенько отлаживал программы параллельно с работой в Word, приемом корреспонденции, загрузкой нескольких файлов из Интернета и при этом точность профилировки всегда оставалась удовлетворительной! Конечно, без особой нужды не стоит так рисковать, и параллельно работающие приложения перед началом профилировки, действительно, лучше завершить, но не следует доводить ситуацию до абсурда, и пытаться обеспечить полную "стерильность" своей машине.
Аппаратное непостоянство
Возможно, это покажется удивительным, но на аппаратном уровне время выполнения одних и тех же операций не всегда постоянно и подвержено определенным разбросам, под час очень большим и значительно превосходящим программную погрешность. Но, если последнюю, хотя бы теоретически, возможно ликвидировать (ну, например, запустить программу в однозадачном режиме), то аппаратное непостоянство неустранимо принципиально.
Почему оно — аппаратное непостоянство — вообще возникает? Ну, тут много разных причин. Вот, например, одна из них: если частота системной шины не совпадает с частотой модулей оперативной памяти, чипсету придется каждый раз выжидать случайный промежуток времени до прихода следующего фронта тактового импульса. Исходя из того, что один цикл пакетного обмена в зависимости от типа установленных микросхем памяти занимает от 5 до 9 тактов, а синхронизовать приходится и его начало, и его конец, нетрудно подсчитать, что в худшем случае мы получаем неоднозначность в 25%—40%.
Проблема "второго прохода"
Для достижения приемлемой точности измерений профилируемое приложение следует выполнить, по крайней мере, 9—12 раз, причем каждый прогон должен осуществляться в идентичных условиях окружения. Увы! Без написания полноценного эмулятора всей системы это требование практически невыполнимо. Дисковый кэш, сверхоперативная память обоих уровней, буфера физических страниц и история переходов чрезвычайно затрудняют профилировку программ, поскольку при повторных прогонах время выполнения программы значительно сокращается.
При профилировании многократно выполняющихся функций, результаты первых двух–трех прогонов стоит вообще откинуть, и категорически не следует их арифметически усреднять.
Напротив, при профилировании функций, исполняющихся в реальной программе всего один раз, следует обращать внимание лишь на время первого прогона и отбрасывать все остальные, причем, при последующих запусках программы необходимо каким-либо образом очистить все кэши и все буфера, искажающие реальную производительность.
Проблема наведенных эффектов
Исправляя одни ошибки, мы всегда потенциально вносим другие и потому после любых, даже совсем незначительных модификаций кода программы, цикл профилировки следует повторять целиком.
Вот простой и очень типичный пример. Пусть в оптимизированной программе встретилась функция следующего вида:
Листинг 1.13. Фрагмент кода, демонстрирующий ситуацию, в которой удаление лишнего кода может обернуться существенным и труднообъясним падением производительности
ugly_func(int foo)
{
int a;
<…>
if (foo<1) return ERR_FOO_MUST_BE_POSITIVELY;
for(a=1; a <= foo; a++)
{
<…>
}
}
Очевидно, если попытаться передать функции ноль или отрицательное число, то цикл for_a не выполнится ни разу, а потому принудительная проверка значения аргумента (в тексте она выделена жирным шрифтом) бессмысленна! Конечно, при больших значениях foo накладные расходы на такую проверку относительно невелики, но в праве ли мы надеяться, что удаление этой строки, по крайней мере, не снизит скорость выполнения функции?
Постойте, это отнюдь не бредовый вопрос, относящийся к области теоретической абстракции! Очень может статься так, что удаление выделенной строки будет носить эффект прямо противоположный ожидаемому, и вместо того чтобы оптимизировать функцию, мы даже снизим скорость ее выполнения, причем, весьма значительно!
Как же такое может быть? Да очень просто! Если компилятор не выравнивает циклы в памяти (как, например, MS VC), то с довольно высокой степенью вероятности мы рискуем нарваться на кэш-конфликт, облагаемый штрафным пенальти. А можем и не нарваться! Это уж как фишка ляжет. Быть может, эта абсолютно бессмысленная (и, заметьте, однократно выполняемая) проверка аргументов как раз и спасала цикл от штрафных задержек, возникающих в каждой итерации.
Сказанное относится не только к удалению, но и вообще любой модификации кода, влекущий изменение его размеров. В ходе оптимизации производительность программы может меняться самым причудливым образом, то повышаясь, то понижаясь без всяких видимых на то причин. Самое неприятное, что подавляющее большинство компиляторов не позволяет управлять выравниванием кода и, если цикл лег по неудачным с точки зрения процессора адресам, все, что нам остается так это добавить в программу еще один кусок кода с таким расчетом, чтобы он вывел цикл из неблагоприятного состояния, либо же просто "перетасовать" код программы, подобрав самую удачную комбинацию.
"Идиотизм какой-то", — скажите вы и будете абсолютно правы. К счастью, тот же MS VC выравнивает адреса функций по адресам, кратным 0x20 (что соответствует размеру одной кэш-линейки на процессорах P6 и K6). Это исключает взаимное влияние функций друг на друга и ограничивает область тасования команд рамками всего "лишь" одной функции.
Сформулируем три правила, которыми всегда следует руководствоваться при профилировке больших программ, особенно тех, что разрабатываются несколькими независимыми людьми. Представляете — в один "прекрасный" день вы обнаруживаете, что после последних внесенных вами "усовершенствований" производительность вверенного вам фрагмента неожиданно падает… Но, чтобы вы не делали, пусть даже выполнили "откат" к прежней версии, вернуть производительность на место вам никак не удавалось. А на завтра она вдруг — без всяких видимых причин! — сама восстанавливалась до прежнего уровня. Да, правильно, причина в том, что ваш коллега чуть-чуть изменил свой модуль, а это рикошетом ударило по вам!
Итак, обещанные правила при профилировке больших программ:
- никогда–никогда не оптимизируйте программу "вслепую", полагаясь на "здравый смысл" и интуицию;
- каждое внесенное изменение проверяйте на "вшивость" профилировщиком и, если производительность неожиданно упадает, вместо того чтобы увеличиться, незамедлительно устраивайте серьезные "разборки": "кто виноват" и "чья тут собака порылась", анализируя весь, а не только свой собственный код;
- после завершения оптимизации локального фрагмента программы, выполните контрольную профилировку всей программы целиком на предмет обнаружения новых "горячих" точек, появившихся в самых неожиданных местах.
Комментариев нет:
Отправить комментарий