Tempora mutantur, et nos mutamur in illis




НазваниеTempora mutantur, et nos mutamur in illis
страница4/9
Дата публикации09.03.2013
Размер1.08 Mb.
ТипДокументы
uchebilka.ru > Информатика > Документы
1   2   3   4   5   6   7   8   9
^

Фундаментальные проблемы профилировки "в большом"


Профилировкой "в большом" мы будем называть измерение времени выполнения структурных единиц программы (функций, многократно выполняемых циклов и т.д.), а то и всей программы целиком.

Профилировке "в большом" присущи свои проблемы. Это и непостоянство времени выполнения, и проблема "второго прохода", и необходимость учета наведенных эффектов… Словом, здесь есть над чем поработать!


^

Непостоянства времени выполнения


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

Причин такого непостоянства существует по меньшей мере две: программное непостоянство, связанное с тем, что в многозадачных операционных системах (в частности в Windows) профилируемая программа попадает под влияние чрезвычайно изменчивой окружающей среды, и аппаратное непостоянство, вызванное внутренней "многозадачностью" самого железа.

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


^
Программное непостоянство

В многозадачной среде, коей и является популярнейшая на сегодняшний день операционная система Windows, никакая программа не владеет всеми ресурсами системы единолично и вынуждена делить их с остальными задачами. А это значит, что скорость выполнения профилируемой программы не постоянна и находится в тесной зависимости от "окружающей среды". На практике разброс результатов измерений может достигать 10% –15%, а то и больше, особенно если параллельно с профилировкой исполняются интенсивно нагружающие систему задачи.

Тем не менее, особой проблемы в этом нет, – достаточно лишь в каждом сеансе профилировки делать несколько контрольных прогонов и затем… нет, не усреднять, а выбирать замер с наименьшим временем выполнения. Мотив такой: измерения производительности – это не совсем обычные инструментальные измерения и типовые правила метрологии здесь неуместны. Процессор никогда не ошибается и каждый полученный результат точен. Другое дело, что он в той или иной степени искажен побочными эффектами, но! никакие побочные эффекты никогда не приводят к тому, чтобы программа начинает исполняться быстрее, нежели она исполняется в действительности, а потому, прогон с минимальным временем исполнения и представляет собой измерение в минимальной степени испорченное побочными эффектами.

Кстати, во многих руководствах утверждается, что перед профилировкой целесообразно выходить из сети ("что бы машина не принимала пакеты"), завершать все-все приложения, кроме самого профилировщика и вообще лучше даже "на всякий случай" перегрузиться. Все это чистейшей воды гон! Автор частенько отлаживал программы параллельно с работой в Word'e, приемом корреспонденции, скачкой нескольких файлов из Интернет и – точностью профилировки всегда оставалась удовлетворительной! Конечно, без особой нужды не стоит так рисковать, и параллельно работающие приложения перед началом профилировки, действительно, лучше завершить, но не следует доводить ситуацию до абсурда, и пытаться обеспечить полную "стерильность" своей машине.


^
Аппаратное непостоянство

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

Почему оно – аппаратное непостоянство – вообще возникает? Ну, тут много разных причин. Вот, например, одна из них: если частота системной шины не совпадает с частотой модулей оперативной памяти, чипсету придется каждый раз выжидать случайный промежуток времени до прихода следующего фронта тактового импульса. Исходя из того, что один цикл пакетного обмена в зависимости от типа установленных микросхем памяти занимает от 5 до 9 тактов, а синхронизовать приходится и его начало, и его конец, нетрудно подсчитать, что в худшем случае мы получаем неоднозначность в 25% –40%.

Самое интересное, что аппаратный разброс в чрезвычайно высокой степени разниться от системы к системе. Я, к сожалению, так и не смог определить кто именно здесь виноват, но могу сказать, что, к примеру, на P-III 733/133/100/I815EP не смотря на разницу в частотах памяти и системной шины, аппаратный разброс весьма невелик и едва ли превышает 1% – 2%, на что можно вообще закрыть глаза.

Вот AMD Athlon 1050/100/100/VIA KT133 – совсем другое дело! У него наблюдается просто ошеломляюще аппаратное непостоянство, в частности, в операциях с основной памятью доходящее аж до двух раз! Непонятно, как на такой системе вообще можно профилировать программы!!! В, частности, последовательные замеры времени копирования 16-мегабайтного блока памяти после предварительной обработки (т.е. откидывания заведомо пограничных значений) могут выглядеть так:
Прогон № 01: 84445103 тактов

Прогон № 02: 83966665 тактов

Прогон № 03: 73795939 тактов

Прогон № 04: 80323626 тактов

Прогон № 05: 84381967 тактов

Прогон № 06: 85262076 тактов

Прогон № 07: 85151531 тактов

Прогон № 08: 91520360 тактов

Прогон № 09: 92603591 тактов

Прогон № 10: 100651353 тактов

Прогон № 11: 93811801 тактов

Прогон № 12: 84993464 тактов

