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

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

Сочетаемость

Определённые оптимизации могут работать лишь совместно друг с другом, а некоторые, если их скомбинировать, не улучшают производительность, а ухудшают. Быть экспертом в этой сфере — значит знать о существующих способах оптимизации. А «мастер оптимизации» — этот тот, кто знает о том, что именно выбрать.

Я сейчас работаю над статьёй о форматировании целочисленных значений, в которой речь идёт о том, как устроен один весьма специфический алгоритм. Я до сих пор эту статью не дописала, так как мне нужно принять что-то около пяти решений, связанных с алгоритмом. При этом я не знаю о том, как они повлияют друг на друга, и мне нужно проанализировать 2⁵ вариантов, чтобы с уверенностью сказать, какой из них самый лучший. Несколько моих проектов «забуксовали» по той же причине — мне не хватает силы воли на то, чтобы реализовать дюжину комбинаций вариантов кода.

Отсечь «очевидно» неоптимальные подходы — это практически чистая эвристика. Меня греет мысль о том, что я лучше других ориентируюсь в процессорах архитектуры x86-64, но и эти процессоры, время от времени, умудряются преподносить мне сюрпризы. Примитивный алгоритм может оказаться полезнее, чем ожидалось, из-за векторизации. А искусно написанный код может дать сбой из-за неудачного предсказания переходов (branch misprediction) или из-за того, что произошла ошибка в механизме store-to-load forwarding, ускоряющем операции чтения данных, выполняемые после операций их записи.

Оптимизация требует многократного применения метода проб и ошибок. Мне не нравится, когда говорят, что «интуиция тут не поможет — профилируйте код», так как эта фраза, вроде бы, указывает на то, что профилирование — это жизнеспособная замена теоретических вычислений, хотя на самом деле это не так. Но я не могу сказать, что без профилирования можно обойтись. Я часто шучу о том, что perf report — это мой «дежурный» дизассемблер.

Но ещё хуже то, что совершенно нельзя доверять и «очевидно» хорошему коду. В предыдущей статье я оптимизировала код, заменив однопроходной линейный алгоритм на алгоритм, сложность которого выше линейной. Это — совсем не уникальный случай. Буквально вчера я видела, как кто-то оптимизировал лучший в своём классе алгоритм Барретта, деля числа как значения типа double, округляя то, что получилось, и вычисляя остаток от деления на основе результата деления. Выглядит это глупостью, которая, скорее всего, нигде и не пригодится. А оно пригодилось.

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

Работая над своими проектами, попробуйте воспользоваться тем, что уже сделано до вас. А именно — можете поговорить с коллегами или почитать о том, как другие решали похожие задачи.

Непротиворечивость

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

• Гибридные алгоритмы сортировки способны переключаться между различными реализациями из-за высоких постоянных величин «большое О».

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

• При работе с данными разной плотности оптимальными могут оказаться множества с разной структурой. Это может быть битовое множество, хеш-множество, или комплементарное хеш-множество.

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

А вот — ещё пример. Представьте себе программу, которая n раз выполняет либо действие A, либо действие B, что зависит от вероятности p. Если p сильно отличается от 1/2 — особенности работы предсказания переходов говорят о том, что лучше реализовать выбор варианта с помощью if. Если p близко к 1/2 — предсказание переходов будет работать плохо, и лучше подойдёт подход, где ветвление не используется. Здесь играет роль не только сравнительная производительность A и B, но и «стоимость» неправильного предсказания переходов, а она может зависеть не только от самого CPU, но и от того, какой именно код на нём выполняется.

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

Несовместимость

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

Скажем, такое происходит, когда две таблицы поиска (LUT) вместе не помещаются в кеше, хотя по одной — помещаются. Иногда подобное можно исправить, разделив вычисления на несколько проходов, где при выполнении каждого из проходов нужно обращаться лишь к вспомогательным данным, которые помещаются в кеш. Это не обязательно означает выполнение двух проходов по всем данным с созданием удвоенной нагрузки на пропускную способность памяти. Данные можно разбить на фрагменты и выполнить два прохода над одним из фрагментов, что повысит производительность в том случае, если, например, фрагмент поместиться в L3-кеш. Но иногда этот подход неприменим, и тогда я буквально бьюсь головой о стену.

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

Всё не должно быть именно так. Программируемые пользователем вентильные матрицы (FPGA) позволяют проектировать собственное аппаратное обеспечение (ну — нечто вроде того). Альтернативные подходы, вроде сетей взаимодействия (interaction net), дают шанс сделать операции, определённые программно, такими же эффективными, как операции, обычно реализуемые в «железе». Но это не похоже на тот мир, в котором мы живём, где Intel регулярно добавляет полезные инструкции в AVX-512, а потом их забрасывает. Поэтому мне приходится выбирать между процессорами, которые поддерживают vp2intersect или FP16. В результате нужно не только тестировать производительность разного кода — нужно ещё и испытывать его на разных CPU для того чтобы решить, на каком инстансе EC2 его развернуть.

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

