Оптимизация (информатика)

Хотя термин «оптимизация» происходит от слова «оптимум»^[2], достижение действительно оптимальной системы на практике встречается редко (см. супероптимизация)^[3]. Чаще оптимизация направлена на улучшение системы по конкретному качественному критерию, а не на универсальное совершенство. Это приводит к компромиссам: улучшение одного показателя часто ухудшает другой. Частый пример — компромисс между временем и памятью, когда ускорение программы требует большего объёма памяти. В обратной ситуации — при дефиците памяти — предпочтение отдаётся более медленным, но менее требовательным по памяти алгоритмам. Универсального решения для всех случаев обычно не существует, и программисты вынуждены расставлять приоритеты между атрибутами в зависимости от задач. Типичные показатели (метрики) включают скорость выполнения, проходная способность, задержка, использование оперативной памяти, долговременного хранения, сетевого трафика, энергопотребление и износ оборудования. Наиболее распространённая метрика — это скорость работы.

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

Оптимизация возможна на разных уровнях. Обычно более высокие уровни оказывают больший эффект и труднее поддаются изменениям позднее, часто требуя значительной переработки или полного переписывания проекта. Поэтому оптимизация часто проводится по этапам — от верхнего уровня к нижнему, где ранние улучшения достигаются проще и быстрее, а последующие — сложнее и менее значимы. Однако иногда производительность в целом зависит от низкоуровневых частей программы, и небольшие доработки на поздних этапах или раннее внимание к низкоуровневым деталям могут существенно повлиять на результат. В ходе разработки к производительности обычно обращаются на протяжении всего проекта, однако интенсивная оптимизация зачастую относится к доводке, выполняемой в конце (или вовсе не делается). В больших проектах оптимизация проходит циклически: улучшение одной части выявляет узкие места в другой, а процесс прекращается, когда производительность становится приемлемой или дальнейшие усилия теряют смысл. Лучшими практиками считается постоянное мониторирование и тестирование производительности на каждом этапе разработки^[4][5].

Поскольку производительность входит в требования к программе, слишком медленное приложение не выполняет своей задачи: видеоигра с частотой 60 кадров в секунду приемлема, но при 6 кадрах в секунду её работа считается неудовлетворительно «рваной». Поэтому оценка производительности необходима с самого начала, чтобы убедиться в достижимости целевых показателей в итоговой системе. Иногда это игнорируют, предполагая, что оптимизацию всегда можно провести позже, результатом чего становятся прототипы, которые медленнее целевой производительности на порядок величины и более, и даже проекты, обречённые на провал из-за непреодолимых архитектурных ограничений, как, например, Intel 432. Бывают и такие случаи, когда только годы последующей оптимизации и появление новых технологий позволяют добиться приемлемой скорости работы, как в случае с Java, которой лишь с появлением HotSpot удалось достичь скорости, сравнимой с нативным кодом^[6]. Различие производительности между прототипом и конечной системой, а также возможности последующей оптимизации — источник неопределённости и риска.

На самом верхнем уровне проводится оптимизация архитектуры — наилучшее использование доступных ресурсов при учёте целей, ограничений и предполагаемой нагрузки. Архитектурные решения критически влияют на производительность: при ограничении по задержке сети систему проектируют так, чтобы минимизировать число сетевых запросов, предпочитая одну итерацию протокола или даже передачу по push-протоколу, а не множество. Выбор проектных решений зависит от целей: компилятор, ориентированный на скорость трансляции, обычно реализуется в виде однопроходного компилятора, тогда как для максимальной скорости генерируемого кода лучше использовать многопроходный компилятор. Здесь же определяется выбор платформы и языка — зачастую смена требует переписывания всей системы, однако модульное проектирование позволяет заменить лишь отдельные компоненты (например, критически важные по производительности части на Python могут быть написаны на C). Для распределённых систем важен выбор архитектуры (клиент-сервер, peer-to-peer и др.), который меняется сложно или вовсе невозможен без синхронной замены всех компонентов.

