Критерии оптимизации программы это

Издано: 2003, BHV
Твердый переплет, 560 стр..

Введение в оптимизацию

Pro et contra целесообразности оптимизации

Это в наше-то время говорить об оптимизации программ? Бросьте! Не лучше ли сосредоточиться на изучении классов MFC или технологии .NET? Современные компьютеры так мощны, что даже Windows XP оказывается бессильна затормозить их!

Нынешние программисты к оптимизации относятся более чем скептически. Позволю себе привести несколько типичных высказываний:

С приведенными выше тезисами, действительно, невозможно не согласиться. Тем не менее, не стоит бросаться и в другую крайность. Начертавший на своем знамени лозунг «на эффективность — плевать» добьется только того, что плевать (причем дружно) станут не в эффективность, а в него самого. Не стоит переоценивать аппаратные мощности!

И сегодня существуют задачи, которым не хватает производительности даже самых современных процессоров. Взять хотя бы моделирование различных физических процессов реального мира, обработку видео-, аудио- и графических изображений, распознавание текста… Да что угодно, вплоть до элементарного сжатия данных архиватором a la Super Win Zip!

№108: Производительность кода — это важнейший критерий качества?

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

Цель — определяет средства . Вот из этого, на протяжении всей книги, мы и будем исходить. Ко всем оптимизирующим алгоритмам будут предъявляется следующие жесткие требования:

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

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

Критерии оптимизации

И в заключении позвольте привести еще одну цитату:

«Я программирую, чтобы решать проблемы, и обнаружил, что определенные мысли блокируют все остальные мысли и творческие цели, которые у меня есть.

Это мысли об эффективности в то время, когда я пытаюсь решить проблему. Мне кажется, что гораздо логичнее концентрироваться полностью на проблеме, решить ее, а затем творчески запрограммировать, затем, если решение медленное (что затрудняет работу с ним), то. «

О чем и для кого предназначена эта книга

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

Она ориентирована на прикладных программистов, владеющих (хотя бы в минимальном объеме) языком Си, а так же на системных программистов, знающих ассемблер. Описываемые техники не привязаны ни к какому конкретному языку, и знание Си требуется лишь для чтения исходных текстов примеров, приведенных в книге.

В не меньшей степени «Техника оптимизации» будет интересна и лицам, занимающимся сборкой и настройкой компьютеров, поскольку подробно описывает устройство «железа» и разбирает «узкие места» распространенных моделей комплектующих.

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

Материал книги в основном ориентирован на микропроцессоры AMD Athlon и Intel Pentium-II, Pentium-III и Pentium-4, но местами описываются и более ранние процессоры.

Семь китов оптимизации или
Жизненный цикл оптимизации

Часто программист (даже высококвалифицированный!), обнаружив профилировщиком «узкие» места в программе, автоматически принимает решение о переносе соответствующих функций на ассемблер. А напрасно! Как мы еще убедимся (см.

Часть III. » Смертельная схватка: ассемблер VS-компилятор «), разница в производительности между ручной и машинной оптимизацией в подавляющем большинстве случаев крайне мала. Очень может статься так, что улучшать уже будет нечего, — за исключением мелких, «косметических» огрехов, результат работы компилятора идеален и никакие старания не увеличат производительность, более чем на 3%—5%. Печально, если это обстоятельство выясняется лишь после переноса одной или нескольких таких функций на ассемблер. Потрачено время, затрачены силы… и все это впустую. Обидно, да?

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

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

Назовем ряд правил оптимизации.

Правило I

Прежде, чем оптимизировать код, обязательно следует иметь надежно работающий не оптимизированный вариант или «. put all your eggs in one basket, after making sure that you’ve built a really *good* basket» («…прежде, чем класть все яйца в одну корзину — убедись, что ты построил действительно хорошую корзину «). Таким образом прежде, чем приступать к оптимизации программы, убедись, что программа вообще-то работает.

Создание оптимизированного кода «на ходу», по мере написания программы, невозможно! Такова уж специфика планирования команд — внесение даже малейших изменений в алгоритм практически всегда оборачивается кардинальными переделками кода. Потому, приступайте к оптимизации только после тренировки на «кошках», — языке высокого уровня.

Это поможет пояснить все неясности и «темные» места алгоритма. К тому же, при появлении ошибок в программе подозрение всегда падает именно на оптимизированные участки кода (оптимизированный код за редкими исключениями крайне ненагляден и чрезвычайно трудно читаем, потому его отладка — дело непростое), — вот тут-то и спасает «отлаженная кошка». Если после замены оптимизированного кода на не оптимизированный ошибки исчезнут, значит, и в самом деле виноват оптимизированный код. Ну, а если нет, то ищите их где-нибудь в другом месте.