Прогон № 13: 92927920 тактов
Смотрите, расхождение между минимальным и максимальным времени выполнения составляет не много, не мало – 36%! А это значит, что вы не сможете обнаруживать "горячие" точки меньшей величины. Более того, вы не сможете оценивать степень влияния тех или иных оптимизирующих алгоритмов, если только они не дают по меньшей мере двукратного прироста производительности!

Отсюда правило: I) не всякая система пригодна для профилировки и оптимизации приложений и II) если последовательные замеры дают значительный временной разброс, просто смените систему. (Под "системой" подразумевается не операционная система, а аппаратное обеспечение).


^
Обработка результатов измерений

Непосредственные результаты замеров времени исполнения программы в "сыром" виде, как было показано выше, ни на что ни годны. Очевидно, перед использованием их следует обработать. Как минимум откинуть пограничные значения, вызванные нерегулярными наведенными эффектами (ну, например, в самый ответственный для профилировки момент, операционная система принялась что-то сбрасывать на диск), а затем… Затем перед нами встает Буриданова проблема. Мы будет должны либо выбрать результат с минимальным временем исполнения – как наименее подвергнувшийся пагубному влиянию многозадачности, либо же вычислить наиболее типичное время выполнения – как время выполнения в реальных, а не идеализированных "лабораторных" условиях.

Мной опробован и успешно применяется компромиссный вариант, комбинирующий оба этих метода. Фактически я предлагаю вам отталкиваться от среде минимального времени исполнения. Сам алгоритм в общих чертах выглядит так: мы делаем N прогонов программы, а затем отбрасываем N/3 максимальных и N/3 минимальных результатов замеров. Для оставшиеся N/3 замеров мы находит среднее арифметическое, которое и берем за основной результат. Величина N варьируется в зависимости от конкретной ситуации, но обычно с лихвой хватает 9-12 прогонов – большее количество уже не увеличивает точности результатов.

Одна из возможных реализаций данного алгоритма приведена ниже:
unsigned int cycle_mid(unsigned int *buff, int nbuff)

{

int a,xa=0;

if (!nbuff) nbuff=A_NITER;

buff=buff+1; nbuff--; // Исключаем первый элемент
if (getargv("$NoSort",0)==-1)

qsort(buff,nbuff,sizeof(int), \

(int (*)(const void *,const void*))(_compare));
for (a=nbuff/3;a<(2*nbuff/3);a++)

xa+=buff[a];
xa/=(nbuff/3);
return xa;

}

Листинг 8 Нахождение средне типичного времени выполнения


^

Проблема второго прохода


Для достижения приемлемой точности измерений профилируемое приложение следует прогнать по крайней мере 9 – 12 раз (см. "Непостоянства времени выполнения. Обработка результатов измерений"), причем каждый прогон должен осуществляться в идентичных условиях окружения. Увы! Без написания полноценного эмулятора всей системы это требование практически невыполнимо. Дисковый кэш, сверхоперативная память обоих уровней, буфера физических страниц и история переходов чрезвычайно затрудняют профилировку программ, поскольку при повторных прогонах время ее выполнения значительно сокращается.

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

Да и можем же мы наконец захотеть оптимизировать именно инициализацию приложения?! Пускай, она выполняется всего лишь один раз за сеанс, но какому пользователю приятно, если запуск вашей программы растягивается на минуты и то и десятки минут? Конечно, можно просто перезагрузить систему, но… сколько же тогда профилировка займет времени!