Следующий уровень — подбор алгоритмов и структур данных, а также их эфективная реализация. Выбор алгоритмической схемы и структуры данных влияет на быстродействие сильнее всего, после архитектурных решений. Зачастую замена структуры данных требует больших изменений, чем замена алгоритма, ведь выбор структуры и её характеристик напрямую отражается на коде. Использование абстрактных типов данных и ограничение областей влияния конкретных реализаций позволяют облегчить такие изменения. При отображении структуры данных в базу данных приходится производить миграции схемы либо серьёзные инфраструктурные доработки^[7].

Выбирая алгоритмы, предпочтение отдают постоянным (O(1)), логарифмическим O(log n), линейным O(n) и иногда линейно-логарифмическим O(n log n) схемам по времени и памяти. Алгоритмы с квадратной сложностью O(n²) плохо масштабируются, а даже линейные становятся проблемой при частом запуске; по возможности заменяются на более быстрые.

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

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

На этом уровне конкретные варианты использования синтаксиса языка или структур управления могут существенно влиять на производительность. Например, в ранних компиляторах C конструкция while(1) была медленнее, чем for(;;) для бесконечных циклов. Современные оптимизирующие компиляторы обычно устраняют такие различия, однако конечный результат зависит от конкретного компилятора, языка и архитектуры. Типовые техники включают вынос инварианта из цикла и оптимизация возврата значения, минимизирующие лишние переменные и переходы.

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

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

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

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

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

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

JIT-компиляторы способны генерировать машинный код на основе информации, получаемой во время выполнения, жертвуя временем компиляции ради эффективности. Подобные подходы появились ещё в ранних системах регулярных выражений и ныне массово применяются в Java (HotSpot) и JavaScript (V8). В отдельных случаях адаптивная оптимизация позволяет превышать уровень, достижимый статическим компилятором, за счёт настройки параметров во время выполнения.

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

Самоизменяемый код может модифицировать себя для оптимизации во время выполнения — чаще встречался в ассемблерных программах.

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

Оптимизации делятся на платформенно-независимые (работающие на любом оборудовании) и платформенно-зависимые, использующие уникальные особенности конкретной архитектуры или модели процессора. К платформенно-независимым относят универсальные техники, такие как разворачивание цикла, минимизация числа вызовов функций, эффективное использование памяти и т. д. Например, обнаружено^[8], что вложенные циклы могут давать больше операций в единицу времени, чем альтернативные варианты. Эти методы направлены на сокращение пути исполнения программ и/или снижение потребления памяти. Платформенно-зависимые методы включают оптимизации с учётом параллелизма команд, планирования инструкций, настройки кэша (параметры могут различаться не только на разных архитектурах, но и на моделях одного семейства).

Многие вычислительные задачи можно реализовать разными методами, отличающимися по эффективности. Перевод программы на более эффективную схему называется снижением мощности операций. Пример на языке C: суммирование всех чисел от 1 до N.

int i, sum = 0;
for (i = 1; i <= N; ++i) {
  sum += i;
}
printf("sum: %d\n", sum);

Эта программа (если не учитывать переполнение арифметики) может быть записана математической формулой:

int sum = N * (1 + N) / 2;
printf("sum: %d\n", sum);

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

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

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

Как правило, оптимизация направлена на один–два ресурса: время, память, место на диске, пропускную способность, энергопотребление и т. д. Это требует жертв: например, увеличение размера кэша ускоряет программу, но повышает расход памяти. Классический обмен — между читаемостью кода и его лаконичностью.

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

Оптимизация включает поиск узких мест системы: компонентов, ограничивающих производительность. Обычно это горячие участки кода, однако «бутылочным горлышком» может быть и подсистема I/O или сеть.

В программировании распределение расхода ресурсов часто подчиняется степенному закону, и принцип Парето применим к оптимизации: 80 % ресурсов тратится 20 % операций^[9]. В разработке ПО нередко используется правило 90/10: 90 % времени программа проводит в 10 % кода.

Более сложные алгоритмы и структуры эффективнее при больших данных, а при малых объёмах их сложность окупается редко: адаптивные или гибридные схемы часто оказываются быстрее линейных для любых данных. Профилировщик помогает анализировать, когда и какой подход эффективнее^[10].