Правило II

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

Правило III

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

Правило IV

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

Особенно это касается наукоемких приложений, жадных до математических расчетов и графических пакетов, нуждающихся в больших объемах памяти. Наивно думать, что перенос программы на ассемблер увеличит пропускную способность памяти или, скажем, заставит процессор вычислять синус угла быстрее. Получив ассемблерный листинг откомпилированной программы (для Microsoft Visual C++, например, это осуществляется посредством ключа /FA), бегло просмотрите его глазами на предмет поиска явных ляпов и откровенно глупых конструкций наподобие: MOV EAX, [EBX]MOV [EBX], EAX. Обычно гораздо проще не писать ассемблерную реализацию с чистого листа, а вычищать уже сгенерированный компилятором код. Это требует гораздо меньше времени, а результат дает ничуть не худший.

Правило V

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

Наибольшая производительность достигается при выравнивании переходов по адресам, кратным шестнадцати, и будет уж совсем хорошо, если все тело цикла целиком поместится в одну кэш-линейку (т. е. 32 байта). Впрочем, мы отвлеклись. Техника оптимизации машинного кода — тема совершенно другого разговора. Обратитесь к документации, распространяемой производителями процессоров — Intel и AMD.

Правило VI

Если существующие команды процессора позволяют реализовать ваш алгоритм проще и эффективнее, — вот тогда действительно, «тяпнув» для храбрости пивка, забросьте компилятор на полку и приступайте к ассемблерной реализации с чистого листа. Однако с такой ситуацией приходится встречаться крайне редко, и к тому же не стоит забывать, что вы — не на одиноком острове. Вокруг вас — огромное количество высокопроизводительных, тщательно отлаженных и великолепно оптимизированных библиотек. Так зачем же изобретать велосипед, если можно купить готовый?

Правило VII

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

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

Единственная предметная область, не только оправдывающая, но, прямо скажем, провоцирующая ассемблерные извращения, это — защита программ, но это уже тема совсем другого разговора…

Распространенные заблуждения

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

Заблуждение I

За меня все оптимизирует мой компилятор!

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

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

Заблуждение II

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

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

Подробнее о сравнении качества машинной и ручной оптимизации см. Часть III. » Смертельная схватка: ассемблер VS-компилятор «.

Заблуждение III

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

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

Замечание рецензента

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

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

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

Тем не менее, современные процессоры с одной стороны достаточно умны и самостоятельно оптимизируют переданный им на выполнение код. С другой стороны оптимального кода для всех процессоров, все равно не существует и архитектурные особенности процессоров P-II, P-4, AMD K6 и Athlon отличаются друг от друга столь разительно, что все позывы к ручной оптимизации гибнут прямо на корю.

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

Заблуждение IV

Процессоры семейства x86 — полный «отстой», вот на PowerPC, например, действительно есть место, где развернуться!

Как гласит народная мудрость «Хорошо там, — где нас нет». Сам я, правда, ничего не оптимизирую под PowerPC, но хорошо знаком с людьми, разрабатывающими под него оптимизирующие компиляторы. И могу сказать, что они далеко не в восторге от его «закидонов», коих у него, поверьте уж, предостаточно.

Да, семейству процессоров x86 присущи многие проблемы и ограничения. Но это ничуть не оправдывает программистов, пишущих «уродливый» код, и палец о палец не ударяющих, чтобы хоть как-то его улучшить.

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

Источник: citforum.ru

21. Оптимизация: цель, критерии, требования, методика, средства.

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

Основными критериями при оптимизации программ являются:

• Скорость работы
• Объем используемой памяти
• Объем места, занимаемого на диске

Если программа работает медленно:

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

Если программа требует много памяти (ОЗУ):

• с ней откажутся работать потенциальные пользователи (пример: Задача о поиске оптимального маршрута между городами – при хранении разреженной матрицы в полном варианте огромный объем требуемой памяти приведет к активному использованию файла подкачки Windows – крайне медленная работа)

Если программа требует много места на жестком диске:

• ее могут отказаться приобретать потенциальные пользователи

(пример: вспомним наше недовольство при установке программ с 5 компакт-дисков, а также разговоры о том, что каждый новый Windows занимает в 3 раза больше места, чем старый).

Обычно 1 из критериев является основным. В современных условиях это, как правило, скорость работы (память стоит дешево).

• Переносимость
• Небольшая трудоемкость
• Значимый выигрыш
• Понятность программы
• Возможность развития

