Новости о продуктах

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

8 минут чтения
Посмотреть профиль участника Santiago Aboy Solanes Посмотреть профиль Чарльза Мангера
Santiago Aboy Solanes и Vladimír Marko

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

Optimizing compile-time speed is crucial for ART. For example, when just-in-time (JIT) compiling it directly impacts the efficiency of applications and overall device performance. Faster compilations reduce the time before the optimizations kick in, leading to a smoother and more responsive user experience. Furthermore, for both JIT and ahead-of-time (AOT), improvements in compile-time speed translate to reduced resource consumption during the compilation process, benefiting battery life and device thermals, especially on lower-end devices.

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

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

Optimizing a compiler is always a game of trade-offs. You can't just get speed for free; you have to give something up. We set a very clear and challenging goal for ourselves: make the compiler faster, but do it without introducing memory regressions and, crucially, without degrading the quality of the code it produces. If the compiler is faster but the apps run slower, we've failed.

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

Поиск перспективных вариантов оптимизации

Before you can begin to optimize a metric, you have to be able to measure it. Otherwise, you can't ever be sure if you improved it or not. Luckily for us, compile time speed is fairly consistent as long as you take some precautions like using the same device you use for measuring before and after a change, and making sure you don't thermal throttle your device. On top of that, we also have deterministic measurements like compiler statistics that help us understand what's going on under the hood.

Since the resource we were sacrificing for these improvements was our development time, we wanted to be able to iterate as fast as we could. This meant that we grabbed a handful of representative apps (a mix of first-party apps, third-party apps, and the Android operating system itself) to prototype solutions. Later, we verified that the final implementation was worth it with both manual and automated testing in a widespread manner.

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

image.png

Пример графика пламени профиля в pprof

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

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

image.png

Вид профиля снизу вверх

In our optimizing compiler, there's a phase called Global Value Numbering (GVN). You don't have to worry about what it does as a whole, but the relevant part is to know that it has a method called `Kill` that it will delete some nodes according to a filter. This is time consuming as it has to iterate through all the nodes and check one by one. We noticed that there are some cases in which we know in advance that the check will be false, no matter the nodes we have alive at that point. In these cases, we can skip iterating altogether , bringing it from 1.023% down to ~0.3% and improving GVN's runtime by ~15%.

Внедрение эффективных оптимизаций

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

Usually, in a case like the `Kill` one above we would take a look at how we iterate through the nodes and do it faster by, for example, doing things in parallel or improving the algorithm itself. In fact, that's what we tried at first and only when we couldn't find anything to do we had a “Wait a minute…” moment and saw that the solution was to (in some cases) not iterate at all! When doing these kinds of optimizations, it is easy to miss the forest for the trees.

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

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

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

That's the neat part, you don't. After detecting that an area is consuming a lot of compile time and after devoting development time to try to improve it, sometimes you can't just find a solution. Maybe there's nothing to do, it will take too long to implement, it will regress another metric significantly, increase code base complexity, etc. For every successful optimization that you can see in this blog post, know that there are countless others that just didn't come to fruition.

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

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

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

Погружение глубже

Итак, без лишних слов, давайте рассмотрим некоторые из изменений, которые мы внедрили.

We implemented a change to optimize a method called FindReferenceInfoOf. This method was doing a linear search of a vector to find an entry. We updated that data structure to be indexed by the instruction's id so that FindReferenceInfoOf would be O(1) instead of O(n). Also, we pre-allocated the vector to avoid resizing. We slightly increased memory as we had to add an extra field which counted how many entries we inserted in the vector, but it was a small sacrifice to make as the peak memory didn't increase. This sped up our LoadStoreAnalysis phase by 34-66% which in turns gives ~0.5-1.8% compile time improvement.

We have a custom implementation of HashSet that we use in several places. Creating this data structure was taking a considerable amount of time and we found out why. Many years ago, this data structure was used in only a few places that were using very big HashSets and it was tweaked to be optimized for that. However, nowadays it was used in the opposite direction with only a few entries and with a short lifespan. This meant that we were wasting cycles by creating this huge HashSet but we only used it for a few entries before discarding it. With this change , we improved ~1.3-2% of compile time. As an added bonus, memory usage decreased by ~0.5-1% since we weren't using as big data structures as before.

We improved ~0.5-1% of compile time by passing data structures by reference to the lambda to avoid copying them around. This was something that was missed in the original review and sat in our codebase for years. It was thanks to taking a look at the profiles in pprof that we noticed that these methods were creating and destroying a lot of data structures, which led us to investigate and optimize them.

We sped up the phase that writes the compiled output by caching computed values , which translated to ~1.3-2.8% of total compile time improvement. Sadly, the extra bookkeeping was too much and our automated testing alerted us of the memory regression. Later, we took a second look at the same code and implemented a new version which not only took care of the memory regression but also improved the compile time a further ~0.5-1.8%! In this second change we had to refactor and reimagine how this phase should work, in order to get rid of one of the two data structures.

We have a phase in our optimizing compiler which inlines function calls in order to get better performance. To choose which methods to inline we use both heuristics before we do any computation, and final checks after doing work but right before we finalize the inlining. If any of those detect that the inlining is not worth it (for example, too many new instructions would be added), then we don't inline the method call.

We moved two checks from the “final checks” category to the “heuristic” category to estimate whether an inlining will succeed or not before we do any time-expensive computation. Since this is an estimate it is not perfect, but we verified that our new heuristics cover 99.9% of what was inlined before without affecting performance. One of these new heuristics was about the needed DEX registers (~0.2-1.3% improvement), and the other one about number of instructions (~2% improvement).

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

Furthermore, the BitVectorView class was templatized on the underlying storage type (instead of always using uint32_t as the old BitVector). This allows some operations, for example Union(), to process twice as many bits together on 64-bit platforms. The samples of the affected functions were reduced by more than 1% in total when compiling the Android OS. This was done across several changes [ 1 , 2 , 3 , 4 , 5 , 6 ]

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

Заключение

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

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

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

    Автор:
    Продолжить чтение