Введение
Улучшение эффективности программного обеспечения
В информатике оптимизация программ, оптимизация кода или оптимизация программного обеспечения — это процесс изменения программной системы для повышения её производительности или снижения потребления ресурсов. Как правило, компьютерная программа может быть оптимизирована для более быстрого выполнения, для работы с меньшим объёмом памяти или других ресурсов, либо для снижения энергопотребления.
Общий
Хотя слово "оптимизация" имеет тот же корень, что и "оптимальный", процесс оптимизации редко приводит к созданию действительно оптимальной системы. Система обычно может быть оптимизирована не в абсолютном смысле, а лишь относительно заданного критерия качества, который может противоречить другим возможным критериям. В результате оптимизированная система, как правило, будет оптимальной только для конкретного приложения или целевой аудитории. Можно сократить время выполнения задачи программой, но при этом увеличить потребление памяти. В приложении, где память ограничена, можно намеренно выбрать более медленный алгоритм, чтобы снизить использование памяти. Часто не существует универсального решения, подходящего для всех случаев, поэтому инженеры идут на компромиссы, чтобы оптимизировать наиболее важные характеристики. Кроме того, усилия, необходимые для достижения полной оптимальности программного обеспечения, исключающей дальнейшие улучшения, почти всегда неоправданно велики по сравнению с получаемыми преимуществами; поэтому процесс оптимизации может быть прекращен до достижения полностью оптимального решения. К счастью, обычно наибольший эффект достигается на ранних этапах. Даже при заданном критерии качества (например, скорости выполнения) большинство методов оптимизации лишь улучшают результат, но не претендуют на получение оптимального значения. Супероптимизация – это процесс поиска действительно оптимального результата.
Уровни оптимизации
Оптимизация может происходить на различных уровнях. Как правило, более высокие уровни оказывают большее влияние, и их сложнее изменить на поздних этапах проекта, что требует значительных изменений или полной переработки, если это необходимо. Таким образом, оптимизация обычно выполняется последовательно, сверху вниз: первоначальные улучшения достигаются легче и дают больший эффект, а последующие – сложнее и требуют больших усилий. Однако в некоторых случаях общая производительность зависит от эффективности низкоуровневых компонентов программы, и незначительные изменения на поздней стадии или учет деталей низкого уровня на раннем этапе могут оказать существенное влияние. В течение проекта обычно уделяется некоторое внимание эффективности, хотя степень этого внимания сильно варьируется, но существенная оптимизация часто рассматривается как завершающий этап, который выполняется, если вообще выполняется. В длительных проектах обычно возникают циклы оптимизации, когда улучшение одной области выявляет ограничения в другой. Эти циклы обычно прекращаются, когда производительность становится приемлемой или дальнейшие улучшения оказываются слишком незначительными или дорогостоящими. Поскольку производительность является частью спецификации программы, неприемлемо медленная программа непригодна для использования: видеоигра с частотой 60 Гц (кадров в секунду) приемлема, но 6 кадров в секунду – это неприемлемо низкая и прерывистая производительность. Производительность необходимо учитывать с самого начала, чтобы гарантировать, что система сможет обеспечить достаточный уровень производительности, и ранние прототипы должны демонстрировать хотя бы приблизительно приемлемую производительность, чтобы была уверенность в том, что конечная система (после оптимизации) достигнет требуемого уровня. Иногда этот аспект игнорируется, исходя из убеждения, что оптимизацию всегда можно выполнить позже, что приводит к созданию слишком медленных прототипов – часто на порядок или более – и систем, которые в конечном итоге терпят неудачу из-за архитектурной невозможности достижения поставленных целей производительности, как, например, Intel 432 (1981); или систем, для достижения приемлемой производительности которых требуются годы работы, как Java (1995), которая достигла приемлемой производительности только с HotSpot (1999). Степень изменения производительности между прототипом и готовой системой, а также возможность ее оптимизации, могут быть значительным источником неопределенности и риска.
Уровень проектирования
На самом высоком уровне проектирование может быть оптимизировано для наилучшего использования доступных ресурсов, учитывая цели, ограничения и ожидаемую нагрузку. Архитектурное проектирование системы оказывает решающее влияние на её производительность. Например, система, производительность которой ограничена сетевой задержкой (когда сетевая задержка является основным фактором, ограничивающим общую производительность), будет оптимизирована для минимизации сетевых обращений, в идеале выполняя один запрос (или вообще без запросов, как в протоколе push), а не множество обменов данными. Выбор проектировочного решения зависит от целей: при разработке компилятора, если приоритетом является скорость компиляции, однопроходный компилятор будет быстрее, чем многопроходный (при одинаковом объеме работы), но если целью является скорость генерируемого кода, более медленный многопроходный компилятор лучше справится с этой задачей, хотя и потребует больше времени на выполнение. Выбор платформы и языка программирования происходит на этом уровне, и их изменение часто требует полной переработки, хотя модульная система может позволить переписать только некоторые компоненты, например, программа на Python может переписать критически важные для производительности участки на C. В распределенной системе выбор архитектуры (клиент-сервер, одноранговая сеть и т.д.) происходит на этапе проектирования и может быть сложно изменить, особенно если все компоненты нельзя заменить одновременно (например, устаревшие клиенты).
Алгоритмы и структуры данных
При наличии общего дизайна, следующим шагом является хороший выбор эффективных алгоритмов и структур данных, а также их эффективная реализация. После проектирования выбор алгоритмов и структур данных оказывает наибольшее влияние на эффективность программы, чем любой другой её аспект. Как правило, структуры данных сложнее изменить, чем алгоритмы, поскольку предположения о структуре данных и её производительности используются во всей программе, хотя это можно минимизировать, используя абстрактные типы данных в определениях функций и ограничивая определения конкретных структур данных несколькими местами. Что касается алгоритмов, важно, чтобы их сложность была постоянной O(1), логарифмической O(log n), линейной O(n) или, в некоторых случаях, логарифмически-линейной O(n log n) относительно входных данных (как по времени, так и по памяти). Алгоритмы с квадратичной сложностью O(n²) не масштабируются, и даже линейные алгоритмы могут вызывать проблемы при многократном вызове, поэтому их обычно заменяют на алгоритмы с постоянной или логарифмической сложностью, если это возможно. Помимо асимптотической сложности, важны и константы: асимптотически более медленный алгоритм может оказаться быстрее или компактнее (из-за своей простоты), чем асимптотически более быстрый, при работе с небольшими входными данными, что может иметь место на практике. Часто наилучшую производительность обеспечивает гибридный алгоритм, поскольку этот компромисс меняется в зависимости от размера входных данных. Общий способ повышения производительности – избегать лишних операций. Хорошим примером является использование быстрого пути для часто встречающихся случаев, что позволяет улучшить производительность за счёт исключения ненужной работы. Например, можно использовать простой алгоритм разметки текста для латинских шрифтов и переключаться на более сложный алгоритм только для сложных систем письма, таких как деванагари. Другой важной техникой является кэширование, особенно мемоизация, которая позволяет избежать повторных вычислений. Из-за важности кэширования в системе часто используется несколько уровней кэша, что может привести к проблемам с использованием памяти и ошибкам из-за устаревших данных в кэше.
Уровень исходного кода
Помимо общих алгоритмов и их реализации на абстрактной машине, конкретные решения на уровне исходного кода могут существенно влиять на производительность. Например, в ранних компиляторах C цикл `while(1)` работал медленнее, чем `for(;;)` для безусловного повторения, поскольку `while(1)` вычислял значение 1, а затем выполнял условный переход, проверяющий истинность этого значения, в то время как `for(;;)` выполнял безусловный переход. Некоторые подобные оптимизации в настоящее время могут выполняться оптимизирующими компиляторами. Это зависит от исходного языка программирования, машинного кода целевой платформы и используемого компилятора, и может быть сложно понять, предсказать и со временем меняться; это ключевая область, где понимание принципов работы компиляторов и машинного кода может помочь повысить производительность. Вынесение инвариантного кода из цикла и оптимизация возвращаемых значений – примеры оптимизаций, которые уменьшают потребность во вспомогательных переменных и даже могут привести к увеличению скорости работы, избегая избыточных оптимизаций.
Уровень стройки
Между уровнем исходного кода и компиляцией директивы и флаги сборки могут быть использованы для оптимизации параметров производительности как в исходном коде, так и в компиляторе. Например, можно использовать определения препроцессора для отключения неиспользуемых функций программного обеспечения, оптимизировать код для конкретных моделей процессоров или аппаратных возможностей, или включить предсказание ветвлений. Системы распространения программного обеспечения, основанные на исходном коде, такие как Ports в BSD и Portage в Gentoo, могут использовать этот вид оптимизации.
Уровень компиляции
Использование оптимизирующего компилятора обычно обеспечивает оптимизацию исполняемой программы как минимум настолько, насколько это возможно предсказать компилятору.
Уровень сборки
На самом низком уровне, написание кода на языке ассемблера, разработанного для конкретной аппаратной платформы, может привести к созданию наиболее эффективного и компактного кода, если программист использует весь набор машинных инструкций. Многие операционные системы, используемые во встраиваемых системах, традиционно писались на ассемблере по этой причине. Программы (за исключением очень небольших) редко пишутся с нуля до конца на ассемблере из-за затрат времени и средств. Большинство из них компилируются из языка высокого уровня в ассемблер, а затем подвергаются ручной оптимизации. Если эффективность и размер не имеют большого значения, значительные части кода могут быть написаны на языке высокого уровня. С появлением более современных оптимизирующих компиляторов и возросшей сложностью современных процессоров, написать более эффективный код, чем тот, который генерирует компилятор, становится сложнее, и лишь немногим проектам требуется этот "предельный" этап оптимизации. Большая часть кода, написанного сегодня, предназначена для работы на максимально возможном количестве машин. Следовательно, программисты и компиляторы не всегда используют более эффективные инструкции, предоставляемые новыми процессорами, или особенности старых моделей. Кроме того, код на ассемблере, оптимизированный для конкретного процессора без использования этих инструкций, может оказаться неоптимальным на другом процессоре, требующем другой настройки. В настоящее время, вместо написания кода на языке ассемблера, программисты чаще используют дизассемблер для анализа выходных данных компилятора и изменения исходного кода высокого уровня, чтобы повысить эффективность компиляции или понять причины неэффективности.
Время исполнения
Компиляторы JIT (Just In Time) могут генерировать специализированный машинный код на основе данных времени выполнения, но это требует накладных расходов на компиляцию. Эта техника берет свое начало из первых движков регулярных выражений и получила широкое распространение с появлением Java HotSpot и V8 для JavaScript. В некоторых случаях адаптивная оптимизация способна выполнять оптимизацию во время выполнения, превосходящую возможности статических компиляторов, динамически настраивая параметры в зависимости от фактических входных данных или других факторов. Оптимизация на основе профиля – это техника оптимизации компиляции, основанная на профилях времени выполнения, и она аналогична статическому "среднему случаю" динамической технике адаптивной оптимизации. Самомодифицирующийся код может изменять себя в ответ на условия времени выполнения для оптимизации кода; это было более распространено в программах, написанных на языке ассемблера. Некоторые архитектуры процессоров способны выполнять определенные оптимизации во время выполнения, например, внеочередное исполнение, спекулятивное исполнение, конвейерная обработка инструкций и предсказание переходов. Компиляторы могут помочь программе использовать эти возможности процессора, например, посредством планирования инструкций.
Оптимизация, зависящая от платформы, и независимая оптимизация
Оптимизация кода также может быть широко классифицирована на методы, зависящие от платформы, и независимые от платформы. В то время как последние эффективны на большинстве или всех платформах, методы, зависящие от платформы, используют специфические особенности конкретной платформы или полагаются на параметры, зависящие от одной платформы или даже от отдельного процессора. В связи с этим может потребоваться создание различных версий одного и того же кода для разных процессоров. Например, при оптимизации на уровне компиляции, независимые от платформы методы представляют собой общие приемы (такие как развертывание циклов, сокращение количества вызовов функций, эффективные по использованию памяти подпрограммы, упрощение условий и т. д.), которые оказывают схожее влияние на большинство архитектур процессоров. Ярким примером независимой от платформы оптимизации служит анализ вложенных циклов for, где было установлено, что цикл с вложенным циклом for выполняет больше вычислений за единицу времени, чем цикл без него или с вложенным циклом while. Как правило, эти методы направлены на сокращение общей длины последовательности инструкций, необходимой для завершения программы, и/или на уменьшение общего объема используемой памяти в процессе выполнения. С другой стороны, методы, зависящие от платформы, включают планирование инструкций, параллелизм на уровне инструкций, параллелизм на уровне данных, методы оптимизации кэша (то есть параметры, различающиеся на разных платформах), а оптимальное планирование инструкций может отличаться даже на разных процессорах одной и той же архитектуры.
Компромиссы
В некоторых случаях, однако, оптимизация опирается на использование более сложных алгоритмов, использующих "особые случаи" и специальные "приемы", а также требующих сложных компромиссов. "Полностью оптимизированная" программа может быть сложнее для понимания и, следовательно, содержать больше ошибок, чем неоптимизированные версии. Помимо устранения очевидных антипаттернов, некоторые оптимизации на уровне кода снижают поддерживаемость. Оптимизация обычно фокусируется на улучшении одного или двух аспектов производительности: времени выполнения, использования памяти, дискового пространства, пропускной способности, энергопотребления или других ресурсов. Это, как правило, требует компромисса, когда один фактор оптимизируется в ущерб другим. Например, увеличение размера кэша повышает производительность, но также увеличивает потребление памяти. Другие распространенные компромиссы включают ясность и краткость кода. Бывают ситуации, когда программист, выполняющий оптимизацию, должен решить улучшить программное обеспечение для определенных операций, но за счет снижения эффективности других операций. Эти компромиссы иногда могут быть нетехническими, например, когда конкурент опубликовал результаты тестирования, которые необходимо превзойти для улучшения коммерческого успеха, но это может привести к снижению эффективности обычного использования программного обеспечения. Такие изменения иногда в шутку называют "пессимизациями".
Недостатки
Оптимизация может включать в себя поиск узкого места в системе — компонента, являющегося ограничивающим фактором производительности. С точки зрения кода, это часто будет «горячая точка» — критическая часть кода, которая является основным потребителем необходимого ресурса, хотя это может быть и другой фактор, такой как задержка ввода-вывода или пропускная способность сети. В информатике потребление ресурсов часто подчиняется распределению, близкому к степенному закону, и принцип Парето можно применить к оптимизации ресурсов, заметив, что 80% ресурсов обычно используется 20% операций. В разработке программного обеспечения часто более точно утверждать, что 90% времени выполнения компьютерной программы тратится на выполнение 10% кода (известное в этом контексте как правило 90/10). Более сложные алгоритмы и структуры данных хорошо работают с большим количеством элементов, в то время как простые алгоритмы больше подходят для небольших объемов данных — накладные расходы на настройку, время инициализации и постоянные факторы более сложного алгоритма могут нивелировать его преимущества, поэтому гибридный или адаптивный алгоритм может оказаться быстрее любого отдельного алгоритма. Профилировщик производительности может помочь сузить выбор, определяя, какая функциональность лучше всего подходит для каких условий. В некоторых случаях увеличение объема памяти может ускорить работу программы. Например, программа фильтрации обычно читает каждую строку, фильтрует её и сразу же выводит. Это требует памяти только для одной строки, но производительность обычно низкая из-за задержки при каждом чтении с диска. Кэширование результата также эффективно, хотя и требует большего объема памяти.
Время, затраченное на оптимизацию
Иногда время, затрачиваемое на саму оптимизацию, может стать проблемой. Оптимизация существующего кода обычно не добавляет новых функций, а что еще хуже, может внести новые ошибки в ранее работающий код (как и любое изменение). Поскольку код, оптимизированный вручную, иногда может быть менее "читаемым", чем неоптимизированный, оптимизация также может повлиять на его поддерживаемость. Оптимизация требует затрат, и важно убедиться, что инвестиции оправданы. Автоматический оптимизатор (или оптимизирующий компилятор – программа, выполняющая оптимизацию кода) сам может нуждаться в оптимизации, либо для дальнейшего повышения эффективности оптимизируемых программ, либо для ускорения собственной работы. Компиляция с включенной оптимизацией обычно занимает больше времени, хотя это обычно становится проблемой только для достаточно крупных программ. В частности, для JIT-компиляторов ключевым фактором повышения общей скорости выполнения является производительность компонента компиляции во время выполнения, работающего совместно со своим целевым кодом.