Прежде чем оптимизировать программу, убеждаемся в ее работоспособности. Основной прирост производительности приходит от алгоритмической оптимизации, а не от «трюков» (ищем эффективные алгоритмы). Оптимизация кода ≠ Ассемблерная реализация (улучшаем код для увеличения быстродействия в рамках ЯПВУ). Перед переписыванием на Ассемблер изучаем ассемблерный листинг после работы компилятора (знаем ли мы, как сделать лучше?). Если все вышеперечисленное не помогло и мы знаем как улучшить ассемблерный код, только тогда переходим на Ассемблер.

• Оптимизирующий компилятор.
• Средства профилировки.
• Оптимизирующие библиотеки.

Главное средство: голова программиста, снабженная знаниями основ программирования, теории алгоритмов, архитектуры ЭВМ.

22. Алгоритмическая оптимизация: временная сложность, сравнение алгоритмов, примеры.

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

• Анализируем задачу.
• Ищем (литература, Интернет, изобретаем сами) алгоритмы ее решения.
• Сравниваем эти алгоритмы по тем критериями, которые для нас имеют смысл.
• Выбираем лучший алгоритм.
• Думаем, нельзя ли улучшить и его.

Сравнение алгоритмов – теория сложности. Теория сложности игнорирует константы. Для получения реальной картины и выбора путей дальнейшей (не алгоритмической) оптимизации необходимо оценить полученную реализацию.

Задача: Дано прямоугольное поле размера m x n. В каждой ячейке лежит определенное кол-во денег. Буратино начинает свой путь в ячейке (1, 1) и за 1 шаг способен двигаться на 1 клетку вправо, либо на 1 клетку вниз. Требуется найти наибольшее кол-во денег, которое может собрать Буратино на пути из (1, 1) в (m, n) и соответствующий путь.

Алгоритм 1. Полный перебор всех путей.

• сгенерировать все пути;
• для каждого найти сумму денег;
• из сумм найти максимум.

1-я разумная модификация: сгенерировав путь, сразу считать сумму и сравнивать с максимумом.

Источник: studfile.net

Оптимизация программ

Оптимиза́ция програ́мм, преобразование программ для ЭВМ , направленное на улучшение их рабочих характеристик, чаще всего времени выполнения, реже – объёма, энергии, потребной для выполнения.

Од­но из тре­бо­ва­ний, предъ­яв­ляе­мых к оптимизации программ, – её кор­рект­ность: пре­об­ра­зо­ван­ная про­грам­ма долж­на быть эк­ви­ва­лент­на ис­ход­ной по сво­им ре­зуль­та­там. Дру­гое тре­бо­ва­ние со­сто­ит в том, что­бы оптимизация программы име­ла при­ем­ле­мую ал­го­рит­мическую слож­ность при реа­ли­за­ции на ЭВМ. В статических компиляторах при оптимизации отдельных процедур или всей программы обычно выбирают алгоритмы линейной сложности относительно размера программы, а для алгоритмов большей сложности ограничивают размеры участков программы, которые подвергаются оптимизации. При динамической компиляции сложность алгоритмов оптимизации балансируют с выигрышем, получаемым от оптимизации, поэтому алгоритмы большой сложности применяют только к участкам программы, выполнение которых занимает значительную долю времени.

По сте­пе­ни за­ви­си­мо­сти оп­ти­ми­за­ции от осо­бен­но­стей ЭВМ оптимизацию программ де­лят на ма­шин­но-за­ви­си­мую и ма­шин­но-ори­ен­ти­рован­ную. По раз­ме­ру оп­ти­ми­зи­руе­мо­го уча­ст­ка про­грам­мы раз­ли­ча­ют ло­каль­ные (в пределах базового блока), гло­баль­ные (в пределах процедуры), межпроцедурные и межмодульные оп­ти­ми­за­ции (всей программы целиком). В ходе выполнения оптимизации программ часто сначала определяют потенциальные оптимизационные преобразования с учётом их корректности и выгодности с использованием методов анализа программ , а далее выполняют сами преобразования.

Часто применяющимися оптимизациями яв­ля­ют­ся сле­дую­щие: умень­ше­ние час­тот вы­пол­не­ния фраг­мен­тов про­грам­мы («чи­ст­ка» цик­лов, зон и ре­кур­сив­ных об­лас­тей); эко­но­мия из­бы­точ­ных и об­щих вы­ра­же­ний; «чи­ст­ка» про­грам­мы за счёт уда­ле­ния не­дос­туп­ных, не­ис­поль­зуе­мых или не влияю­щих на ре­зуль­тат фраг­мен­тов про­грам­мы; раскрутка, изменение пространства итераций и другие преобразования циклов для выявления параллелизма программы и улучшения локальности данных ; встраивание одних процедур программы в другие для уменьшения стоимости вызовов процедур и увеличения области глобальных оптимизаций; преобразование косвенных вызовов процедур в прямые (девиртуализация) и др.

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

Редакция информационных технологий

Источник: bigenc.ru