Преждевременная оптимизация может оказаться корнем всех зол, а запоздалая — корнем безысходности. Каким бы быстрым ни становилось аппаратное обеспечение, мы находим способы писать медленные программы. И зачастую проявляется это не сразу. Пользователи могут годами не обращать внимания на проблему в производительности ПО, пока она не становится очевидной, что порой происходит в течение одного дня.
Я бо́льшую часть своей жизни посвятил оптимизации, и за это время сделал два наблюдения:
Вряд ли вы удивитесь, узнав, что оба этих проявления оптимизма я считаю неуместными. Отчасти, потому что по мере всё большего усложнения аппаратного и программного обеспечения стало сложнее понимать их влияние на производительность. Но, возможно, на более фундаментальном уровне мы склонны переоценивать степень нашей осведомлённости в отношении собственных программ. Мы излишне акцентируемся на элементах ПО и частях системы, с которыми работаем лично, особенно на тех из них, с которыми имели дело недавно. При этом мы недооцениваем другие части системы, включая влияние зависимостей (например, библиотек).
Решение для первого из моих наблюдений широко известно — необходимо тщательно профилировать программу, прежде чем предполагать, какая её часть выполняется дольше всего. Я намеренно говорю «тщательно профилировать», потому что люди зачастую путают «Я профилировал свою программу один раз» с «Я построил хорошую модель производительности программы в различных ситуациях».
Порой быстрое профилирование оказывается вполне адекватным решением, но оно также может ввести в заблуждение. Зачастую необходимо профилировать программу при разных входных данных, иногда на разных машинах и с разными конфигурациями сети, используя различные подходы с выборкой и без [1].
А вот множество решений для второго наблюдения и их неизбежные компромиссы, на мой взгляд, недооцениваются. Я считаю, что среди них можно выделить четыре основных:
В оставшейся части статьи я разберу каждый из этих пунктов, описав связанные с ними компромиссы.
Давайте представим, хотя я лично видел такое в реальности, что после внимательного профилирования программы Python я выясняю, что бо́льшую часть времени она проводит в следующей функции:
def f1(l):
while True:
c = False
for i in range(0, len(l) - 1):
if l[i+1] < l:
t = l
l = l[i+1]
l[i+1] = t
c = True
if not c: return l
Это алгоритм сортировки «пузырьком». И здесь многие рассмеются, потому что для упорядочивания элементов эта техника явно будет медленной. Тем не менее у этой сортировки есть часто упускаемое из внимания преимущество перед «более быстрыми» алгоритмами: она выполняется в константной памяти [2]. Могу поспорить, что моя программа не нуждается в использовании этого вида памяти, но, если я не уверен, то есть вариант использовать альтернативный алгоритм, который сохранит это свойство. Попробуем сортировку методом выбора:
def f2(l):
for i in range(0, len(l) - 1):
m = i
for j in range(i + 1, len(l)):
if l[j] < l[m]: m = j
if m != i:
t = l
l = l[m]
l[m] = t
return l
Если я возьму этот быстрый проверочный код:
import random, time
l = [random.random() for _ in range(1000)]
before = time.time()
l1 = f1(l[:])
print(time.time() - before)
before = time.time()
l2 = f2(l[:])
print(time.time() - before)
И выполню его с помощью CPython 3.11 на сервере Linux, то буду последовательно получать следующие тайминги:
0.0643463134765625
0.020025014877319336
Иными словами, в моём тесте сортировка выбором примерно втрое быстрее сортировки «пузырьком». Уверен, вы понимаете, что сортировка методом выбора не является самым быстрым алгоритмом, но понятие «самый быстрый» может оказаться не столь однозначным. Например, приведённый выше алгоритм сортировки выбором быстрее сортировки «пузырьком» для случайных данных, но с упорядоченными данными последний справится намного эффективнее [3].
Связь между входными данными и производительностью алгоритма может быть очень тонкой. Как известно, если при реализации быстрой сортировки вы выберете неудачный «центральный элемент», то получите совсем небыстрое решение (например, оно может оказаться таким же медленным для уже упорядоченных данных, как сортировка выбором выше).
На основе этого можно сделать вывод, что «использование более эффективного алгоритма» требует широкого понимания контекста системы и природы самого предполагаемого алгоритма. Например, я часто вижу, как специалисты сводят воедино производительность лучшего, среднего и худшего случая выполнения алгоритма — но разница между этими случаями при оптимизации программы может оказаться критической.
Иногда я могу знать о программе нечто (например, природу её входных данных), указывающее на то, что худший случай невозможен, или же не рассматривать такой случай как возможную проблему (например, это пакетная задача, и никто не заметит её редкой задержки). Но обычно худший случай меня волнует больше, чем лучший, и алгоритмы я выбираю соответственно.
Также нередко бывает, что алгоритмы, которые в теории имеют высокую производительность, в реальности выполняются медленно (нотация О большое может скрывать множество грехов). Если есть сомнения, я постепенно увеличиваю объём тестируемых данных, пока не почувствую, что действительно понял практические последствия различных решений.
Также можно легко недооценить сложность. По своей сути более быстрые алгоритмы работают эффективнее, потому что обнаруживают возможность пропустить некоторые этапы вычисления. Я до сих пор помню тот момент, когда впервые прочёл описание алгоритма timsort. С тех пор в моём сознании запечатлелась красота его алгоритмической наблюдательности. Но определять такие наблюдения сложнее, чем мы думаем — даже timsort, созданный одним из величайших программистов, с какими я встречался, имеет тонкие недоработки [4].
Когда мы, простые смертные, реализуем более быстрые алгоритмы, они зачастую оказываются чуточку неверными, особенно при первой реализации, и либо дают ошибочные результаты, либо не соответствуют ожидаемым характеристикам производительности [5]. Например, распараллеливание алгоритма зачастую ведёт к значительному ускорению, особенно в свете увеличивающегося числа ядер процессора. Но многие ли из нас понимают модель памяти C11 достаточно хорошо, чтобы уверенно осознавать последствия этого шага?
Именно из-за этой комбинации некоторой (не)верности алгоритма и сложности с пониманием контекста, в котором он работает быстро, я часто рекомендую начинать с простого алгоритма и лишь затем при необходимости переходить к более быстрым вариантам. Умение выбрать (и, возможно, реализовать) алгоритм, наиболее подходящий под стоящую задачу, оказывается на удивление сложным навыком.
Представим, что я профилирую ещё одну программу и обнаруживаю, что бо́льшую часть времени она проводит в следующей функции:
def f3(l, e):
for x in l:
if x == e: return True
return False
Это функция проверки существования. Оптимизация таких функций порой становится очень интересной задачей, поскольку мои выборы определяются тем, как используются списки, передаваемые этой функции. Я мог бы изменить список, к примеру, на двоичное дерево. Но, если я понимаю, что раз за разом выполняю проверку существования элементов в списке, который после создания никогда не изменяется, то могу обойтись и очень простой структурой данных: упорядоченным списком.
Это может прозвучать странно, поскольку «упорядоченный список» не особо вписывается в понятие структуры данных, но он позволит мне выполнить двоичный поиск. Двоичный поиск окажется быстрее описанного выше линейного поиска для любых списков, кроме самых крохотных [6].
Как и в случае «использования более эффективного алгоритма», «использование более эффективной структуры данных» требует внимательного обдумывания и измерений [7]. И несмотря на то, что чаще мне приходится самостоятельно реализовывать «лучшие алгоритмы», я редко вижу потребность в создании собственной «лучшей структуры данных». Отчасти дело в лени, но основная причина в том, что структуры данных проще упаковывать в библиотеку, чем более эффективные алгоритмы [8].
Есть хороший приём в отношении «более эффективных структур данных», который образно можно описать как «посадите ваши структуры/классы на диету». Если программа выделяет много определённых структур/классов, то их размер в байтах может составить значительные траты. Когда я работал над восстановлением после ошибок в grmtools, то выяснил, что простое уменьшение наиболее часто выделяемой структуры на 8 байт ускорило программу на 5%. И этот приём мне удалось применить дважды.
Есть немало аналогичных техник, например, уменьшение «гонки за указателями» (как правило, за счёт свёртывания нескольких структур/классов в один), локальное использование памяти и так далее. Тем не менее несмотря на то, что измерить размер структуры/класса и частоту их выделения несложно, есть сложности с измерением косвенного влияния таких вещей, как локальность размещения данных. Я чаще слышал, как подобными факторами объясняли низкую производительность, нежели видел подтверждение этому. Обычно я рассматриваю их только в крайних случаях.
Переписывание программы на более низкоуровневом языке является традиционным решением. Давайте и мы перепишем нашу реализованную на Python сортировку «пузырьком» на Rust:
use std::cmp:
artialOrd;
fn f1<T: Copy + PartialOrd>(l: &mut Vec<T>) {
loop {
let mut c = false;
for i in 0..l.len() - 1 {
if l[i + 1] < l {
let t = l;
l = l[i + 1];
l[i + 1] = t;
c = true;
}
}
if !c {
return;
}
}
}
Я слегка адаптировал свою программу Python, чтобы сохранить 1000 случайных чисел с плавающей запятой, и добавил этот проверочный код на Rust:
use {env::args, fs::read_to_string, time::Instant};
fn main() {
let mut l = read_to_string(args().nth(1).unwrap())
.unwrap()
.lines()
.map(|x| x.parse:).unwrap())
.collect::>();
let before = Instant::now();
f1(&mut l);
println!("{}", (Instant::now() - before).as_secs_f64());
}
Версия моей сортировки «пузырьком» на Rust выполняется за 0,001 с, то есть примерно в 60 раз быстрее версии на Python. Это похоже на огромный успех для «переписывания на более низкоуровневом языке» — но, как вы заметили, раздел я назвал «Использование более низкоуровневой системы».
Вместо того, чтобы тратить 15 минут на написание кода Rust, было бы более грамотным заметить, что моя сортировка «пузырьком» на Python подчёркивает слабости CPython (наиболее распространённой реализации Python). В частности, CPython представляет то, что для меня является списком чисел с плавающей запятой, в виде массива указателей для отдельно выделяемых в куче объектов Python. Такое представление способствует обобщённости, но не эффективности.
И хотя это часто забывают, CPython является не единственной реализацией Python. Среди её альтернатив можно назвать PyPy, которая представляет списки чисел с плавающей запятой столь же эффективно, как это делает Rust. Просто указав pypy вместо python, мы ускорим сортировку «пузырьком» в 4 раза!
Я могу внести несколько изменений, которые обеспечат значительный прирост производительности при минимальных усилиях. Это не говорит о том, что PyPy выполнит мою программу так же быстро, как Rust (она всё равно справится примерно в 15 раз медленнее), но результат может оказаться достаточно хорош, и именно это важно.
Я видел, как многие организации совершают ошибку, пытаясь решить проблемы с производительностью переписыванием ПО на более низкоуровневых языках, когда оказалось бы достаточно найти способ лишь немного его ускорить. В этих случаях зачастую есть много доступных решений, начиная с использования другой реализации языка и проверки, включена ли в компиляторе оптимизация [9], заканчивая применением более быстрых библиотек или баз данных.
Иногда переписывание на более низкоуровневом языке действительно оказывается правильным выходом, но редко это удаётся сделать быстро. В результате неизбежно возникает период нестабильности, пока баги не будут устранены из этой новой создаваемой версии.
Нередко перед нами возникает проблема, когда у нас есть n элементов чего-либо, и мы хотим понять оптимальное подмножество порядка этих элементов для нашей ситуации. Представим, что я реализовал компилятор и 30 отдельных проходов оптимизации. Я знаю, что некоторые из этих проходов будут более эффективны, если их выполнить после других проходов, но мне неизвестен наиболее эффективный порядок всех проходов.
Я мог бы написать программу для перечисления всех пермутаций этих 30 проходов, прогнать их через набор бенчмарков и выбрать самую быструю. Но, если этот набор бенчмарков будет выполняться за 1 секунду, то на оценку всех возможных комбинаций уйдёт примерно 282 лет, что куда больше текущего возраста нашей Вселенной.
Ясное дело, что так долго ждать я не могу, и у меня есть возможность проверить лишь подмножество всех пермутаций. В подобных ситуациях мне нужно принять тот факт, что я никогда не смогу узнать наверняка, какой был самый лучший вариант. Но я могу хотя бы найти более оптимальный, не опробуя их все.
Решить это можно разными способами, но большинство сводятся к локальному поиску. В этом случае мы определяем метрику (в нашем примере она будет отражать скорость выполнения набора бенчмарков), которая позволит сравнить два решения (в данном случае чем быстрее, тем лучше) и отбросить худшее. Затем нам потребуется способ сгенерировать соседнее решение для оставшегося, повторно вычислить метрику и снова отбросить худший вариант. В итоге либо по истечении установленного временно́го лимита, либо в случае невозможности найти решения, улучшающие показатели метрики, мы возвращаем лучший найденный вариант.
Эффективность этой простой техники (её основной алгоритм состоит из всего нескольких строк кода) может ошеломить новичков, поскольку очевидная проблема локального оптимума, казалось бы, должна подрывать саму её идею.
В своей типичной реализации локальный поиск, как я подчеркнул выше, выдаёт корректные, но не обязательно оптимальные решения. Хотя порой мы готовы принять ответ, который окажется менее точным в том смысле, что, возможно, является «некорректным». Под этим я имею в виду не то, что программа ошибочна, а то, что она может намеренно давать не на 100% «полноценный и правильный» результат.
Причём точное определение «корректности» будет отличаться от ситуации к ситуации. Например, алгоритм быстрого вычисления обратного корня аппроксимируется к мультипликативной инверсии: для таких случаев, как видеоигры, его быстрый, приближенный к верному ответ окажется более удачной альтернативой медленному, но точно верному варианту.
Фильтр Блума может давать ложные положительные результаты. Принятие этой вероятности позволяет добиться с его помощью исключительной экономии памяти. При сжатии изображений JPEG намеренно отбрасывается часть деталей с целью уменьшения их размера. В отличие от других подходов к сжатию изображений, из JPEG невозможно идеально восстановить исходную картинку, но немного поступившись качеством, мы получаем гораздо меньший размер файла для передачи.
Я думаю, что большинство программистов редко готовы принять то, что корректностью иногда можно пожертвовать — лично для меня это противоречит глубокой убеждённости в том, что программы должны быть в точности корректными. Возможно, по этой причине описанную технику используют реже, чем следовало бы.
Хотя с недавних пор, когда начало активно развиваться машинное обучение (МО), мы стали с гораздо большей лёгкостью принимать неточные ответы. В то время, как локальный поиск требует явного указания способа создания новых решений, модели МО обучаются на имеющихся данных, после чего генерируют решения на их основе. И эта техника может оказаться очень эффективной при том, что неизбежные «галлюцинации» таких моделей в действительности лишь представляют одну из форм некорректности.
Таким образом, в случае принятия неточных решений есть два варианта: мы принимаем, возможно, неоптимальный вариант или, возможно, некорректный. По моим наблюдениям многие считают, что это одно и то же, но возможная некорректность вызывает проблемы чаще. Я могу с радостью пожертвовать некоторой точностью изображения ради его уменьшения, но вряд ли обрадуюсь, если модель МО перепишет мой код и отбросит условие «not». Моё главное правило звучит так: «Если нет уверенности, что небольшая некорректность не помешает, то лучше считать, что помешает».
Я перечислил четыре подхода к оптимизации, упорядочив их в соответствии с отмеченной мной частотой использования.
Вас, пожалуй, не удивит, что для меня самым нелюбимым является подход с «переписыванием на более низкоуровневом языке» в том смысле, что он предполагает самое плохое соотношение между получаемым улучшением и затратами. Это не значит, что он всегда окажется ошибочным, но мы склонны прибегать к нему, прежде чем адекватно взвесим более простые альтернативы.
И напротив, я считаю, что до недавних пор мы слишком редко использовали вариант «принятия менее точного решения», хотя прорыв в сфере МО быстро изменил это. Лично я начинаю оптимизацию программ с рассмотрения самых простых решений. Многих удивляет то, насколько часто моей первой попыткой становится поиск подходящих мест для использования хэш-таблиц – я редко прибегаю к использованию неких экзотических структур данных. Ещё реже я прибегаю к заумным алгоритмам. Среди таких заумных алгоритмов, которые я склонен реализовывать сам, чаще всего мне пригождается двоичный поиск, причём не более двух раз в год. И при каждой его реализации мне приходится искать правильный подход [10].
Наконец, в процессе написания статьи я понял, что ко всем описанным техникам оптимизации можно отнести три общих правила.
Во-первых, когда корректностью можно пожертвовать в угоду производительности, такое решение окажется эффективным, но мы зачастую идём на эту жертву ненамеренно. Когда нам нужно оптимизировать программу, лучше всего использовать наименее сложную оптимизацию, которая обеспечит желаемое быстродействие, поскольку она наверняка внесёт меньше всего багов.
Во-вторых, важно учитывать затраченное время. Поскольку мы, будучи программистами, так любим сложность, нас слишком рано тянет использовать сложные оптимизации. И даже если они успешно повысят производительность — что происходит нечасто — это потребует намного больше времени, чем необходимо для получения желаемого прироста быстродействия.
В-третьих, я считаю, что широта понимания оптимизации важнее, чем его глубина. Для каждой из перечисленных техник у меня есть пара регулярно используемых приёмов. Это помогло мне выработать адекватную интуицию и понимать, какая техника окажется наиболее подходящей для решаемой задачи, даже если мне неизвестны её детали.
[1] Зачастую при первом анализе производительности мне достаточно примерного представления о том, что происходит. В процессе я постепенно сужаю спектр возможных деталей, которые нужно изучить более подробно. Обычно я начинаю со стандартного инструмента Linux time, затем перехожу, например, к multitime, потом к профилировщику, например perf и, наконец, использую более подробный профилировщик вроде Valgrind. Каждый очередной инструмент требует чуть больше времени на выполнение и трактовку результатов, в связи с чем я не начинаю, скажем, с Valgrind.
Сложнее понять, какие входные данные использовать. Всегда есть соблазн протестировать программу с одним вариантом входных данных, и нередко я на такой соблазн ведусь, хоть и знаю, что это ловушка.
[2] Иными словами: изменение размера или природы входных данных не влияет на количество используемой алгоритмом памяти.
[3] Формально говоря, для упорядоченных данных сортировка «пузырьком» выполняется за O, а сортировка методом выбора за O(n2). Это значительное отличие!
[4] История с timsort не заканчивается первой работой, в которой проводился его анализ. Продолжение можете почитать в этом обращении на сайте Python.
[5] Карл-Фридрих Больц указал на примеры, с которыми я сталкивался неоднократно, но никогда конкретно не классифицировал: действительно легко реализовать алгоритм так, что он случайно окажется квадратичным. Классический случай — это конкатенация строк в языках, где строки немутабельны — каждая операция с позиции быстродействия выглядит безобидной, но если вы возьмётесь генерировать большую строку, путём постепенного конкатенирования небольшой начальной строки, то получите неприятности. В этом блоге есть много примеров.
[6] По моему опыту, двоичный поиск становится быстрее линейного после примерно 8-12 элементов.
[7] По факту использование «более эффективных структур данных» обычно подразумевает использование где-то «более эффективного алгоритма».
[8] Например, я реализовывал поистине сложные алгоритмы, но никогда не писал балансировщики деревьев.
[9] Я не перестаю удивляться тому, как часто люди используют ПО, скомпилированное без оптимизаций.
[10] Метод Rust binary_search_by практически избавил меня от затруднений в выборе правильной средней точки.
habr.com
Я бо́льшую часть своей жизни посвятил оптимизации, и за это время сделал два наблюдения:
- Человеческий оптимизм заставляет нас верить, что мы можем запросто понять, какая часть программы выполняется дольше всего.
- Человеческий оптимизм заставляет нас верить, что мы без проблем поймём, как ускорить эти медленные участки программы.
Вряд ли вы удивитесь, узнав, что оба этих проявления оптимизма я считаю неуместными. Отчасти, потому что по мере всё большего усложнения аппаратного и программного обеспечения стало сложнее понимать их влияние на производительность. Но, возможно, на более фундаментальном уровне мы склонны переоценивать степень нашей осведомлённости в отношении собственных программ. Мы излишне акцентируемся на элементах ПО и частях системы, с которыми работаем лично, особенно на тех из них, с которыми имели дело недавно. При этом мы недооцениваем другие части системы, включая влияние зависимостей (например, библиотек).
Решение для первого из моих наблюдений широко известно — необходимо тщательно профилировать программу, прежде чем предполагать, какая её часть выполняется дольше всего. Я намеренно говорю «тщательно профилировать», потому что люди зачастую путают «Я профилировал свою программу один раз» с «Я построил хорошую модель производительности программы в различных ситуациях».
Порой быстрое профилирование оказывается вполне адекватным решением, но оно также может ввести в заблуждение. Зачастую необходимо профилировать программу при разных входных данных, иногда на разных машинах и с разными конфигурациями сети, используя различные подходы с выборкой и без [1].
А вот множество решений для второго наблюдения и их неизбежные компромиссы, на мой взгляд, недооцениваются. Я считаю, что среди них можно выделить четыре основных:
- Использовать более эффективный алгоритм.
- Использовать более эффективную структуру данных.
- Использовать более низкоуровневую систему.
- Принять менее точное решение.
В оставшейся части статьи я разберу каждый из этих пунктов, описав связанные с ними компромиссы.
▍ Использование более эффективного алгоритма
Давайте представим, хотя я лично видел такое в реальности, что после внимательного профилирования программы Python я выясняю, что бо́льшую часть времени она проводит в следующей функции:
def f1(l):
while True:
c = False
for i in range(0, len(l) - 1):
if l[i+1] < l:
t = l
l = l[i+1]
l[i+1] = t
c = True
if not c: return l
Это алгоритм сортировки «пузырьком». И здесь многие рассмеются, потому что для упорядочивания элементов эта техника явно будет медленной. Тем не менее у этой сортировки есть часто упускаемое из внимания преимущество перед «более быстрыми» алгоритмами: она выполняется в константной памяти [2]. Могу поспорить, что моя программа не нуждается в использовании этого вида памяти, но, если я не уверен, то есть вариант использовать альтернативный алгоритм, который сохранит это свойство. Попробуем сортировку методом выбора:
def f2(l):
for i in range(0, len(l) - 1):
m = i
for j in range(i + 1, len(l)):
if l[j] < l[m]: m = j
if m != i:
t = l
l = l[m]
l[m] = t
return l
Если я возьму этот быстрый проверочный код:
import random, time
l = [random.random() for _ in range(1000)]
before = time.time()
l1 = f1(l[:])
print(time.time() - before)
before = time.time()
l2 = f2(l[:])
print(time.time() - before)
И выполню его с помощью CPython 3.11 на сервере Linux, то буду последовательно получать следующие тайминги:
0.0643463134765625
0.020025014877319336
Иными словами, в моём тесте сортировка выбором примерно втрое быстрее сортировки «пузырьком». Уверен, вы понимаете, что сортировка методом выбора не является самым быстрым алгоритмом, но понятие «самый быстрый» может оказаться не столь однозначным. Например, приведённый выше алгоритм сортировки выбором быстрее сортировки «пузырьком» для случайных данных, но с упорядоченными данными последний справится намного эффективнее [3].
Связь между входными данными и производительностью алгоритма может быть очень тонкой. Как известно, если при реализации быстрой сортировки вы выберете неудачный «центральный элемент», то получите совсем небыстрое решение (например, оно может оказаться таким же медленным для уже упорядоченных данных, как сортировка выбором выше).
На основе этого можно сделать вывод, что «использование более эффективного алгоритма» требует широкого понимания контекста системы и природы самого предполагаемого алгоритма. Например, я часто вижу, как специалисты сводят воедино производительность лучшего, среднего и худшего случая выполнения алгоритма — но разница между этими случаями при оптимизации программы может оказаться критической.
Иногда я могу знать о программе нечто (например, природу её входных данных), указывающее на то, что худший случай невозможен, или же не рассматривать такой случай как возможную проблему (например, это пакетная задача, и никто не заметит её редкой задержки). Но обычно худший случай меня волнует больше, чем лучший, и алгоритмы я выбираю соответственно.
Также нередко бывает, что алгоритмы, которые в теории имеют высокую производительность, в реальности выполняются медленно (нотация О большое может скрывать множество грехов). Если есть сомнения, я постепенно увеличиваю объём тестируемых данных, пока не почувствую, что действительно понял практические последствия различных решений.
Также можно легко недооценить сложность. По своей сути более быстрые алгоритмы работают эффективнее, потому что обнаруживают возможность пропустить некоторые этапы вычисления. Я до сих пор помню тот момент, когда впервые прочёл описание алгоритма timsort. С тех пор в моём сознании запечатлелась красота его алгоритмической наблюдательности. Но определять такие наблюдения сложнее, чем мы думаем — даже timsort, созданный одним из величайших программистов, с какими я встречался, имеет тонкие недоработки [4].
Когда мы, простые смертные, реализуем более быстрые алгоритмы, они зачастую оказываются чуточку неверными, особенно при первой реализации, и либо дают ошибочные результаты, либо не соответствуют ожидаемым характеристикам производительности [5]. Например, распараллеливание алгоритма зачастую ведёт к значительному ускорению, особенно в свете увеличивающегося числа ядер процессора. Но многие ли из нас понимают модель памяти C11 достаточно хорошо, чтобы уверенно осознавать последствия этого шага?
Именно из-за этой комбинации некоторой (не)верности алгоритма и сложности с пониманием контекста, в котором он работает быстро, я часто рекомендую начинать с простого алгоритма и лишь затем при необходимости переходить к более быстрым вариантам. Умение выбрать (и, возможно, реализовать) алгоритм, наиболее подходящий под стоящую задачу, оказывается на удивление сложным навыком.
▍ Использование более эффективной структуры данных
Представим, что я профилирую ещё одну программу и обнаруживаю, что бо́льшую часть времени она проводит в следующей функции:
def f3(l, e):
for x in l:
if x == e: return True
return False
Это функция проверки существования. Оптимизация таких функций порой становится очень интересной задачей, поскольку мои выборы определяются тем, как используются списки, передаваемые этой функции. Я мог бы изменить список, к примеру, на двоичное дерево. Но, если я понимаю, что раз за разом выполняю проверку существования элементов в списке, который после создания никогда не изменяется, то могу обойтись и очень простой структурой данных: упорядоченным списком.
Это может прозвучать странно, поскольку «упорядоченный список» не особо вписывается в понятие структуры данных, но он позволит мне выполнить двоичный поиск. Двоичный поиск окажется быстрее описанного выше линейного поиска для любых списков, кроме самых крохотных [6].
Как и в случае «использования более эффективного алгоритма», «использование более эффективной структуры данных» требует внимательного обдумывания и измерений [7]. И несмотря на то, что чаще мне приходится самостоятельно реализовывать «лучшие алгоритмы», я редко вижу потребность в создании собственной «лучшей структуры данных». Отчасти дело в лени, но основная причина в том, что структуры данных проще упаковывать в библиотеку, чем более эффективные алгоритмы [8].
Есть хороший приём в отношении «более эффективных структур данных», который образно можно описать как «посадите ваши структуры/классы на диету». Если программа выделяет много определённых структур/классов, то их размер в байтах может составить значительные траты. Когда я работал над восстановлением после ошибок в grmtools, то выяснил, что простое уменьшение наиболее часто выделяемой структуры на 8 байт ускорило программу на 5%. И этот приём мне удалось применить дважды.
Есть немало аналогичных техник, например, уменьшение «гонки за указателями» (как правило, за счёт свёртывания нескольких структур/классов в один), локальное использование памяти и так далее. Тем не менее несмотря на то, что измерить размер структуры/класса и частоту их выделения несложно, есть сложности с измерением косвенного влияния таких вещей, как локальность размещения данных. Я чаще слышал, как подобными факторами объясняли низкую производительность, нежели видел подтверждение этому. Обычно я рассматриваю их только в крайних случаях.
▍ Использование более низкоуровневой системы
Переписывание программы на более низкоуровневом языке является традиционным решением. Давайте и мы перепишем нашу реализованную на Python сортировку «пузырьком» на Rust:
use std::cmp:
artialOrd;fn f1<T: Copy + PartialOrd>(l: &mut Vec<T>) {
loop {
let mut c = false;
for i in 0..l.len() - 1 {
if l[i + 1] < l {
let t = l;
l = l[i + 1];
l[i + 1] = t;
c = true;
}
}
if !c {
return;
}
}
}
Я слегка адаптировал свою программу Python, чтобы сохранить 1000 случайных чисел с плавающей запятой, и добавил этот проверочный код на Rust:
use {env::args, fs::read_to_string, time::Instant};
fn main() {
let mut l = read_to_string(args().nth(1).unwrap())
.unwrap()
.lines()
.map(|x| x.parse:
).unwrap()).collect::>();
let before = Instant::now();
f1(&mut l);
println!("{}", (Instant::now() - before).as_secs_f64());
}
Версия моей сортировки «пузырьком» на Rust выполняется за 0,001 с, то есть примерно в 60 раз быстрее версии на Python. Это похоже на огромный успех для «переписывания на более низкоуровневом языке» — но, как вы заметили, раздел я назвал «Использование более низкоуровневой системы».
Вместо того, чтобы тратить 15 минут на написание кода Rust, было бы более грамотным заметить, что моя сортировка «пузырьком» на Python подчёркивает слабости CPython (наиболее распространённой реализации Python). В частности, CPython представляет то, что для меня является списком чисел с плавающей запятой, в виде массива указателей для отдельно выделяемых в куче объектов Python. Такое представление способствует обобщённости, но не эффективности.
И хотя это часто забывают, CPython является не единственной реализацией Python. Среди её альтернатив можно назвать PyPy, которая представляет списки чисел с плавающей запятой столь же эффективно, как это делает Rust. Просто указав pypy вместо python, мы ускорим сортировку «пузырьком» в 4 раза!
Я могу внести несколько изменений, которые обеспечат значительный прирост производительности при минимальных усилиях. Это не говорит о том, что PyPy выполнит мою программу так же быстро, как Rust (она всё равно справится примерно в 15 раз медленнее), но результат может оказаться достаточно хорош, и именно это важно.
Я видел, как многие организации совершают ошибку, пытаясь решить проблемы с производительностью переписыванием ПО на более низкоуровневых языках, когда оказалось бы достаточно найти способ лишь немного его ускорить. В этих случаях зачастую есть много доступных решений, начиная с использования другой реализации языка и проверки, включена ли в компиляторе оптимизация [9], заканчивая применением более быстрых библиотек или баз данных.
Иногда переписывание на более низкоуровневом языке действительно оказывается правильным выходом, но редко это удаётся сделать быстро. В результате неизбежно возникает период нестабильности, пока баги не будут устранены из этой новой создаваемой версии.
▍ Принятие менее точного решения
Нередко перед нами возникает проблема, когда у нас есть n элементов чего-либо, и мы хотим понять оптимальное подмножество порядка этих элементов для нашей ситуации. Представим, что я реализовал компилятор и 30 отдельных проходов оптимизации. Я знаю, что некоторые из этих проходов будут более эффективны, если их выполнить после других проходов, но мне неизвестен наиболее эффективный порядок всех проходов.
Я мог бы написать программу для перечисления всех пермутаций этих 30 проходов, прогнать их через набор бенчмарков и выбрать самую быструю. Но, если этот набор бенчмарков будет выполняться за 1 секунду, то на оценку всех возможных комбинаций уйдёт примерно 282 лет, что куда больше текущего возраста нашей Вселенной.
Ясное дело, что так долго ждать я не могу, и у меня есть возможность проверить лишь подмножество всех пермутаций. В подобных ситуациях мне нужно принять тот факт, что я никогда не смогу узнать наверняка, какой был самый лучший вариант. Но я могу хотя бы найти более оптимальный, не опробуя их все.
Решить это можно разными способами, но большинство сводятся к локальному поиску. В этом случае мы определяем метрику (в нашем примере она будет отражать скорость выполнения набора бенчмарков), которая позволит сравнить два решения (в данном случае чем быстрее, тем лучше) и отбросить худшее. Затем нам потребуется способ сгенерировать соседнее решение для оставшегося, повторно вычислить метрику и снова отбросить худший вариант. В итоге либо по истечении установленного временно́го лимита, либо в случае невозможности найти решения, улучшающие показатели метрики, мы возвращаем лучший найденный вариант.
Эффективность этой простой техники (её основной алгоритм состоит из всего нескольких строк кода) может ошеломить новичков, поскольку очевидная проблема локального оптимума, казалось бы, должна подрывать саму её идею.
В своей типичной реализации локальный поиск, как я подчеркнул выше, выдаёт корректные, но не обязательно оптимальные решения. Хотя порой мы готовы принять ответ, который окажется менее точным в том смысле, что, возможно, является «некорректным». Под этим я имею в виду не то, что программа ошибочна, а то, что она может намеренно давать не на 100% «полноценный и правильный» результат.
Причём точное определение «корректности» будет отличаться от ситуации к ситуации. Например, алгоритм быстрого вычисления обратного корня аппроксимируется к мультипликативной инверсии: для таких случаев, как видеоигры, его быстрый, приближенный к верному ответ окажется более удачной альтернативой медленному, но точно верному варианту.
Фильтр Блума может давать ложные положительные результаты. Принятие этой вероятности позволяет добиться с его помощью исключительной экономии памяти. При сжатии изображений JPEG намеренно отбрасывается часть деталей с целью уменьшения их размера. В отличие от других подходов к сжатию изображений, из JPEG невозможно идеально восстановить исходную картинку, но немного поступившись качеством, мы получаем гораздо меньший размер файла для передачи.
Я думаю, что большинство программистов редко готовы принять то, что корректностью иногда можно пожертвовать — лично для меня это противоречит глубокой убеждённости в том, что программы должны быть в точности корректными. Возможно, по этой причине описанную технику используют реже, чем следовало бы.
Хотя с недавних пор, когда начало активно развиваться машинное обучение (МО), мы стали с гораздо большей лёгкостью принимать неточные ответы. В то время, как локальный поиск требует явного указания способа создания новых решений, модели МО обучаются на имеющихся данных, после чего генерируют решения на их основе. И эта техника может оказаться очень эффективной при том, что неизбежные «галлюцинации» таких моделей в действительности лишь представляют одну из форм некорректности.
Таким образом, в случае принятия неточных решений есть два варианта: мы принимаем, возможно, неоптимальный вариант или, возможно, некорректный. По моим наблюдениям многие считают, что это одно и то же, но возможная некорректность вызывает проблемы чаще. Я могу с радостью пожертвовать некоторой точностью изображения ради его уменьшения, но вряд ли обрадуюсь, если модель МО перепишет мой код и отбросит условие «not». Моё главное правило звучит так: «Если нет уверенности, что небольшая некорректность не помешает, то лучше считать, что помешает».
▍ Обобщение
Я перечислил четыре подхода к оптимизации, упорядочив их в соответствии с отмеченной мной частотой использования.
Вас, пожалуй, не удивит, что для меня самым нелюбимым является подход с «переписыванием на более низкоуровневом языке» в том смысле, что он предполагает самое плохое соотношение между получаемым улучшением и затратами. Это не значит, что он всегда окажется ошибочным, но мы склонны прибегать к нему, прежде чем адекватно взвесим более простые альтернативы.
И напротив, я считаю, что до недавних пор мы слишком редко использовали вариант «принятия менее точного решения», хотя прорыв в сфере МО быстро изменил это. Лично я начинаю оптимизацию программ с рассмотрения самых простых решений. Многих удивляет то, насколько часто моей первой попыткой становится поиск подходящих мест для использования хэш-таблиц – я редко прибегаю к использованию неких экзотических структур данных. Ещё реже я прибегаю к заумным алгоритмам. Среди таких заумных алгоритмов, которые я склонен реализовывать сам, чаще всего мне пригождается двоичный поиск, причём не более двух раз в год. И при каждой его реализации мне приходится искать правильный подход [10].
Наконец, в процессе написания статьи я понял, что ко всем описанным техникам оптимизации можно отнести три общих правила.
Во-первых, когда корректностью можно пожертвовать в угоду производительности, такое решение окажется эффективным, но мы зачастую идём на эту жертву ненамеренно. Когда нам нужно оптимизировать программу, лучше всего использовать наименее сложную оптимизацию, которая обеспечит желаемое быстродействие, поскольку она наверняка внесёт меньше всего багов.
Во-вторых, важно учитывать затраченное время. Поскольку мы, будучи программистами, так любим сложность, нас слишком рано тянет использовать сложные оптимизации. И даже если они успешно повысят производительность — что происходит нечасто — это потребует намного больше времени, чем необходимо для получения желаемого прироста быстродействия.
В-третьих, я считаю, что широта понимания оптимизации важнее, чем его глубина. Для каждой из перечисленных техник у меня есть пара регулярно используемых приёмов. Это помогло мне выработать адекватную интуицию и понимать, какая техника окажется наиболее подходящей для решаемой задачи, даже если мне неизвестны её детали.
▍ Сноски
[1] Зачастую при первом анализе производительности мне достаточно примерного представления о том, что происходит. В процессе я постепенно сужаю спектр возможных деталей, которые нужно изучить более подробно. Обычно я начинаю со стандартного инструмента Linux time, затем перехожу, например, к multitime, потом к профилировщику, например perf и, наконец, использую более подробный профилировщик вроде Valgrind. Каждый очередной инструмент требует чуть больше времени на выполнение и трактовку результатов, в связи с чем я не начинаю, скажем, с Valgrind.
Сложнее понять, какие входные данные использовать. Всегда есть соблазн протестировать программу с одним вариантом входных данных, и нередко я на такой соблазн ведусь, хоть и знаю, что это ловушка.
[2] Иными словами: изменение размера или природы входных данных не влияет на количество используемой алгоритмом памяти.
[3] Формально говоря, для упорядоченных данных сортировка «пузырьком» выполняется за O
, а сортировка методом выбора за O(n2). Это значительное отличие![4] История с timsort не заканчивается первой работой, в которой проводился его анализ. Продолжение можете почитать в этом обращении на сайте Python.
[5] Карл-Фридрих Больц указал на примеры, с которыми я сталкивался неоднократно, но никогда конкретно не классифицировал: действительно легко реализовать алгоритм так, что он случайно окажется квадратичным. Классический случай — это конкатенация строк в языках, где строки немутабельны — каждая операция с позиции быстродействия выглядит безобидной, но если вы возьмётесь генерировать большую строку, путём постепенного конкатенирования небольшой начальной строки, то получите неприятности. В этом блоге есть много примеров.
[6] По моему опыту, двоичный поиск становится быстрее линейного после примерно 8-12 элементов.
[7] По факту использование «более эффективных структур данных» обычно подразумевает использование где-то «более эффективного алгоритма».
[8] Например, я реализовывал поистине сложные алгоритмы, но никогда не писал балансировщики деревьев.
[9] Я не перестаю удивляться тому, как часто люди используют ПО, скомпилированное без оптимизаций.
[10] Метод Rust binary_search_by практически избавил меня от затруднений в выборе правильной средней точки.
Четыре способа оптимизации ПО
Преждевременная оптимизация может оказаться корнем всех зол, а запоздалая — корнем безысходности. Каким бы быстрым ни становилось аппаратное обеспечение, мы находим способы писать медленные...
habr.com