К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 11
Текст из файла (страница 11)
Процессор никогда не ошибается и каждый полученный результат точен. Другое дело, что он в той или иной степени искажен побочными эффектами, но! Никакие побочные эффекты никогда не приводят к тому, что программа начинает исполняться быстрее, нежели она исполняется в действительности, а потому, прогон е минимальным временем исполнения а представляет собой измерение, в минимальной степени испорченное побочными э44мнтами. Кстати, во многих руководствах утверждается, что перед профилировкой целесообразно выходить из сети ("что бы машина не принимала пакеты"), завершать все-все приложения, кроме самого профилировщика и вообще лучше даже "на всякий случай" перегрузиться. Все это бред чистейшей воды! Автор частенько отлаживал программы параллельно с работой в хогг), приемом корреспонденции, загрузкой нескольких файлов из Интернета, и лри этом точность профилировки всегда оставалась удовлетворительной! Конечно, без особой нужды не стоит так рисковать, и параллельно работающие приложения перед началом профилировки.
действительно, лучше завершить, но не следует доводить ситуацию до абсурда и пытаться обеспечить полную "стерильность" своей машине. Глава 1 Аппаратное непостоянство Возможно, это покажется удивительным, но на аппаратном уровне время выполнения одних и тех же операций не всегда постоянно и подвержено определенным разбросам, под час очень большим и значительно превосходящим программную погрешность. Но если последнюю, хотя бы теоретически, возможно ликвидировать (ну, например, запустить программу в олнозадачном режиме), то аппаратное непостоянство неустранимо принципиально. Почему оно — аппаратное непостоянство — вообще возникает? Ну, тут много разных причин.
Вот, например, одна из них: если частота системной шины не совпадает с частотой модулей оперативной памяти, чипсету придется каждый раз выжидать случайный промежуток времени до прихода следующего фронта тактового импульса. Исходя из того, что один цикл пакетного обмена в зависимости от типа установленных микросхем памяти занимает от 5 до 9 тактов, а синхронизировать приходится и его начало, и его конец, нетрудно подсчитать, что в худшем случае мы получаем неоднозначность в 25 — 40% 84445103 тактов 83966665 тактов 73795939 тактов 80323626 тактов 84381967 тактов 85262076 тактов Прогон И' 01: Прогон В 02: Прогон И' 03: Прогон т 04: прогон в 05: Прогон И' Об: Прогон В 07: Прогон и' 08; Прогон В 09; Прогон 9 10: Прогон В 11.
Прогон т 12: прогон т 13; 85151531 91520360 тактов тактов 92603591 тактов 100651353 тактов 93811801 тактов 84993464 тактов 92927920 тактов Самое интересное, что аппаратный разброс в чрезвычайно высокой степени разнится от системы к системе. Я, к сожалению, так и не смог определить, кто именно здесь виноват, но могу сказать, что, к примеру, на Р-Ш 733/133/100/1815ЕР, несмотря на разницу в частотах памяти и системной шины, аппаратный разброс весьма невелик и едва ли превышает ! — 2% на что можно вообще закрыть глаза.
Вот АМ(3 А!17!оп 1050/100/100/У(А КТ133 — совсем другое дело! У него наблюдается просто ошеломляющее аппаратное непостоянство, в частности, в операциях с основной памятью доходящее аж до двух раз! Непонятно, как на такой системе вообще можно профилировать программы? В частности, последовательные замеры времени копирования 1б-мегабайтного блока памяти после предварительной обработки (т. е. после отбрасывания заведомо пограничных значений) могут выглядеть так: Профилировка программ 41 Смотрите, расхождение между минимальным и максимальным временем выполнения составляет ни много ни мало — 36%' А это значит, что вы не сможете обнаруживать "горячие" точки меньшей величины.
Более того, вы не сможете оценивать степень влияния тех или иных оптимизирующих алгоритмов, если только они не дают, по меньшей мере, двукратного прироста производительности! Отсюда правила: 1. Не всякая система пригодна для профилировки и оптимизации приложений. 2. Если последовательньге замеры дают значительный временной разброс, просто смените састему. Под "системой" в данном случае подразумевается не операционная система, а аппаратное обеспечение.
Обработка результатов измерений Непосредственные результаты замеров времени исполнения программы в "сыром" виде, как было показано выше, ни на что ни годны. Очевидно, перед использованием их следует обработать. Как минимум откинуть пограничные значения, вызванные нерегулярными наведенными эффектами (ну, например, в самый ответственный лля профилировки момент операционная система принялась что-то сбрасывать на диск), а затем перед нами встает Буриданова проблема-". Мы будем должны либо выбрать результат с минимальным временем исполнения — как наименее подвергнувшийся пагубному влиянию многозадачности, либо же вычислить наиболее типичное время выполнения — как время выполнения в реальных, а не идеализированных "лабораторных" условиях. Мной опробован и успешно применяется компромиссный вариант, комбинирующий оба этих метода. Фактически я предлагаю вам отталкиваться от среднеминимольного времени исполнения.
Сам алгоритм в общих чертах выглядит так: мы выполняем Ж прогонов программы, а затем отбрасываем Ж/3 максимальных и Ф/3 минимальных результатов замеров. Для оставшихся У/3 замеров мы находим среднее арифметическое, которое и берем за основной результат. Величина Ф варьируется в зависимости от конкретной ситуации, но обычно с лихвой хватает 9 — 12 повторов, т. к. большее количество уже не увеличивает точности результатов. ' "Буриданова проблема" — в приписываемом французскому философу ХХ1Ч века Буридану рассказе об осле, который, находясь между двумя совершенно олинаковыми охапками сена, не решается, какую из них выбрать, и тем самым обречен своим бездействием на гололную смерть.
В переносном смысле — проблема выбора.— Ред. 42 Глава ! Одна из возможных реализаций данного алгоритма приведена в листинге !.! !. (~~(!~?Ви~~~Д';.н~~~и(йвнив:,'с опв1дпеб апь сус1е впб!ппвлчпеб юпо *Ьп Г, 1пс вылет) ! лпе а,ха=О; ЫпЬпгм вылет а Взтвш Ьптт=ьптт+1; пЬпгт †; // Исключаем переса впемепт Шеоалэч!"Гяозоль", Ш ==-1! Чвовь(ьпет,пьп .,влхеоенп о пс !*) (сопвс чо б *,сопев колбы ~ ~ совралеы; гол (а=пьпгг/3;а<(2*пьпгт/Зма+ ха+=Ьптт!а!; ха/ ~пыле//ЗЫ леоплп ха; Проблема второго прохода Для достижения приемлемой точности измерений профилируемое приложение следует выполнить, по крайней мере, 9 — )2 раз (см.
предьпуший разд. "Обрабо/пка резульп/атов измерений" э/пой главы), причем каждый прогон должен осушествляться в идентичных условиях окружения. Увы! Без написания полноценного эмулятора всей системы это требование практически невыполнимо. Дисковый кэш, сверхоперативная память обоих уровней, буфера физических страниц и история переходов чрезвычайно затрудняют профилировку программ, поскольку при повторных прогонах время выполнения программы значительно сокрашается. Если мы профилируем многократно выполняемый цикл, то этим обстоятельством можно и пренебречь, поскольку время загрузка данных и/или кода в кэш практически не сказывается на обшем времени выполнения цикла.
К сожалению, так бывает далеко не всегда (такой случай как раз и был разобран в разд. "е(нформация о пеналыпи" э/пой главы). Да и можем же мы, наконец, захотеть оптимизировать именно инициализацию приложения?! Пускай она выполняется всего лишь один раз за сеанс, но какому пользователю приятно, если запуск вашей программы растягивается на минуты, а то и десятки минут? Конечно, можно просто перезагрузить систему, но сколько же тогда профилировка займет времени?! Профипировка программ 43 Хорошо. Очистить кэш данных — это вообше раз плюнуть.
Достаточно считать очень большой блок памяти, намного превышающий его (коша) емкость. Не лишним будет записать и большой блок для выгрузки всех буферов записи (см. главу 3). Это же, кстати, очистит и Т1.В (Тгапя!а(е 1.сок ая1()е Вцйег) — буфер, хранящий атрибуты страниц памяти для быстрого обращения к ним (см.
раэд. "Управление кэшированием в процессорах старшего поколения семейства х8б" главы 3). Аналогичным образом очищается и кэш/Т(.В от кода. Достаточно сгенерировать очень большую функцию, имеюшую размер порядка 1 — 4 Мбайт, и при этом "ничего не делающую" ()шя определенности забьем ее машинными командами иск — "нет операции").
Таким образом мы уменьшим пагубное влияние всех, перечисленных выше эффектов, хотя и не устраним его полностью. Увы! В этом мире есть веши„неподвластные ни прямому, ни косвенному контролю (во всяком случае, на прикладном уровне). С другой стороны, если мы оптимизируем одну отдельно взятую функцию, (для определенности остановимся на функции реверса строк), то как разтаки ее первый прогон нам ничего и не даст, поскольку в данном случае основным фактором, определяющим производительность, окажется не эффективность кода/алгоритма самой функции, а накладные расходы на загрузку машинных инструкций в кэш, выделение и проецирование страниц операционной системой, загрузку обрабатываемых функцией данных в сверхоперативную память и т.
д. В реальной же программе эти накладные расходы, как правило, уже устранены (даже если эта функция вызывается однократно). Давайте проведем следую(ций эксперимент. Возьмем следуюшую функцию и десять раз подряд запустим ее на выполнение, замеряя время каждого прогона (листинг 1.12). 4ФЙМ$й)(946(ЙФ1Г)(ЙФФ6(уа()(МЬФ~ФФ~!Я)а';1(.,!~!~~(!''')))~:,;:;'1(::,~((::."в1 „',: ()Се11пе а (1пе *) ((1пе)р + х) х вкати(о) ()Оет1пе Ь (1пе *) ((1пе)р + ВЬОСК Я1ЯŠ— х - егееег(1п")) Гоп (х = О) х < ВЬОСК Я1ЯЕ/З) х+=51хепй(1пе)) ()11аес ОЕКЕ ВКХИСН 11 (хат) ()епа11 а = *а "Ь) *Ь = *Ь"*а; *а = а *Ь) х киь(о) Глава 7 Для блоков памяти, полностью умешаюшихся в кэш-памяти первого уровня, на Р-Ш 733/133/100/1815ЕР мы получим следуюший ряд замеров: СЧВВ 86634СН еее аес1ее СЧВВ 86731СН хе Вевх 68586 бз'788 17628 17573 17573 17573 18507 18488 18488 18488 18488 16488 16486 17573 Таким образом, при профилировании многократно выполняющихся функций, результаты первых двух-трех прогонов стоит вообще откинуть, и категориче- ски не следует их арифметически усреднять.
Обратите внимание, что время выполнения первого прогона функции (не путать с первой итерацией цикла!) практически вчетверо превосходит все последуюшие! Причем, результаты замеров непредсказуемым образом колеблются от 62 190 до 91 873 тактов, что соответствует погрешности 50%.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
