Компиляция на 18 % быстрее без компромиссов

Команда Android Runtime (ART) сократила время компиляции на 18 %, не ухудшив скомпилированный код и не допустив регрессий пикового объема памяти. Это улучшение было частью нашей инициативы 2025 года по сокращению времени компиляции без ущерба для использования памяти или качества скомпилированного кода.

Оптимизация скорости компиляции имеет решающее значение для ART. Например, при JIT-компиляции это напрямую влияет на эффективность приложений и общую производительность устройства. Чем быстрее выполняется компиляция, тем раньше начинают действовать оптимизации, что делает приложение более плавным и отзывчивым. Кроме того, как для JIT-, так и для AOT-компиляции ускорение процесса означает снижение потребления ресурсов. Это положительно сказывается на времени работы от батареи и температуре устройства, особенно если оно относится к бюджетному сегменту.

Некоторые из этих улучшений были запущены в июньском выпуске Android 2025 года, а остальные будут доступны в выпуске Android в конце года. Кроме того, все пользователи Android 12 и более поздних версий могут получить эти улучшения через обновления Mainline.

Оптимизация оптимизирующего компилятора

Оптимизация компилятора – это всегда поиск компромиссов. Вы не можете просто так получить скорость; вам придется от чего-то отказаться. Мы поставили перед собой очень четкую и сложную цель: сделать компилятор быстрее, но сделать это без регрессии памяти и, что критически важно, без ухудшения качества кода, который он производит. Если компилятор работает быстрее, но приложения работают медленнее, мы потерпели неудачу.

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

Поиск возможных оптимизаций

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

Поскольку единственным ресурсом, который мы тратили на эти улучшения, было время разработки, мы хотели иметь возможность выполнять итерации как можно быстрее. Это значит, что мы взяли несколько репрезентативных приложений (собственные и сторонние приложения, а также саму операционную систему Android) для создания прототипов решений. Затем мы провели масштабное ручное и автоматизированное тестирование, чтобы убедиться, что все работает как надо.

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

Пример флейм-графа профиля в pprof

Инструмент pprof очень мощный и позволяет нам разбивать, фильтровать и сортировать данные, чтобы увидеть, например, какие фазы или методы компилятора занимают больше всего времени. Мы не будем подробно рассматривать pprof. Достаточно знать, что чем больше полоса, тем больше времени заняла компиляция.

Один из них – Bottom-Up (Снизу вверх). В нем показано, какие методы занимают больше всего времени. На изображении ниже мы видим вызов метода Kill, на который приходится более 1% времени компиляции. Некоторые другие популярные методы также будут рассмотрены далее в этой записи блога.

Профиль снизу вверх

В нашем оптимизирующем компиляторе есть этап, который называется глобальной нумерацией значений (GVN). Вам не нужно беспокоиться о том, что он делает в целом, но важно знать, что у него есть метод под названием `Kill`, который удаляет некоторые узлы в соответствии с фильтром. Это занимает много времени, поскольку приходится перебирать все узлы и проверять их один за другим. Мы заметили, что в некоторых случаях мы заранее знаем, что проверка будет ложной, независимо от того, какие узлы у нас живы на данный момент. В таких случаях мы можем полностью пропустить итерацию, снизив ее с 1,023% до ~0,3% и улучшив время выполнения GVN примерно на 15%.

Внедрение полезных оптимизаций

Мы рассмотрели, как измерять и определять, на что тратится время, но это только начало. Следующий шаг – оптимизировать время, затрачиваемое на компиляцию.

Обычно в таких случаях, как с методом `Kill`, мы смотрим, как происходит итерация по узлам, и ускоряем ее, например, за счет параллельного выполнения или улучшения самого алгоритма. Именно так мы и поступили вначале. Но когда мы не смогли найти ничего подходящего, нас осенило: в некоторых случаях решение заключается в том, чтобы вообще не использовать итерации. При такой оптимизации легко упустить из виду общую картину.

В других случаях мы использовали ряд различных методов, в том числе:

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

Как узнать, стоит ли проводить оптимизацию?

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

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

1. Оценка на основе уже собранных показателей или просто интуиция
2. Оценка с помощью быстрого и грязного прототипа
3. Реализуйте решение.

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

Изучение данных

Давайте посмотрим, что изменилось.

Мы оптимизировали метод FindReferenceInfoOf. Этот метод выполнял линейный поиск вектора, чтобы найти запись. Мы обновили структуру данных, чтобы она индексировалась по идентификатору инструкции. Это позволило сократить время выполнения FindReferenceInfoOf с O(n) до O(1). Также мы предварительно выделили вектор, чтобы избежать изменения размера. Мы немного увеличили объем памяти, так как нам пришлось добавить дополнительное поле, в котором подсчитывалось, сколько записей мы вставили в вектор, но это была небольшая жертва, поскольку пиковый объем памяти не увеличился. Это ускорило этап LoadStoreAnalysis на 34–66 %, что, в свою очередь, сократило время компиляции примерно на 0,5–1,8 %.