Компиляторы

Многие привыкли думать, что «компиляторы умнее людей». Но вряд ли что-то может быть дальше от истины, чем эта идея. Любой разработчик способен понять, что два следующих примера (как ожидается) эквивалентны:

let condition1 = HashSet::from([a, b]).contains(&c);
let condition2 = a == c || b == c;

Но компиляторы не собираются оптимизировать первый пример так, чтобы свести его ко второму (JVM JIT, в некоторых случаях, это не касается). Они не рассуждают, прибегая к абстракциям, и, определённо — они не обращают внимание на ваши собственные абстракции. Это относится не только к высокоуровневому коду: LLVM даже не понимает, что побитовый оператор И (AND) — это пересечение.

Задача, в которой компиляторы раскрываются во всей красе — это не оптимизация. Они превращают код, написанный на языках высокого уровня, в абстракции, обработка которых не требует дополнительных затрат вычислительных ресурсов. Но они не отличаются ни находчивостью, ни остроумием. Компиляторы — это оптимальные транспиляторы. Они, за редкими исключениями, генерируют именно тот код, который написан программистом в исходниках. Они позволяют писать на ассемблере, используя синтаксис и возможности Rust или C++. Но не вздумайте забыть о том, что написанная вами конструкция arr.map(|x| x / c) вызовет idiv, не выполняя очевидных предварительных расчётов в духе libdivide.

Иногда я думаю о том, что флаг -O2, возможно, надо переименовать в -fzero-cost-abstractions.

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

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

Несмотря на то, что компиляторы обладают очевидными недостатками, они не позволяют нам поправлять их там, где они ошибаются. Нет способа дать компилятору и оптимизированный код на ассемблере, и эквивалентный ему код на C, и сделать так, чтобы компилятор использовал бы первый при обычной работе, а второй — в особых случаях. Пользовательские соглашения о вызовах, по большей части, не поддерживаются, равно как и выбор между кодом с переходами и без них, а так же — многие другие ассемблерные трюки. Существует такое явление, как низкоуровневые встроенные функции (intrinsics), но LLVM и rustc, работая с ними, пытаются показать свою интеллектуальность, и их переписывают. Это иногда ведёт к падению производительности, в результате не остаётся ничего, кроме применения барьера оптимизации.

Эквивалентные графы (e-graphs), в том виде, в котором они популяризованы Cranelift, пытаются решить эту проблему, но, насколько я знаю, пока в этой сфере особых успехов не наблюдается. Я, правда, всё ещё надеюсь на лучшее.

Документация

Сайт uops.info предоставляет данные о времени выполнения и о портах для каждой инструкции процессоров x86, содержит сведения о многих процессорах Intel и AMD. Агнер Фог написал руководство по оптимизации кода для процессоров x86 и опубликовал собственные таблицы. В руководстве для разработчиков Intel содержится более 5000 страниц, описывающих не только набор инструкций, но и многие внутренние механизмы процессоров Intel.

У Apple Silicon ничего подобного нет. Я совершенно не представляю, как работать с процессорами M1+. Вот — руководство по оптимизации для процессора Apple Silicon, которое содержит всего 169 страниц и читается так, будто написано не для профессионалов, а для новичков. Выглядит оно как учебник, который можно найти на Hacker News, а не как нечто такое, что мне было бы интересно. Там содержатся лишь примерные оценки временных параметров и пропускной способности для некоторых категорий инструкций, а вот табличных данных там до обидного мало. Там не упоминается слияние микроопераций, нет там и информации о портах. Исследование Даголла Джонсона чрезвычайно полезно, но оно посвящено только процессорам M1, а не более новым CPU, и оно тоже не даёт ответов на многие вопросы.

Даже в форке LLVM, сделанном Apple, нет аннотаций по планированию инструкций для Apple Silicon. Как мне писать эффективный код, когда компания Apple не обеспокоилась тем, чтобы настроить собственный компилятор? Оптимизация кода для подобной платформы — это на 90% реверс-инжиниринг и на 10% — написание осмысленного кода, при том, что писать осмысленный код и без того — задача не из лёгких.

Правильное решение этой проблемы — кража интеллектуальной собственности, но мне нельзя этого говорить, поэтому я молчу. Упс.

Итоги

Оптимизация производительности — это сложная задача. Дело в том, что тому, кто за неё берётся, нужно следующее:

• Вручную исследовать дюжины вариантов и не сойти при этом с ума.

• Возиться с несовершенными инструментами. (Профилировщики и MCA — это штуки полезные, но они, при этом, остаются игрушками, возможности которых не соответствуют реальной сложности того, что с их помощью изучают.)

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

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

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

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