Цель занятия: Ознакомление с видами оптимизации программы, оптимизация индивидуального модуля по выбранному параметру (время выполнения, объем памяти).
Задание:
Разработать тестовые модулей проекта для тестирования отдельных модулей, провести оптимизацию программы по выбранному параметру.
Теоретические сведения:
Оптимизация – преобразование программы, сохраняющее ее семантику (конструкции языка программирования), но уменьшающие ее размер и время выполнения.
Виды оптимизация программы:
· глобальная (всей программы);
· локальная (нескольких соседних операторов, образующих линейный участок);
· квазилокальная (фрагментов программы фиксированной структуры, например, циклов).
1. Разгрузка участков повторяемости: вынесение вычислений из многократно проходимых исполняемых участков программы на участки программы, редко проходимые. Таким образом, это преобразование тела цикла или рекурсивных процедур.
2. Упрощение действий: улучшение программы за счет замены групп вычислений на группу вычислений, дающих тот же результат с точки зрения всей программы, но имеющих меньшую сложность.
Что такое законная минимизация налогов. Семинар КЦПРБ
а) упрощение действий происходит при замене сложных операций в выражениях более простыми: x / 0.4 -> x*0.25;
б) преобразование по объединению или расчленению циклов, по перестановке заголовков циклов, по удалению избыточных выражений (замене их на переменную).
3. Реализация действия: действия над константами заменяются на константы; ликвидация константных распознавателей -замена условного оператора на одну из его ветвей, если его выбирающее условие-выражение имеет постоянное значение; удаление из программы ненужных пересылок вида:
4. Чистка программы (удаление ненужных конструкций): недостижимых операторов, существенных операторов, неиспользуемых переменных, видов, операций.
5. Сокращение размера программы: вынесение одинаковых конструкций в начальную или конечную точку программы; поиск в программе похожих объектов и формирование их в виде процедуры.
6. Экономия памяти -уменьшение объема памяти, отводимые под информационные объекты программы (например, параметры процедуры).
Выполнение работы:
1. Для индивидуального модуля выбрать параметр оптимизации и определить его количественные характеристики.
2. Провести оптимизацию программы по выбранному параметру.
3. Сравнить характеристики исходного модуля и модуля, полученного в результате оптимизации.
4. Оформить отчет, содержащий описание, обоснование и результаты оптимизации программы.
Требования к отчету: Текст должен быть написан шрифтом Times New Roman, 12. Интервал между строками и абзацами – 1,5. Отступ слева 1,5. Ориентация текста – по ширине страницы. Скриншоты необходимо подписать.
Название практической работы, цель работы, ход работы, вывод, ответы на контрольные вопросы, должны быть выделены жирным шрифтом, так же как в методичке.
Контрольные вопросы:
1. Почему необходимо проводить оптимизацию, а не минимизацию программы?
Современные методы оптимизации — Александр Гасников
2. От чего зависит выбор метода оптимизации?
3. Почему большое внимание уделяется циклическим участкам?
4. К каким нежелательным последствиям может привести оптимизация?
Задание №2:
1) Ознакомиться с лекционным материалом по теме «Тестирование, отладка и ПО»
2) Провести функциональное тестирование разработанного программного обеспечения
Теоретические сведения:
Процесс тестирования состоит из трёх этапов:
1. Проектирование тестов.
2. Исполнение тестов.
3. Анализ полученных результатов.
На первом этапе решается вопрос о выборе некоторого подмножества множества тестов, которое сможет найти наибольшее количество ошибок за наименьший промежуток времени. На этапе исполнения тестов проводят, запуск тестов и отлавливают ошибки в тестируемом программном продукте.
Функциональные тесты составляются на уровне спецификации, до решения задачи. Будущий алгоритм рассматривается как «черный ящик» — функция с неизвестной (или не рассматриваемой) структурой, преобразующая входы в выходы. Суть функциональных тестов: каким бы способом ни решалась задача, при заданных входных значениях должны получиться соответствующие выходные значения.
Структурные тесты составляются для проверки логики решения, или логики работы уже готового алгоритма. Логика определяется последовательностью операций, их условным выполнением или повторением (т.е. композицией базовых конструкций). Совокупность структурных тестов должна обеспечить проверку каждой из таких конструкций.
Чаще всего совокупность тщательно составленных функциональных тестов покрывает множество структурных тестов.
Приведенные понятия различаются тем, что первое рассматривает программу только с точки зрения входов и выходов, тогда как второе относится к ее структуре; но оба понятия не касаются процесса организации тестирования.
Общая последовательность разработки тестов
Наиболее рациональная процедура заключается в том, что сначала разрабатываются функциональные тесты, а затем – структурные.
Функциональное тестирование (тестирование «черного ящика»)
При функциональном тестировании выявляются следующие категории ошибок:
· некорректность или отсутствие функций;
· ошибки в структурах данных;
· ошибки машинных характеристик (нехватка памяти и др.);
· ошибки инициализации и завершения.
Техника тестирования ориентирована:
· на сокращение необходимого количества тестовых вариантов;
· на выявление классов ошибок, а не отдельных ошибок.
Способы функционального тестирования
Разбиение на классы эквивалентности
Это самый популярный способ. Его суть заключается в разделении области входных данных программы на классы эквивалентности и разработке для каждого класса одного тестового варианта.
Класс эквивалентности – набор данных с общими свойствами, в силу чего при обработке любого набора данных этого класса задействуется один и тот же набор операторов.
Классы эквивалентности определяются по спецификации программы. Тесты строятся в соответствии с классами эквивалентности, а именно: выбирается вариант исходных данных некоторого класса и определяются соответствующие выходные данные.
Самыми общими классами эквивалентности являются классы допустимых и недопусти-мых (аномальных) исходных данных. Описание класса строится как комбинация условий, описывающих каждое входное данное.
Условия допустимости или недопустимости данных задают возможные значения данных и могут описывать:
· некоторое конкретное значение; определяется один допустимый и два недопустимых класса эквивалентности: заданное значение, множество значений меньше заданного, множество значений больше заданного;
· диапазон значений; определяется один допустимый и два недопустимых класса эквивалентности: множество значений в границах диапазона; множество значений, выходящих за левую границу диапазона; множество значений, выходящих за правую границу диапазона;
· множество конкретных значений; определяется один допустимый и один недопустимый класс эквивалентности: заданное множество и множество значений, в него не входящих.
Такие классы можно описать языком логики, например, языком исчисления предикатов. Описания более сложных условий и соответствующих классов (например, элементы массива должны находиться в некотором диапазоне и при этом массив не должен содержать нулевых элементов) могут быть построены на основании приведенных выше условий.
В примере, приводимом в вопросе 2 темы 3, при построении тестов неформально использовался описанный метод. В методических целях были выделены только основные класс тестов. Кроме того, исходя из условия задачи, были выделены классы эквивалентности внутри класса правильных данных.
Анализ граничных значений
Этот способ построения тестов дополняет предыдущий. Также он предполагает анализ значений, лежащих на границе допустимых и недопустимых данных. Построение таких тестов часто диктуется интуицией.
Основные правила построения тестов:
· если условие правильности данных задает диапазон, то строятся тесты для левой и правой границы диапазона; для значений чуть левее левой и чуть правее правой границы;
· если условие правильности данных задает дискретное множество значений, то строятся тесты для минимального и максимального значений; для значений чуть меньше минимума и чуть больше максимума;
· если используются структуры данных с переменными границами (массивы), то строятся тесты для минимального и максимального значения границ.
· Взаимосвязь классов эквивалентности и соответствующих им действий описывается формально в виде графа на основе автоматного подхода. Граф преобразуется в таблицу решений, столбцы которой в свою очередь преобразуются в тестовые варианты.
Выполнение работы:
1) Разработать тестовые наборы для функционального тестирования.
2) Провести тестирование программы и представить результаты в виде таблицы.
3) Выработать рекомендации для корректировки тестируемой программы.
4) Представить отчет по лабораторной работе для защиты.
Требования к отчету: Текст должен быть написан шрифтом Times New Roman, 12. Интервал между строками и абзацами – 1,5. Отступ слева 1,5. Ориентация текста – по ширине страницы. Скриншоты необходимо подписать.
Название практической работы, цель работы, ход работы, вывод, ответы на контрольные вопросы, должны быть выделены жирным шрифтом, так же как в методичке.
Контрольные вопросы:
1. Что такое тестирование ПС?
2. Чем тестирование отличается от отладки ПС?
3. Для чего проводится функциональное тестирование?
4. Каковы правила тестирования программы «как черного ящика»?
5. Как проводится тестирования программы по принципу «белого ящика»?
6. Как осуществляется сборка программы при модульно тестировании?
Практическая работа №6
Источник: infopedia.su
12. Оптимизация программ
Основной задачей программирования является создание правильных, а не эффективных программ. Эффективная программа не нужна, если она не обеспечивает правильных результатов.
Правильную, но не эффективную программу можно оптимизировать и сделать эффективной.
Для больших программ на стадии проектирования определяются требуемые параметры, включающие время выполнения и емкость памяти. Оптимизация программы – это процесс построения по исходной программе эквивалентной программы, обладающей лучшими характеристиками времени работы и/или объема занимаемой ОП.
Существует 3 типа программ:
- Часто используемые программы (ОС, компиляторы, постпроцессоры). Для них эффективность – первостепенная задача.
- Производственные программы. Эффективность существенна.
- Программы, написанные не программистами. Эффективность нужна если есть ограничения по памяти или по времени.
- Программа не помещается в памяти.
- Программа слишком долго выполняется.
- Программа должна быть включена в библиотеку и часто использоваться.
- Оптимизирующий компилятор.
- Определить критические области, подлежащие оптимизации. Применить локальную оптимизацию в критических областях (наиболее часто используемых частях программы).
- Синтаксический анализ программ.
- Анализ описаний данных и преобразование их в удобную для хранения и дальнейшего использования форму (в т.ч. вычисление констант).
- Распределение памяти для используемых в программе объектов.
- Установление соответствия между конструкциями входного языка и эквивалентными им конструкциями выходного языка.
- Печать в отредактированном виде текста исходной программы.
- Сообщение об обнаруженных в процесс трансляции ошибках в исходной программе.
- Эквивалентные преобразования на уровне входного языка с целью оптимизации программы.
- выигрыш в памяти за счет времени;
- дополнительные усилия программиста;
- сохранение промежуточных результатов.
Источник: studfile.net
Тема 2.8. Оптимизация программ. Оптимизирующие компиляторы
Оптимизация программы — это улучшение какой-либо характеристики программы, называемой критерием оптимизации. Оптимизация программ в основном выполняется по двум основным критериям: быстродействие и объему используемых данных.
Производительность приложения определяется самым узким его участком, поэтому в первую очередь нужно определить части программы, на которых будет выполняться оптимизация. Процесс оптимизации следует начать с профилировки программы. Профилировкой называют измерение производительности как всей программы, так и отдельных ее фрагментов, с целью нахождения «горячих точек» — тех участков программы, на выполнение которых расходуется наибольшее количество времени. При этом важно отметить, что ликвидация не самых «горячих» точек программы, практически не увеличивает ее быстродействия.
Основная цель профилировки – это исследование характера поведения приложения во всех его точках. В зависимости от степени детализации в качестве «точки» рассматривается как отдельная машинная команда, так и целая конструкция высокого языка — функция, цикл, процедура. Сложная программа состоит из большого числа функций.
Нет смысла оптимизировать их все – трудоемкость такого подхода будет выше выгод, полученных от оптимизации программы целиком. Для начала необходимо локализовать участки кода с максимальной вычислительной трудоемкостью.
Участки программы, которые в наибольшей степени влияют на ее производительность, в силу наиболее частого выполнения или своей ресурсоемкости называются критическим кодом. В поиске критического кода программы используют профайлеры (профилировщики) – специальные программы, которые измеряют временные затраты на выполнение участков кода программы.
Профилировщики представляют возможности для оптимизации программ. К таким программам относятся Intel VTune, AMD Code Analyst, profile.exe и множество других. Наиболее мощным из них на сегодняшний день является пакет от Intel. Эта программа позволяет измерить время обработки каждой команды и вывести полную статистику о состоянии процессора при выполнении каждой команды.
Большинство современных профилировщиков поддерживают следующий набор базовых операций:
• определение общего времени исполнения каждой точки программы;
• определение удельного времени исполнения каждой точки программы;
• определение причины и/или источника конфликтов;
• определение количества вызовов той или иной точки программы;
• определение степени покрытия программы.
Основные правила оптимизации:
1. Прежде чем приступать к оптимизации, необходимо иметь надежно работающий неоптимизированный вариант.
2. Основной прирост оптимизации дает не учет особенностей системы, а алгоритмическая оптимизация.
3. Обнаружив профилировщиком узкие места необходимо произвести оптимизацию в рамках языка высокого уровня.
Возможны ситуации, где в неудовлетворительной производительности кода виноваты процессор или подсистема памяти, а не компилятор. Лишь после анализа листинга следует приступать к ассемблерной оптимизации.
Оптимизация начинается с выделения профилировщиком критического кода и анализа его неоптимальности. Причем каждое внесенное изменение необходимо проверять профилировщиком. После завершения оптимизации локального фрагмента программы, необходимо выполнить контрольную профилировку всей программы целиком на предмет обнаружения новых появившихся «горячих точек».
Проводя оптимизацию, не следует забывать о ее цели. Фактически идеал недостижим, поэтому оптимизацию следует завершать когда:
1. Производительность программы признана удовлетворяющей;
2. В программе отсутствуют «горячие точки», то есть количество инструкций равномерно распределено по все программе, и дальнейшая оптимизация потребует переписывания большого количества кода;
3. Сложность алгоритма настолько высока, что не представляется возможным дальнейшая оптимизация без значительных временных затрат;
4. Критическая зависимость от платформы, когда дальнейшая машинно-зависимая оптимизация приведет к потере совместимости с одной из целевых платформ.
Ко всем методам оптимизации алгоритма предъявляются следующие требования:
1. оптимизация должна быть по возможности максимально машинно- независимой и переносимой на другие платформы (операционные системы) без существенных потерь эффективности.
2. оптимизация не должна увеличивать трудоемкость разработки (в том числе тестирования) приложения более чем на 10-15%.
3. оптимизирующий алгоритм должен давать выигрыш не менее чем на 20-25% в скорости выполнения.
4. оптимизация не должна допускать безболезненное внесение изменений.
Алгоритмические приемы оптимизации
Приемы оптимизации программы можно разделить на алгоритмические и машинно-зависимые способы. В случае использования алгоритмических приемов оптимизации используются различные математические и логические методы для улучшения параметров алгоритма. Такой способ оптимизации невозможно автоматизировать, успешность его применения зависит от программиста. Способность программиста к алгоритмической оптимизации программы зависит от его понимания предметной области: владения им базовых концепций применяемых алгоритмов и особенностей предметной области программы.
В первую очередь это замена алгоритмов на более быстродействующие. Часто бывает, что более простой алгоритм показывает низкую производительность по сравнению с более сложными. Тогда, возможна замена эквивалентных алгоритмов, например, замена пузырьковой сортировки массива на быструю сортировку.
В некоторых случаях возможна оптимизация программы за счет снижение точности. В зависимости от особенностей предметной области возможно уменьшить разрядность представления чисел или перейти от выполнения операций с числами с плавающей запятой к целым числам или числам с фиксированной запятой.
На практике используется весьма широкий набор машинно-независимых оптимизирующих преобразований, что связано с большим разнообразием неоптимальностей. К ним относятся:
• разгрузка участков повторяемости — это такой способ оптимизации, который состоит в вынесении вычислений из многократно исполняемых участков программы на участки программы, редко исполняемые. К этому виду преобразования относятся различные чистки зон, тел циклов и тел рекурсивных процедур, когда инвариантные по результату выполнения выражения, исполняемые при каждом прохождении участка повторяемости, выносятся из него. Если размещение осуществляется перед входом в участок повторяемости, то эту ситуацию называют чисткой вверх, если же за выходом из участка повторяемости, то чисткой вниз
• упрощение действий — этот способ оптимизации ориентирован на улучшение программы за счет замены групп (как правило, удаленных друг от друга) вычислений на группу вычислений, дающий тот же результат с точки зрения всей программы, но имеющих меньшую сложность.
• чистка программы — данный способ повышает качество программы за счет удаления из нее ненужных объектов и конструкций. Набор преобразований этого типа включает в себя следующие оптимизации: удаление идентичных операторов, удаление из программы операторов, недостижимых по управлению от начального, удаление несущественных операторов, то есть операторов не влияющих на результат программы, удаление процедур, к которым нет обращений, удаление неиспользуемых переменных и другие.
• экономия памяти и оптимизация работы с памятью — улучшения быстродействия возможно за счет уменьшения объема памяти, отводимой под информационные объекты программы в каждом ее исполнении.
• реализация действий — это способ повышения быстродействия программы за счет выполнения определенных ее вычислений на этапе трансляции.
• сокращение программы и другие методы.
Машинно-зависимые приемы оптимизации
Машинно-зависимые используют особенности устройства и работы конкретной системы. Ярким примером машинно-зависимой оптимизации является векторизация операций, т.е. использование потоковых расширений процессора, таких как MMX (MultiMedia eXtensions), SSE (Streaming SIMD Extensions) и т.п. Машино-зависимую оптимизацию можно выполнять двумя различными способами.
Первый способ основан на понимании работы кодогенератора компилятора, его алгоритма и рекомендуется для приложений, в которых компилятор выбирается в начале проекта и в дальнейшем не меняется. При использовании такого способа преобразуется исходный код программы, написанный на языке высокого уровня.
Для тех проектов, в которых заранее не известен компилятор (OpenSource проекты, кроссплатформенные приложения) применятся другой способ, основанный на замещении ресурсоемких участков кода ассемблерными вставками. При такой оптимизации ухудшается переносимость кода на другие платформы. Машинно-зависимые способы оптимизации довольно хорошо автоматизируются и большую часть их выполняют оптимизирующие компиляторы. Однако всегда остаются моменты в программе, которые можно оптимизировать вручную.
Источник: studopedia.ru