К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 12
Текст из файла (страница 12)
Означает ли это, что, если данный цикл в реальной программе исполняется всего один раз, то оптимизировать его бессмысленно? Конечно же, нет! Давайте, для примера избавимся от этого чудачества с командой хов и как нормальные люди обменяем два элемента массива через временную переменную. Оказывается, это сократит время первого прогона до 47 603— 65 577 тактов, т. е. увеличит эффективность его выполнения на 20 — 40%! Тем не менее, устойчивая повторяемость результатов начинается лишь с третьего прогона! Почему так медленно выполняется первый прогон — это понятно (загрузка данных в кэш и прочее), но вот что не лает второму показать себя во всю мощь? Оказывается — ветвления. За первый прогон алгоритм динамическопз предсказания ветвлений еше не накопил достаточное количество информации и потому во втором прогоне еше давал ошибки, но, начиная с третьего, наконец-то "въехал" в ситуацию и понял, что от него хотят.
Убедиться, что виноваты именно ветвления, а не кто-нибудь другой, позволяет следую1ций эксперимент; давайте определим очвв ввьвсн и посмотрим как это скажется на результат. Ага! Разница между вторым и третьим проходом сократилась с 0,3% до 0,1%. Естественно, будь наш алгоритм малость поветвистее (в том смысле, что содержит побольше ветвлений), и всех трех прогонов могло бы не хватить лля накопления надежного статистического результата. С другой стороны, погрешность, вносимая переходами, коайне невелика и потому ей можно пренебречь.
Кстати, обратите внимание, что постоянство времени выполнения функции на всех последних проходах соблюдается с точностью до одного такта! Профипировка программ Напротив, при профилировании функций, исполняющихся в реавьной программе всего один раз, следует обращать внимание лишь на время первого прогона и отбрасывать все остальные, причем, при последующих запусках программы необходимо каким-либо образом очистить все кзши и все буферы, искажающие реальную производительность. Проблема наведенных эффектов Исправляя одни ошибки, л1ы всегда потенциально вносим другие и потому после любых, даже совсем незначительных модификаций кода программы цикл профилировки следует повторять целиком.
Вот простой и очень типичный пример. Пусть в оптимизированной программе встретилась функция следующего вида (листинг 1.! 3). сд1у Гььс(1ьь Гьо~ ( 1ьь еи 1е Фоькх) яьььхь ввв есо нияз вв ювттхчвьз; Гое(а 1; а < тот ь+Ю Очевидно, если попытаться передать функции в качестве аргументов ноль или отрицательное число, то цикл г ь не выполнится ни разу, а потому принудительная проверка значения аргумента (в тексте она выделена жирным шрифтом) бессмысленна! Конечно, при больших значениях переменной гьь накладные расходы на такую проверку относительно невелики, но в праве ли мы надеяться, что удаление втой строки, по крайней мере, не снизит скорость выполнения функции? Постойте, это отнюдь не бредовый вопрос, относящийся к области теоретической абстракции! Очень может статься так, что удаление выделенной Глава 1 строки будет носить эффект, прямо противоположный ожидаемому, и вместо того чтобы оптимизировать функцию, мы даже снизим скорость ее выполнения, причем, весьма значительно! Как же такое может быть? Да очень просто! Если компилятор нс выравнивает циклы в памяти (как, например, МБ ЧС), то с довольно высокой степенью вероятности мы рискуем нарваться на кэш-конфликт (см.
главу 3), облагаемый штрафным пенальти. А можем и не нарваться! Это уж как фишка ляжет. Быть может, эта абсолютно бессмысленная (и, заметьте, однократно выполняемая) проверка аргументов как раз и спасала цикл от штрафных задержек, возникающих в казкдой итерации. Сказанное относится не только к удалению, но и вообще к любой модификации кода, влекущей изменение его размеров.
В ходе оптимизации произволительность программы может меняться самым причудливым образом, то повышаясь, то понижаясь без всяких видимых на то причин. Самое неприятное, что подавляющее большинство компиляторов не позволяет управлять выравниванием кода и„если цикл лег по неудачным с точки зрения процессора адресам, все, что нам остается, так зто лобавить в программу еще олин кусок кода с таким расчетом, чтобы он вывел цикл из неблагоприятного состояния, либо же просто "перетасовать" код программы, подобрав самую удачную комбинацию.
"Идиотизм какой-то", — скажете вы и будете абсолютно правы. К счастью, тот же МЯ ЧС выравнивает адреса функций по адресам, кратным Ох20 (что соответствует размеру одной кэш-линейки на процессорах Рб и Кб). Это исключает взаимное влияние функций друг на друга и ограничивает область тасования команд рамками всего "лишь" одной функции. То же самое относится и к размеру обрабатываемых блоков данных, числу и типу переменных и т.
д, Часто бывает так, что уменыпение количества потребляемой программой памяти приволит к конфликтам того или иного рода, в результате чего производительность естественно падает. Причем, при работе с глобальными и/или динамическими переменными мы уже не ограничиваемся рамками одной отдельно взятой функции„а косвенно воздействуем на всю программу целиком! (си. разд. "Стратегия распределения данных ло 0ЛАМ-банкам" главы 2). Сформулируем три правила, которыми всегла следует руководствоваться при профилировке больших программ, особенно тех, что разрабатываются несколькими независимыми людьми.
Представляете — в один "прекрасный" лень вы обнаруживаете, что после последних внесенных вами "усовершенствований" производительность вверенного вам фрагмента неожиданно падает. Но, чтобы вы ни делали, пусть даже выполнили "откат" к прежней версии, вернуть производительность на место вам никак не удавалось. А на завтра она вдруг — без всяких видимых причин! — сама восста- Профипироака программ навливалась до прежнего уровня. Да, правильно, причина в том, что ваш коллега чуть-чуть изменил свой модуль, а это рикошетом ударило по вам! Итак, обешанные правила: 0 никогда-никогда не оптимизируйте программу "вслепую", полагаясь на "здравый смысл" и интуицию; 0 каждое внесенное изменение проверяйте на "вшивость" профилировшиком, и если производительность неожиданно упадает, вместо того чтобы увеличиться, незамедлительно устраивайте серьезные "разборки": "кто виноват" и "чья тут собака порылась", анализируя весь, а не только свой собственный код; 0 после завершения оптимизации локального фрагмента программы выполните контрольную профилировку всей программы целиком на предмет обнаружения новых "горячих" точек, появившихся в самых неожиданных местах.
Проблемы оптимизации программ на отдельно взятой машине Большинство программистов, особенно из тех, что "пасутся на вольных хлебах", имеют в своем распоряжении одну, ну максимум две машины, на которых и осуществляются все стадии создания программы: от проектирования до отладки и оптимизации. Между тем, как уже успел убедиться читатель, "что русскому хорошо, то немцу — смерть". Код, оптимальный для одной платформы, может оказаться совсем не оптимальным для другой.
Планирование потоков данных 1си. одноименный раздел главы 2) — яркое тому подтверждение. Ну, вспомните: особенности реализации предвыборки данных в чипсете х'!А КТ133 приводят к резкому падению производительности при параллельной обработке нескольких близко расположенных потоков. Об этом малоприятном факте умалчивает документация, он не может быть вычислен логически, — обнаружить его можно лишь экспериментально. Совершенно недопустимо профилировать программу на одной-единственной машине, — это не позволит выявить все *'узкие" места алгоритма.
Следует, как минимум, охватить три-четыре типовые конфигурации, обращая внимание не только на модели процессоров, но и чипсетов. Этим вы более или менее застрахуете себя от "сюрпризов", подобных странностям чипсета Ч1А КТ 133, описанным в данной книге.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
