17 Авг 2017

Оптимизация кода

17 Авг 2017

Определение и свойства
Виды оптимизации
Выбор оптимизируемого участка
Вред и польза оптимизаций
Итог
PVS-Studio
Библиографический список

Определение и свойства

Оптимизация кода - различные методы преобразования кода ради улучшения его характеристик и повышения эффективности. Среди целей оптимизации можно указать уменьшения объема кода, объема используемой программой оперативной памяти, ускорение работы программы, уменьшение количества операций ввода-вывода.

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

Виды оптимизации

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

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

Выбор оптимизируемого участка

При оптимизации кода вручную существует еще одна проблема: нужно знать не только, каким образом проводить оптимизацию, но и в каком месте её применить. Обычно из-за разных факторов (медленные операции ввода, разница в скорости работы человека-оператора и машины и т.д.) лишь 10% кода занимают целых 90% времени выполнения (конечно, утверждение довольно умозрительно, и имеет сомнительное основание в виде закона Парето, однако выглядит довольно убедительно у Э. Таненбаума). Так как на оптимизацию придется расходовать дополнительное время, поэтому вместо попыток оптимизации всей программы лучше будет оптимизировать эти "критичные" ко времени выполнения 10%. Такой фрагмент кода называют узким местом или бутылочным горлышком (bottleneck), и для его определения используют специальные программы - профайлеры, которые позволяют замерять время работы различных частей программы.

На самом деле, на практике оптимизация зачастую проводится после этапа "хаотического" программирования (включающего такие вещи, как "копипаст", "потом разберемся", "и так сойдет"), поэтому представляет собой смесь из собственно оптимизации, рефакторинга и исправления ошибок: упрощение "причудливых" конструкций – вроде strlen(path.c_str()), логических условий (a.x != 0 && a.x != 0) и т.п. Для таких оптимизаций профайлеры вряд ли пригодны. Однако для обнаружения таких мест можно использовать программы статического анализа - средства поиска семантических ошибок на основе глубокого анализа исходного кода – ведь, как видно из второго примера, неэффективный код может быть следствием ошибок (как, например, опечатки в данном примере - скорее всего, имелось ввиду a.x != 0 && a.y != 0). Хороший статический анализатор обнаружит подобный код, и выведет предупреждающее сообщение.

Вред и польза оптимизаций

Практически ко всему в программировании надо относиться рационально, и оптимизации - не исключение. Считается, что неопытный программист на ассемблере обычно пишет код, который в 3-5 раз медленнее, чем код, сгенерированный компилятором (Зубков). Широко известно выражение по поводу ранних, довольно низкоуровневых (вроде борьбы за лишний оператор или переменную) оптимизаций, сформулированное Кнутом: "Преждевременная оптимизация — это корень всех бед".

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

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

Например, рассмотрим язык Си++ и т.н. Return-Value Optimization, суть которой в том, что компилятор может не создавать копии возвращаемого функцией временного объекта. Так как в этом случае компилятор "пропускает" копирование, этот прием также называется "Copy elision". Итак, следующий код:

#include <iostream>
 
struct C {
  C() {}
  C(const C&) { std::cout << "A copy was made.\n"; }
};
 
C f() {
  return C();
}
 
int main() {
  std::cout << "Hello World!\n";
  C obj = f();
}

может иметь несколько вариантов вывода:

Hello World!
A copy was made.
A copy was made.

Hello World!
A copy was made.

Hello World!

Как ни странно, все три варианта являются законными, так как в стандарте языка позволяется пропускать вызов копирующего конструктора в данном случае, даже если у конструктора есть побочные эффекты (§12.8 Копирование объектов класса, пункт 15).

Итог

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

PVS-Studio

В статическом анализаторе PVS-Studio реализован набор диагностик, позволяющих обнаруживать некоторые ситуации, когда код может быть оптимизирован. Однако PVS-Studio, как и любой статический анализатор, не может выступать в качестве замены инструментов профилирования. Выявить узкие места могут только динамические анализаторы программ. Статические анализаторы не знают, какие входные данные получают программы и как часто выполняется тот или иной участок кода. Поэтому мы и говорим, что анализатор предлагает выполнить некоторые "микро оптимизации" кода, которые вовсе не гарантируют прироста производительности.

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