Теоретический материал
ВВЕДЕНИЕ
В современном мире разработка программного обеспечения (ПО) превратилась в одну из самых дорогостоящих индустрий, и любые ошибки и недочеты в процессе его создания могут привести к нежелательным результатам. Написание запутанного кода чревато проблематичным изменением и сопровождением готового продукта. Ошибки, не выявленные в ходе тестирования ПО, приводят к снижению надежности и затягиванию сроков его внедрения. Поэтому актуальность разработки совершенного кода очень высока, так как она позволяет повысить его надежность. Очевидно, что такой код должен быть максимально оптимальным. Примитивный, но правильный код, написанный программистом, во многих случаях может быть усовершенствован. Чаще всего причиной является то, что выбранный алгоритм, является шаблонным и не учитывает условия поставленной задачи, то есть транслирует языковые выражения вне зависимости от их смысла в определенные последовательности команд. Формальный алгоритм не различает особые случаи и не использует их выгод. Выбор такого подхода приводит к результатам, которые лишь отчасти отвечают требованиям экономии памяти и скорости выполнения.
Для того чтобы сгенерировать код, который использует имеющиеся команды и ресурсы машины с наибольшей эффективностью, должны быть использованы более сложные схемы трансляции. Они называются оптимизациями, а использующие их компиляторы – оптимизирующими компиляторами. Так же важно придерживаться правила 10/90, которое гласит, что 10% времени потраченное на планирование до начала работы, экономит 90% времени при решении поставленных задач. Архитектурный дизайн системы особенно сильно влияет на её производительность. Однако выбор алгоритма влияет на эффективность больше, чем любой другой элемент дизайна. Более сложные алгоритмы и структуры данных могут хорошо оперировать с большим количеством элементов, в то время как простые алгоритмы подходят для небольших объёмов данных – накладные расходы на инициализацию более сложного алгоритма могут перевесить выгоду от его использования.
Чем больше памяти использует программа, тем быстрее она обычно выполняется. Например, сортировка ступенчатого массива обычно выполняется построчно – программа читает каждую строку, сортирует её, а затем выводит эту строку. Такая программа хорошо экономит память, т.к. использует её только для хранения одной строки, но производительность программы обычно очень плохая. Производительность может быть значительно улучшена чтением целого файла и записью потом отсортированного результата.
Однако такой способ использует больше памяти. Кэширование результата также эффективно, однако требует большего количества памяти для использования.
Цель работы – изучить теоретические основы оптимизации программного кода.
Поставленная цель определила следующие задачи:
1. Рассмотреть термин «оптимизация кода» и связанные с ним понятия.
2. Изучить виды и подход к оптимизации кода.
3. Познакомиться с методиками оптимизации кода.
ТЕРМИН «ОПТИМИЗАЦИЯ КОДА» И СВЯЗАННЫЕ С НИМ ПОНЯТИЯ
Оптимизация кода – это один из способов преобразования кода, приводящий к улучшению его характеристик и повышению производительности программы. Среди целей оптимизации можно выделить уменьшение размера кода, объема используемой оперативной памяти, повышение скорости выполнения программы, уменьшение количества операций ввода – вывода. Так как под оптимизацией понимается внесение незначительных поправок, то есть изменение одного класса, одного метода или всего лишь нескольких строк кода. Поэтому какие-либо крупные изменения проекта, приводящие к повышению производительности оптимизацией не считаются.
Оптимизацию производительности следует отличать от рефакторинга. Цель рефакторинга – сделать код программы более легким для понимания. Как и оптимизация, рефакторинг обычно не изменяет поведение программы. Но оптимизация часто затрудняет понимание кода, что противоположно рефакторингу.
ВИДЫ ОПТИМИЗАЦИИ ПРОГРАММНОГО КОДА
Оптимизация кода может проводиться, как и вручную, программистом, так и автоматизировано. В последнем случае оптимизатор может быть, как отдельным программным средством, так и быть встроенным в компилятор.
Существуют такие понятия как высокоуровневая и низкоуровневая оптимизация. Высокоуровневые оптимизации в большинстве проводятся программистом, который, оперируя абстрактными сущностями (функциями, процедурами, классами и т.д.) и представляя себе общую модель решения задачи, может оптимизировать дизайн системы.
Оптимизации на уровне элементарных структурных блоков исходного кода (циклов, ветвлений и т.д.) тоже обычно относят к высокому уровню; некоторые выделяют их в отдельный уровень. Низкоуровневая оптимизация производится на этапе превращения исходного кода в набор машинных команд, и зачастую именно этот этап подвергается автоматизации.
ПОДХОД К ОПТИМИЗАЦИИ ПРОГРАММНОГО КОДА
Рассматривая целесообразность оптимизации кода, надо придерживаться следующего алгоритма:
1. Написать хороший и понятный код, поддающийся легкому изменению
2. Если производительность не устраивает:
a. Сохранить работоспособную версию кода, чтобы позднее можно было
вернуться к «последнему нормальному состоянию»
b. Оценить производительность системы с целью нахождения горячих точек
c. Выяснить, обусловлено ли плохое быстродействие неадекватным проектом, неверными типами данных или неудачным алгоритмами и определить, уместна ли оптимизация кода, если оптимизация кода неуместна, вернуться к пункту 1.
d. Оптимизировать узкое место, определенное на этапе (с)
e. Оценить каждое улучшение.
f. Если оптимизация не привела к улучшению кода, вернуться к коду,
сохраненному на этапе (а) (как правило, более чем в половине случаев попытки оптимизации будут приводить лишь к незначительному повышению производительности или к ее снижению)
3. Повторить процесс, начиная с п.2.
4 МЕТОДИКИ ОПТИМИЗАЦИИ КОДА
1. Логические выражения
Рассмотрим эффективное использование логических выражений.
• Прекращение проверки сразу же после получения ответа
Например, выражение if ( 5 < y && y < z ). Если y окажется меньше 5, то вторую проверку выполнять не нужно. Некоторые языки поддерживают так называемую «сокращенную оценку выражений», при которой компилятор генерирует код, автоматически прекращающий проверку после получения ответа.
Если выбранный язык не поддерживает сокращенную оценку, нужно избегать операторов && и ||, используя вместо них дополнительную логику. Для сокращенной оценки код следовало бы изменить так:
if ( 5 < y ) {
if ( y < z ) ... }
Принцип прекращения проверки сразу по получении ответа уместен и других случаях.
• Упорядочение проверок по частоте
Для повышения производительности рекомендуется размещать ветви, вероятность выбора которых является наибольшей, ближе к началу. В том случае будет меньше тратиться времени выбор требуемого варианта. Этот принцип относится к блокам case и цепочкам оператора if.
• Сравнение быстродействия похожих структур логики
В описанном выше пункте указанно, что данную оптимизацию можно выполнить и для блоков case, и для оператора if. В зависимости от среды любой из подходов может оказаться более выгодными. Так, например, в С# быстрее выполняется блок case. То есть без оценки результатов в рабочей среде невозможно обойтись.
• Замена сложных выражений на обращение к таблице
В некоторых случаях более быстрым, чем выполнение сложной логической цепи, может оказаться просмотр таблиц. К категоризации чего-то и выполнении того или иного действия, основанного на конкретной категории, чаще всего сводится суть сложной цепи.
2. Использование выражения
Большинство задач программирования нуждаются в применении математических и логических выражений. Сложные выражения обычно дороги, но есть способы их удешевления.
• Алгебраические тождества
Алгебраические тождества не редко позволяют заменить «дорогие» операции на более «дешевые». Так, следующие выражения логически эквивалентны:
not a and not b
not (a or b)
Выбор второго выражение вместо первого, экономит одну операцию not. Избавление от одной операции not, не приведет к заметным результатам, но тем неменее этот принцип значительно полезен. Джон Бентли отмечает, что в одной программе проверялось условие sqrt(x) < sqrt(y) (Bentley, 1982). Так как sqrt(x) меньше sqrt(y), только когда x меньше, чем y, исходную проверку можно заменить на x < y. С учетом дороговизны метода sqrt(), можно сказать, что достигнута существенная экономии.
• Снижение стоимости операции
Как уже было сказано, снижение стоимости операций подразумевает замену дорогой операции более дешевой. Вот некоторые возможные варианты:
замена умножения сложением;
замена возведения в степень умножением;
замена тригонометрических функций их эквивалентами;
замена типа long long на long или int (следите при этом за аспектами
производительности, связанными с применением целых чисел естественной и
неестественной длины);
замена чисел с плавающей запятой числами с фиксированной точкой или целые числа;
замена чисел с плавающей запятой с удвоенной точностью числами с одинарной точностью;
замена умножения и деления целых чисел на два операциями сдвига.
• Инициализация во время компиляции
Если при вызове метода, передается ему в качестве единственного аргумента именованная константа или непосредственное значение, лучше заранее вычислить нужное значение, присвоить его константе и избежать вызова метода. Это же справедливо и для других операций.
• Недостатки системных методов
Системные методы очень дорогие и часто обеспечивают избыточную точность. Зачастую такая предельная точность не нужна, не стоит тратить на нее время.
• Использование констант корректного типа
Используйте именованные константы и литералы, имеющие тот же тип, что и переменные, которым они присваиваются. Если константа и соответствующая ей переменная имеют разные типы, перед присвоением константы переменной компилятор должен будет выполнить преобразование типа.
• Устранение часто используемых подвыражений
Вместо повторяющихся несколько раз выражений, следует присвоить его значение константе и использовать ее там, где ранее вычислялось само выражение.
3. Циклы
Горячие точки часто следует искать именно внутри циклов, так как они выполняются многократно. Методики, описываемые ниже, помогут ускорить выполнение циклов.
• Размыкание цикла
Если во время выполнения цикла решение не изменяется, можно разомкнуть
(unswitch) цикл, приняв решение вне цикла. Обычно для этого нужно вывернуть цикл наизнанку, то есть поместить циклы в условный оператор, а не условный оператор внутрь цикла. Замыканием (switching) цикла называют принятие решения внутри цикла при каждой его итерации.
• Объединение циклов
Бывает так, что циклы работают с один набором элементов, тогда их можно объединить (jamming). Выгода заключается в устранении затрат, связанных с выполнением дополнительно цикла.
Однако этого не стоит делать, когда нет точной информации об изменении позднее индексов, иначе это может привести к несовместимости циклов. Прежде чем объединять циклы, убедитесь, что это не нарушит работу остальных частей кода.
• Развертывание цикла
Целью развертывания (unrolling) цикла является сокращение затрат, связанных с его выполнением. Экономия времени после оптимизации составляет в среднем 50%.
• Минимизация объема работы, выполняемой внутри цикла
Как говорилось, ранее одной из методик повышения эффективности циклов является минимизация объема работы, выполняемой внутри цикла. Если есть возможность произвести вычисление выражения или его части вне цикла и использовать внутри цикла результат вычисления, то следует так сделать.
4. Методы
Одним из самых эффективных способов оптимизации кода является грамотная декомпозиция программы на методы. Небольшие, хорошо определенные методы делают программу компактнее, устраняя повторяющиеся фрагменты кода. Они упрощают оптимизацию, потому что рефакторинг одного метода улучшает все методы, которые его вызывают. Небольшие методы относительно легко переписывать на низкоуровневый язык.
Объемные хитроумные методы понять сложно, а после переписывания их на низкоуровневом языке ассемблера это вообще невыполнимо. Переписывание кода на низкоуровневый язык обычно положительно влияет и на быстродействие кода, и на его объем. Типичный подход к оптимизации при помощи низкоуровневого языка таков:
1. Напишите все приложение на высокоуровневом языке.
2. Выполните полное тестирование приложения и проверьте его корректность.
3. Если производительность недостаточна, выполните профилирование приложения с целью выявления горячих точек. Так как около 50% времени выполнения программы обычно приходится примерно на 5% кода, горячими точками обычно будут небольшие фрагменты программы.
4. Перепишите несколько небольших фрагментов на низкоуровневом языке для повышения общей производительности программы.
5. Изменения типов данных
Изменение типов данных может быть эффективным способом сокращения кода и повышения его быстродействия - использование вместо чисел с плавающей запятой целые числа. Также сложение и умножение целых чисел, как правило, выполняются быстрее, чем аналогичные операции над числами с плавающей запятой. Например, циклы выполняются быстрее, если индекс имеет целочисленный тип.
• Использование массивов с минимальным число измерений
Использовать массивы, имеющие несколько измерений, сложно. Ускорить выполнение программы можно, путем структурирования данных так, чтобы их можно было хранить в одномерном, а не двумерном или трехмерном массиве.
• Использование дополнительных индексов
Использование дополнительного индекса подразумевает добавление данных, связанных с основным типом данных, которые повышают эффективность обращений к нему. Связанные данные добавляют к основному типу или хранят в параллельной структуре.
• Кэширование
Кэширование – это способ хранения нескольких значений, в котором значения, используемые чаще всего, получить проще, чем значения, используемые редко. Например, если программа читает записи с диска случайным образом, метод может хранить записи, считываемые наиболее часто, в кэше. Метод проверяет, имеется ли запись в кэше, при получении запроса записи. При положительном результате, запись не считывается с диска, а возвращается прямо из памяти. Кэширование можно применять и в разных областях. Можно кэшировать и результаты ресурсоемких вычислений, особенно если их параметры просты. Польза кэширования зависит от числа запросов кэшированной информации, от относительной стоимости обращения к кэшированному элементу, создания не кэшированного элемента и сохранения нового элемента в кэше. Другими словами, кэширование выгодно тогда, когда генерирование нового элемента дороже. Как любая методики оптимизации, кэширование усложняет код и не редко бывает причиной возникновения ошибок.
Следует отметить, что результаты конкретных видов оптимизации во многом зависят от языка, компилятора и среды. Не оценив результатов оптимизации, невозможно сказать, помогает она программе или вредит.