У нас есть собственная реализация HashSet, которую мы используем в нескольких местах. Создание этой структуры данных занимало значительное количество времени, и мы выяснили, почему. Много лет назад эта структура данных использовалась только в нескольких местах, где использовались очень большие HashSet, и она была настроена для оптимизации под это. Однако в настоящее время он используется в противоположном направлении, с небольшим количеством записей и коротким сроком службы. Это означало, что мы тратили циклы на создание огромного HashSet, но использовали его только для нескольких записей, прежде чем отбросить. Это изменение позволило сократить время компиляции примерно на 1, 3–2 %. В качестве дополнительного бонуса использование памяти сократилось примерно на 0,5–1 %, поскольку мы не использовали такие большие структуры данных, как раньше.

Мы улучшили время компиляции примерно на 0,5–1 %, передав структуры данных по ссылке в лямбда-выражение, чтобы избежать их копирования. Это было упущено при первоначальной проверке и оставалось в нашей базе кода в течение многих лет. Изучив профили в pprof, мы заметили, что эти методы создают и уничтожают множество структур данных. Это побудило нас исследовать и оптимизировать их.

Мы ускорили этап записи скомпилированных выходных данных за счет кеширования вычисленных значений, что позволило сократить общее время компиляции примерно на 1,3–2,8 %. К сожалению, дополнительный учет оказался слишком сложным, и наше автоматизированное тестирование предупредило нас о регрессии памяти. Позже мы ещё раз изучили этот код и реализовали новую версию, которая не только устранила регрессию памяти, но и сократила время компиляции ещё на 0,5–1,8 %. В этом втором изменении нам пришлось провести рефакторинг и переосмыслить, как должен работать этот этап, чтобы избавиться от одной из двух структур данных.

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

Мы перенесли две проверки из категории "окончательные проверки" в категорию "эвристические", чтобы оценить, будет ли встраивание успешным, прежде чем выполнять какие-либо трудоемкие вычисления. Поскольку это приблизительная оценка, она не идеальна, но мы убедились, что наши новые эвристики охватывают 99,9% того, что было встроено ранее, не влияя на производительность. Одна из новых эвристик касалась необходимых регистров DEX (улучшение примерно на 0,2–1,3 %), а другая – количества инструкций (улучшение примерно на 2 %).

У нас есть собственная реализация BitVector, которую мы используем в нескольких местах. Мы заменили класс BitVector с изменяемым размером на более простой BitVectorView для определенных бинарных векторов фиксированного размера. Это позволяет избежать некоторых косвенных обращений и проверок диапазонов во время выполнения, а также ускоряет создание объектов битовых векторов.

Кроме того, класс BitVectorView был шаблонизирован для базового типа хранилища (вместо того, чтобы всегда использовать uint32_t, как старый BitVector). Это позволяет некоторым операциям, например Union(), обрабатывать в два раза больше битов на 64-битных платформах. При компиляции ОС Android количество выборок затронутых функций было уменьшено более чем на 1% в целом. Это было сделано в несколько этапов [1, 2, 3, 4, 5, 6].

Если бы мы подробно рассказывали обо всех оптимизациях, мы бы провели здесь весь день! Если вы хотите узнать больше об оптимизации, ознакомьтесь с другими изменениями, которые мы внедрили:

• Добавьте ведение учета, чтобы сократить время компиляции примерно на 0,6–1,6%.
• По возможности используйте ленивые вычисления, чтобы избежать циклов.
• Провести рефакторинг кода, чтобы не выполнять предварительную обработку данных, если они не будут использоваться.
• Избегайте некоторых зависимых цепочек загрузки, когда распределитель можно легко получить из других мест.
• Ещё один случай, когда добавление проверки позволяет избежать лишней работы.
• Избегайте частого ветвления по типу регистра (основной/FP) в распределителе регистров.
• Убедитесь, что некоторые массивы инициализируются во время компиляции. Не полагайтесь на clang.
• Удалите некоторые циклы. Используйте циклы по диапазону, которые clang может оптимизировать лучше, поскольку ему не нужно перезагружать внутренние указатели контейнера из-за побочных эффектов цикла. Избегайте вызова виртуальной функции `HInstruction::GetInputRecords()` в цикле через встроенную функцию `InputAt(.)` для каждого ввода.
• Избегайте функций Accept() для шаблона посетителя, используя оптимизацию компилятора.

Заключение

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

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

Все эти улучшения доступны в обновлении Android за конец 2025 года, а также в основных обновлениях для Android 12 и более поздних версий. Надеемся, что этот подробный разбор процесса оптимизации дал вам ценное представление о сложностях и преимуществах разработки компиляторов.