Хорошо. Очистить кэш данных – это вообще раз плюнуть. Достаточно считать очень большой блок памяти, намного превышающий его (кэша) емкость. Не лишнем будет и записать большой блок для выгрузки всех буферов записи (см. "Часть II. Кэш"). Это же, кстати, очистит и TLB (Translate Look aside Buffer) – буфер, хранящий атрибуты страниц памяти для быстрого обращения к ним (см. "предвыборка?"). Аналогичным образом очищается и кэш/TLB кода. Достаточно сгенерировать очень большую функцию, имеющую размер порядка 1 – 4 Мб, и при этом ничего не делающую (для определенности забьем ее NOP'ами – машинными командами "нет операции"). Всем этим мы уменьшим пагубное влияние всех, перечисленных выше эффектов, хотя и не устраним его полностью. Увы! В этом мире есть вещи, не подвластные ни прямому, ни косвенному контролю (во всяком случае на прикладном уровне).

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

Давайте проведем следующий эксперимент. Возьмем следующую функцию и десять раз подряд запустим ее на выполнение, замеряя время каждого прогона.
#define a (int *)((int)p + x)

A_BEGIN(0)

#define b (int *)((int)p + BLOCK_SIZE - x - sizeof(int))

for (x = 0; x < BLOCK_SIZE/2; x+=sizeof(int))

{

#ifdef __OVER_BRANCH__

if (x & 1)

#endif

*a = *a^*b; *b = *b^*a; *a = *a^*b;

}

A_END(0)

^ Листинг 9 Пример функции, однократно обращающийся к каждой загруженной в кэш ячейке
Для блоков памяти, полностью умещающихся в кэш-памяти первого уровня, на P-III 733/133/100/I815EP мы получим следующий ряд замеров:
__OVER_BRANCH__ not define __OVER_BRANCH__ is define

68586 63788

17629 18507

17573 18488

17573 18488

17573 18488

17573 18488

17573 18488

17573 18488
Обратите внимание: время выполнения первого прогона функции (не путать с первой итерации цикла!) практически вчетверо превосходит все последующие! Причем, результаты замеров непредсказуемым образом колеблются от 62.190 до 91.873 тактов, что соответствует погрешности ~50%. Означает ли это, что если данный цикл в реальной программе исполняется всего один раз, то оптимизировать его бессмысленно? Конечно же нет! Давайте, для примера избавимся от этого чудачества с XOR и как нормальные люди обменяем два элемента массива через временную переменную. Оказывается, это сократит время первого прогона до 47.603 – 65.577 тактов, т.е. увеличит эффективность его выполнения на 20% – 40%!

Тем не менее, устойчивая повторяемость результатов начинается лишь с третьего прогона! Почему так медленно выполняется первый прогон – это понятно (загрузка данных в кэш и все такое), но вот что не дает второму показать себя во всю мощь? Оказывается – ветвления. За первый прогон алгоритм динамического предсказания ветвлений еще не накопил достаточное количество информации и потому во втором прогоне еще давал ошибки, но начиная с третьего наконец-то "въехал" в ситуацию и понял, что от него ходят.

Убедиться, что виноваты именно ветвления, а ни кто ни будь другой, позволяет следующий эксперимент: давайте определим __OVER_BRANCH__ и посмотрим как это скажется на результат. Ага! Разница между вторым и третьим проходом сократилась с 0,3% до 0,1%. Естественно, будь наш алгоритм малость поразлапистее (в смысле – "содержи побольше ветвлений"), и всех трех прогонов могло бы не хватить для накопления надежного статистического результата. С другой стороны, погрешность, вносимая переходами, крайне невелика и потому ей можно пренебречь. Кстати, обратите внимание, что постоянство времени выполнения функции на всех последних проходах соблюдается с точностью до одного такта!

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

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


^

Проблема наведенные эффектов


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

Вот простой и очень типичный пример. Пусть в оптимизированной программе встретилась функция следующего вида:
ugly_func(int foo)

{

int a;







if (foo<1) return ERR_FOO_MUST_BE_POSITIVELY;

for(a=1; a <= foo; a++)

{







}

}

^ Листинг 10 Фрагмент кода, демонстрирующий ситуацию, в которой удаление лишнего кода может обернуться существенным и труднообъясним падением производительности
Очевидно, если попытаться передать функции ноль или отрицательное число, то цикл for_a не выполнится ни разу, а потому принудительная проверка значения аргумента (в тексте она выделена жирным шрифтом) бессмысленна! Конечно, при больших значениях foo накладные расходы на такую проверку относительно невелики, но в праве ли мы надеяться, что удаление этой строки по крайней мере не снизит скорость выполнения функции?

Постойте, это отнюдь не бредовый вопрос, относящийся к области теоретической абстракции! Очень может статься так, что удаление выделенной строки будет носить эффект прямо противоположный ожидаемому, и вместо того чтобы оптимизировать функцию, мы даже снизим скорость ее выполнения, причем, весьма значительно!

Как же такое может быть? Да очень просто! Если компилятор не выравнивает циклы в памяти (как например, MS VC), то с довольно высокой степенью вероятности мы рискуем нарваться на кэш-конфликт (см. "Часть II. Кэш"), облагаемый штрафным пенальти. А можем и не нарваться! Это уж как фишка ляжет. Быть может, эта абсолютно бессмысленная (и, заметьте, однократно выполняемая) проверка аргументов как раз и спасала цикл от штрафных задержек, возникающих в каждой итерации.

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

"Идиотизм какой-то", – скажите вы и будете абсолютно правы. К счастью, тот же MS VC выравнивает адреса функций по адресам, кратным 0x20 (что соответствует размеру одной кэш-линейки на процессорах P6 и K6). Это исключает взаимное влияние функций друг на друга и ограничивает область тасования команд рамками всего "лишь" одной функции.

Тоже самое относится и к размеру обрабатываемых блоков данных, числу и типу переменных и т.д. Часто бывает так, что уменьшение количества потребляемой программой памяти приводит к конфликтам того или иного рода, в результате чего производительность естественно падает. Причем, при работе с глобальными и/или динамическими переменными мы уже не ограничивается рамками одной отдельно взятой функции, а косвенно воздействуем на всю программу целиком! (см. "Часть I. Конфликт DRAM банков").

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

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


1   2   3   4   5   6   7   8   9

Похожие:

Tempora mutantur, et nos mutamur in illis iconНовикова Михаила Петровича Gaudeamus tffttur Juvenes dum sunuts!...
Учебное пособие предназначено для студентов вузов и учащихся колледжей, гимназий, школ

Tempora mutantur, et nos mutamur in illis iconРеферат скачан с сайта allreferat wow ua
Возжелавшие ауспиций: «другие семьи» 7 Перспективы 8Раздел II. 10 “O tempora! O mores!” 10 Биология открытого брака 12 Моногамия...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<