Профилирование даёт не только поиск узких мест, но и целый арсенал приёмов анализа и оптимизационного руководства. Эмпирическая алгоритмика занимается изучением поведения алгоритмов с помощью эмпирической проверки, включая профилирование. Оптимизация с использованием профилирования — автоматизированное использование таких данных компилятором. Некоторые языки включают инструменты для этой цели^[11]. Профилирование нередко акцентируется на улучшении использования кеша^[12], а также может улучшать управление ресурсами и конечный пользовательский опыт^[13].

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

Как правило, оптимизация начинается с выбора наиболее эффективных по времени и памяти алгоритмов и структур^[14]. Такими средствами достигается максимальный эффект, в отличие от микрооптимизаций, редко дающих выигрыш больше нескольких процентов^[14]. Если откладывать оптимизацию до удобного момента, смена алгоритма обернётся полной переделкой системы.

Микрооптимизации часто снижают читаемость и усложняют сопровождение программ.

Дональд Кнут отмечал:

«Мы должны забывать о малых улучшениях в 97 % случаев: преждевременная оптимизация — корень всех зол. Однако мы не должны упускать возможности в тех 3 %, где это действительно важно»^[15]

Позже он приписал эту фразу Тони Хоару, однако последний опроверг авторство^[16][17].

«В инженерии 12-процентное улучшение, достигаемое с лёгкостью, не считается незначительным. То же должно быть справедливо и для программирования»^[15]

Термин «преждевременная оптимизация» часто используется как лозунг против избыточной оптимизации вообще^{[14][18][19][20]}. Нередко, следование принципу SOLID (чистого кода) ведёт к усложнению программ при снижении эффективности^[21].

Определяя приоритеты оптимизации, стоит руководствоваться законом Амдала — оптимизируют те части, которые реально потребляют наибольшее время, что зачастую непросто выявить без профилирования.

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

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

Оптимизация средствами макросов различна в зависимости от языка.

В процедурных языках (например, C и C++) макросы реализуются с помощью подстановки токенов. В современном программировании их часто заменяют inline-функциями, что даёт и типовую безопасность. В обоих случаях тело функции/макроса становится доступным компилятору для дальнейших оптимизаций, например, свёртывание констант.

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

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

В обоих случаях вычисления переносятся на этап компиляции. Отличие в том, что макросы C не выполняют вычислений, а их способность к оптимизации определяется компилятором, тогда как макросы Lisp/C++-шаблоны могут реализовывать любые вычисления. Также, макросы C не поддерживают рекурсию и не являются Тьюринг-полными.

Как и всякая оптимизация, трудно заранее определить, где применение макросов даст максимальный эффект.

Автоматические и ручные оптимизации могут сочетаться (см. также Категория:Оптимизации компилятора).

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

Глобальная (системная) оптимизация проводится вручную программистами или администраторами, поскольку слишком сложна для автоматизации. Несмотря на трудоёмкость, она способна повысить эффективность всей системы. Пространство вариантов оптимизации огромно, поэтому применяются метаэвристики и машинное обучение^[22].

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

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

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

Иногда узкие места связаны не с алгоритмами и структурами, а с ограничениями языка — в таких случаях переписывают критически важные части на более низкоуровневом языке (например, Python, части которого представлены реализованными на C модулями).

С учётом «закона 90/10» (90 % времени тратится в 10 % кода) оптимизация только этих участков даёт максимальный общий эффект.

Ручная оптимизация способна ухудшить понятность и поддержку кода. Поэтому такие изменения тщательно документируют в исходном коде.

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

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

Некоторые языки используют промежуточный язык для оптимизации.

Грид-технологии и распределённые вычисления позволяют оптимизировать всю систему, перераспределяя задачи между занятыми и свободными машинами.

Иногда время, затрачиваемое на оптимизацию, становится проблемой.

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

Автоматические оптимизаторы или компиляторы с расширенной оптимизацией зачастую требуют собственной оптимизации для ускорения собственной работы или повышения эффективности кодогенерации. Компиляция с включёнными оптимизациями занимает больше времени — что важно для крупных программ.

В частности, для JIT-компиляции скорость компонента компиляции критична для эффективности всей системы.

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