К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 16
Текст из файла (страница 16)
О( а < ввв1еп(рввб)п а++) х е- * (тпт *) ((1пт) рвиб а а) ) тетптп х; Профипировка программ Судя по всему, бестолковый компилятор не вынес вызов функции е»г( за тело цикла, хотя ее аргумент — переменная р с — не модифицировался в цикле! Хорошо, если гора не идет к Магомету, пойдем навстречу компилятору и перепишем этот участок кода так (листинг 1.17).
зпе 1еед»Ю 1еечеь=ее»1ее(раас(Ы го» (а = 0; а < 1ееяеь( а+и Перекомпилировав программу, мы с удовлетворением отметим, что теперь ее быстродействие возросло до трех с половиной миллионов паролей в секунду, т. е. практически в два с половиной раза больше, чем было в предыдушем случае.
Шаг третий. Выравнивание данных Тем не менее, профилировка показывает, что количество "горячих" точек не только сократилось, но даже и возросло на одну! Почему? Так дело в том, что алгоритм подсчета "горячих" точек учитывает не абсолютное, а относительное быстродействие различных частей программы по отношению друг к другу. И по мере удаления самых больших пиков на диаграмме появится более мелкая "рябь".
Несмотря на оптимизацию, функция саз захе сас по прежнему идет "впереди планеты всей", отхватывая более 50% всего времени исполнения про(раммы. Но теперь самой "горячей" точкой становится пара команд: ее», сюсвс Рта (еах+еам ас(е еах, ею Хм! Что же в них такого особенного? Ну да, тут налицо обращение к памяти (» е= *( ее .(((ьеюр а + а(), но ведь тестируемый пароль по идее должен нахолиться в кэше первого уровня, доступ к которому занимает один такт. Может быть, кто-то вытеснил эти данные из каша? Или произошел какой- нибудь конфликт? Попробуй тут разберись! Можно бесконечно ломать голову, поскольку причина вовсе не в этом коде, а совсем в другой ветке программы.
Вот тут самое время прибегнуть к одному из мощнейших средств профилировщика УТцпе, т. е. к дннвлтнчеенвму анализу, позволяющему не только определить, куда "уходят" такты, но и выяснить причины этого. Причем, дина- Глава 1 66 мический анализ выполняется отнюдь не на "живом" процессоре, а на его программном эмуляторе. Это здорово экономит ваши финансы! Для оптимизации вовсе не обязательно приобретать всю линейку процессоров — от 1пге! 486 до Репбшп-4, — вполне достаточно приобрести один профилировшик т1Тцпе, и можете запросто оптимизировать свои программы под Реп!)цт-4, имея в наличии всего лишь Репйшп-П или Реп!(цш-П!.
Перед началом динамического анализа вам требуется указать, какую именно часть программы вы хотите профилировать. В частности, можно анализировать как одну "горячую" точку функции сзгсстзгв слс, так и всю функцию целиком. Поскольку наша подопечная функция содержит множество "горячих" точек, выберем последний вариант. Рис. 1.9. Динамический анализ программы не только определяет "температуру" каждой машинной инструкции, но и объясняет причины ее "нагрева" Прокручивая экран вверх, переместим курсор в строку с меткой сзг гзте сяс (метки отображаются во второй слева колонке экрана).
Если же такой строки не окажется, найдем на панели инструментов кнопку с голубым треугольником, направленным вверх (Бсго!! !о Ргеу(овв Рог!а!), и нажмем ее. Теперь установим точку входа (Пупапт(с Апа!увез Епггу Ропг), которая задается кнопкой с желтой стрелкой, направленной вправо. Аналогичным образом задается и точка выхода (()упапт(с Апа!увез Ехй Ропг)— 6/' Профилировка проП)амм ПРОКРУЧИВаЯ ЭКРаН ВНИЗ, ДОбИРаЕМСЯ ДО ПОСЛЕДНЕЙ СТРОКИ Са1сц1абе СВС (Оиа СОСтОИт ВСЕГО ИЗ ОдНОй КОМаНдЫ вЂ” гег) И, ПОМЕтИВ ЕЕ КурСОрОМ, Нажнмаем кнопку с желтой стрелкой, направленной налево.
Теперь— "Кап),Рупаш!с Апа!уз!8 Безз!оп". В появившимся диалоговом окне выбираем змулируемую модель процессора (в нашем случае — Р-П1) и нажимаем кнопку Явг$. Поехали! Профилировщик вновь запустит программу и, погоняя ее минуту-другую, выдаст приблизительно следующее окно (рис. 1.9). Ага! Вот она, наша "горячая" точка (на рисунке она отмечена курсором). Двойной щелчок мыши вызывает информационный диалог, подробно описывающий проблему (листинг !.18). Оесобег Мгп1шцш С1оскв = О, // Мингвьальное время декодирования 0 тактов Оесобег Ьуегаде 01осхз 0.7 ; // Среднее время декодирования 0.7 тактов // Максимальное время декодирования 14 тактов Оесобег Мах1шцш 01оскз = 14 Кег1гешепС Мгп1виш 01осхв - О, ; // Минимальное время завершения 0 тактов кегбгешепС Атегаде 01осхз = 8.9 ) // Среднее время завершения 6.9 тактов аесггешепС Мах1шцш 01осхз = 104 : // Максимальное время завершения 104 такта Тога1 Сус1ез 20117 )35,88%) ; // Полное время исполнения 20.117 тактов )35,88$) Нгсго-Срз Тог Сьгз 1пвСгцсСгоп 1; О Инструкция деке)глруется в одну ьмкрооперациш // инструкция ждала )О, 0.1, 2) цикла пока ее операнды не были готовы ТЬе гпзггцсггоп Ьаб Со иа1С )О, 0.1, 2) сус1ез Тог СС'з зоцгсез Со Ье геабу Вагпгпдз: 3*беседе з1оы:0 // КонФликтов декодеров — нет ТЬе орегапб об Сьгв 1оаб гпзггцсг1оп ыаз пог бп Спе баСа сасье.
Тье гпвггцсг1оп вСа11з ыь11е Сье ргосеввог 1оабв СЬе врес1ггеб аббгезз 1осаСТоп Тгош Сье 12 сасне ог паап шешогу. )Операнд этой инструкции отсутствовал в кате данных. инструкция овидала пока гдоо- цессор загрузит соответствуя)яие данные иэ кэша второго уровня или основной памяти.) // Случалось один рвв Глава 1 ев Вупаябс Регса3.яу с ВС з1ва110п Тпе гпвсгцсс1оп вса11я Ьесааяе гс ассезвеб баса спас чав вр11Г аагояз Гчо с1асасаапе 11пез. )ИиотруКцня Прсотаизапа, ПОтОМу Чта Оиа Обращапаоя К ДаННЫМ, нраощЕПЛЕННЬМ" Чсрсв две кзы-линии.) Оаапггепсев = 2000 // сия гооо р з Вупазя.с Репазсу с 12блаа гс1 згвв тье орегапа ог гпгя 1оаб гпяггпсггоп ная пог гп гпе ь2 сасье. тье 1пяггпсггоп яаа11я иьг1е ГЬе ргосевзог 1оабя гье зреагг1еб аббгеяя 1оаасгог, Тгощ ща1п щещогу.
)Оссеранд втой инструкции отсутствовал в кзае второ о уровня. Инструкция оямдала пока процессор загрузит соответствующие данные из основной памяти.) // Случалось один раз Осспггепсев 1 Вупавп.с РепаЗ.Гу с Ио ВТВ гпго тье ВтВ боев пег сопга1п 1птопыггоп аьоог гпгя ьгапсь. тье ьгапсь нав ргесцсгеб пягпо Гзе яааагс Ьгапаь ргебгссбоп а10ог1Г)чя. )ВТ — Вляпал Тагоеа Вцгуег — бурер ветвлений не содериал иноормацссп об зтом ветв- лении.
Ветка была предсказана статическим алгоритмом предсказаний.) // Случалось один раз Какой богатый кладезь информации! Оказывается, кэш тут действительно не причем (кэш-промах произошел всего один раз), а основной виновник— доступ к невыровненным данным, который имел место аж 2000 раз,— именно столько, сколько и прогонялась программа. Таким образом, такое происшествие случалось на каждой итерации цикла — отсюда и "тормоза". Смотрим — где в программе инициализируется указатель р оу Ага, вот фрагмент кода из тела функции гп (надеюсь, теперь вам понятно, почему статический анализ функции са1сп1аге сас был неспособен что-либо датьв) (листинг 1.19). ~!:.".!!;,,: Ч,яаана 'Юч' сяз))~" ., ' ь р~ ',,;"-~ ч' ряно' = )сьаг *) ща11ос Г512*1024)) Убираем строку рв б +=52 и перекомпилируем программу. Теперь быстродействие соствило четыре с ноловнной миллиона наролей в секунду! Держи тигра за хвост! Профилировка программ 69 Шаг четвертый.
Избавление от функции а~грел Возвращаясь к рис. 1.9, отметим, что обращение к невыровненным дан- НЫМ вЂ” НЕ ЕЛИНСТВЕННая ГоряЧая ТОЧКВ фуНКНИИ Са1оо1аяе СВС. С НсбОЛЬ- шим отрывом за ней следует инструкция рдвн, временно сохраняющая реги- СтРЫ В СТЕКЕ, И ОПЯТЬ та ПРОтнаиаа ФУНКЦИЯ яег1еп, С КОтОРОй МЫ УжЕ сталкивались. Действительно„вычисление длины пароля вполне сопоставимо по времени с подсчетом его контрольной суммы. Вот если бы этого удалось избежать.
А для чего, собственно, вообще вычислять длину каждого пароля? Ведь пароли перебираются не хаотично, а генерируются по вполне упорядоченной схеме и приращение длины пароля на единицу происходит не так уж и часто. Так может быть лучще Возложить эту задачу на функцию деп рано? Пусть при первом же вызове она определяет длину начального пароля, а затем при "растяжке" строки увеличивает глобальную переменную 1 дял на единицу.
Сказано — сделано. Теперь код функции д . р а выглядит так, как показано в листинге 1.20. зпо а; 1пер=0; 1епдвь ввя1еп(рвяяв; У/ определение длины начального пароля 11 (!ряио(р)) ( рано(р)=' рене((рь1)=С; 1~ьдаь++; "ручное" увеличение длины пароля А код функции са1 апе свс так, как показано в листинге 1.21. Тог (а = Оь а <= 1епдвь; аьч) Глава [ В результате этих нехитрых преобразований мы получаем скорость в восемь миллионов паролей в секунду. Много? Подождите! Самое интересное еше только начинается... Шаг пятый.
Удаление операции деления тсцсрЬ На ПсрВОЕ МЕСТО ВЫрЫВВЕТСЯ фуНКЦИЯ дее рееб, В КОТорой ПроЦЕССор проводит более половины всего времени исполнения программы. За дее ре б С бОЛЬШИМ ОтрЫВОМ СЛЕдуЮт фуНКцИИ Са1бе1а«е СКС вЂ” 21% И сьее«сас — 15%. Причем, 40% от обшего времени исполнения функции деп рееб сосРедоточено в одной-единственной "гоРЯчей" точке. Не[юРЯдок! Надо бы оптимизировать! Двойной шелчок по высоченному прямоугольнику приводит нас к инструкции Тшч, выполняюшей целочисленное деление.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
