Zespół środowiska wykonawczego Androida (ART) skrócił czas kompilowania o 18% bez pogorszenia jakości skompilowanego kodu ani regresji pamięci szczytowej. Ta zmiana została wprowadzona w ramach naszej inicjatywy z 2025 r., której celem było skrócenie czasu kompilacji bez pogorszenia wykorzystania pamięci ani jakości skompilowanego kodu.

Optymalizacja szybkości kompilacji jest kluczowa w przypadku ART. Na przykład w przypadku kompilacji just-in-time (JIT) ma to bezpośredni wpływ na wydajność aplikacji i ogólną wydajność urządzenia. Szybsze kompilacje skracają czas, zanim zaczną działać optymalizacje, co zapewnia płynniejsze i bardziej responsywne działanie aplikacji. Ponadto zarówno w przypadku kompilacji JIT, jak i AOT poprawa szybkości kompilacji przekłada się na mniejsze zużycie zasobów podczas procesu kompilacji, co korzystnie wpływa na żywotność baterii i temperaturę urządzenia, zwłaszcza w przypadku urządzeń z niższej półki.

Niektóre z tych ulepszeń dotyczących szybkości kompilacji zostały wprowadzone w czerwcowej wersji Androida z 2025 r., a pozostałe będą dostępne w wersji Androida z końca roku. Ponadto wszyscy użytkownicy Androida w wersji 12 lub nowszej mogą korzystać z tych ulepszeń dzięki aktualizacjom głównym.

Optymalizacja kompilatora optymalizującego

Optymalizacja kompilatora to zawsze kwestia kompromisów. Nie można uzyskać szybkości bezpłatnie, trzeba coś poświęcić. Postawiliśmy sobie jasny i ambitny cel: przyspieszyć działanie kompilatora, ale bez pogorszenia zarządzania pamięcią i co najważniejsze – bez obniżania jakości generowanego kodu. Jeśli kompilator działa szybciej, ale aplikacje działają wolniej, to znaczy, że nam się nie udało.

Jedynym zasobem, który byliśmy gotowi poświęcić, był czas naszych programistów na dogłębne zbadanie problemu i znalezienie sprytnych rozwiązań spełniających te surowe kryteria. Przyjrzyjmy się bliżej temu, jak szukamy obszarów do ulepszenia i jak znajdujemy odpowiednie rozwiązania różnych problemów.

Znajdowanie wartościowych możliwych optymalizacji

Zanim zaczniesz optymalizować dane, musisz mieć możliwość ich pomiaru. W przeciwnym razie nigdy nie będziesz mieć pewności, czy udało Ci się go poprawić. Na szczęście czas kompilacji jest dość stały, o ile zachowasz pewne środki ostrożności, takie jak używanie tego samego urządzenia do pomiarów przed i po zmianie oraz dbanie o to, aby urządzenie nie przegrzewało się. Oprócz tego mamy też pomiary deterministyczne, takie jak statystyki kompilatora, które pomagają nam zrozumieć, co się dzieje w tle.

Ponieważ zasobem, który poświęciliśmy na te ulepszenia, był czas programistów, chcieliśmy jak najszybciej wprowadzać kolejne zmiany. Oznaczało to, że wybraliśmy kilka reprezentatywnych aplikacji (mieszankę aplikacji własnych, aplikacji innych firm i samego systemu operacyjnego Android) do prototypowania rozwiązań. Później sprawdziliśmy, czy ostateczne wdrożenie było warte zachodu, przeprowadzając szeroko zakrojone testy ręczne i automatyczne.

W przypadku wybranej grupy plików APK ręcznie kompilowaliśmy je lokalnie, uzyskiwaliśmy profil kompilacji i używaliśmy narzędzia pprof, aby wizualizować, na co poświęcamy czas.

Przykład wykresu płomieniowego profilu w pprof

Narzędzie pprof jest bardzo przydatne i umożliwia dzielenie, filtrowanie i sortowanie danych, aby sprawdzić np. które fazy kompilatora lub metody zajmują najwięcej czasu. Nie będziemy szczegółowo omawiać pprof. Wystarczy, że wiesz, że im większy słupek, tym więcej czasu zajęła kompilacja.

Jednym z tych widoków jest widok „od dołu”, w którym możesz sprawdzić, które metody zajmują najwięcej czasu. Na ilustracji poniżej widać metodę o nazwie Kill, która odpowiada za ponad 1% czasu kompilacji. Niektóre z pozostałych najpopularniejszych metod omówimy w dalszej części tego posta na blogu.

Widok profilu od dołu

W naszym kompilatorze optymalizującym jest faza o nazwie Global Value Numbering (GVN). Nie musisz się martwić, co robi w całości, ale istotne jest, że ma metodę o nazwie „Kill”, która usuwa niektóre węzły zgodnie z filtrem. Jest to czasochłonne, ponieważ wymaga przejrzenia wszystkich węzłów i sprawdzenia ich po kolei. Zauważyliśmy, że w niektórych przypadkach z góry wiemy, że weryfikacja będzie negatywna, niezależnie od tego, które węzły są w danym momencie aktywne. W takich przypadkach możemy całkowicie pominąć iterację, zmniejszając ją z 1,023% do około 0,3% i skracając czas działania GVN o około 15%.

Wdrażanie wartościowych optymalizacji

Omówiliśmy już, jak mierzyć czas i wykrywać, na co jest on poświęcany, ale to dopiero początek. Kolejnym krokiem jest optymalizacja czasu kompilacji.

Zwykle w przypadku takim jak powyższy przykład „Kill” sprawdzamy, jak iterujemy węzły, i przyspieszamy ten proces, np. wykonując działania równolegle lub ulepszając sam algorytm. Właśnie tak próbowaliśmy na początku. Dopiero gdy nie mogliśmy niczego znaleźć, zdaliśmy sobie sprawę, że rozwiązaniem jest (w niektórych przypadkach) brak iteracji. Podczas przeprowadzania tego rodzaju optymalizacji łatwo jest stracić z oczu szerszą perspektywę.

W innych przypadkach stosowaliśmy różne techniki, w tym:

• stosowanie heurystyki do decydowania, czy optymalizacja nie przyniesie wartościowych wyników i czy można ją pominąć;
• używanie dodatkowych struktur danych do buforowania obliczonych danych,
• zmiana obecnych struktur danych w celu zwiększenia szybkości,
• leniwe obliczanie wyników, aby w niektórych przypadkach uniknąć cykli;
• używaj odpowiedniej abstrakcji – niepotrzebne funkcje mogą spowalniać działanie kodu;
• uniknąć śledzenia często używanego wskaźnika w wielu wczytaniach;

Skąd wiemy, czy warto wprowadzać optymalizacje?

To jest właśnie najlepsze, że nie musisz. Gdy wykryjesz, że jakiś obszar zużywa dużo czasu kompilacji, i poświęcisz czas na próby jego ulepszenia, czasami nie możesz po prostu znaleźć rozwiązania. Może nie ma nic do zrobienia, wdrożenie zmian zajmie zbyt dużo czasu, spowoduje znaczne pogorszenie innych danych, zwiększy złożoność bazy kodu itp. Pamiętaj, że na każdą udaną optymalizację, którą możesz zobaczyć w tym poście na blogu, przypada niezliczona liczba innych, które nie przyniosły oczekiwanych rezultatów.

Jeśli jesteś w podobnej sytuacji, spróbuj oszacować, o ile poprawisz dane, wykonując jak najmniej pracy. Oznacza to, że w kolejności:

1. Szacowanie na podstawie zebranych już danych lub intuicji
2. Szacowanie za pomocą szybkiego prototypu
3. Wdróż rozwiązanie.

Nie zapomnij oszacować wad swojego rozwiązania. Jeśli na przykład zamierzasz korzystać z dodatkowych struktur danych, ile pamięci chcesz wykorzystać?

Szczegółowe informacje

Przyjrzyjmy się niektórym zmianom, które wprowadziliśmy.

Wprowadziliśmy zmianę optymalizującą metodę o nazwie FindReferenceInfoOf. Ta metoda polegała na liniowym wyszukiwaniu wektora w celu znalezienia wpisu. Zaktualizowaliśmy tę strukturę danych, aby była indeksowana według identyfikatora instrukcji, dzięki czemu funkcja FindReferenceInfoOf będzie miała złożoność O(1) zamiast O(n). Wcześniej przydzieliliśmy też wektor, aby uniknąć zmiany rozmiaru. Nieznacznie zwiększyliśmy pamięć, ponieważ musieliśmy dodać dodatkowe pole, które zliczało liczbę wpisów wstawionych do wektora. Było to jednak niewielkie poświęcenie, ponieważ szczytowe zużycie pamięci nie wzrosło. Dzięki temu faza LoadStoreAnalysis została przyspieszona o 34–66%, co z kolei przekłada się na poprawę czasu kompilacji o ok. 0,5–1,8%.

W kilku miejscach używamy niestandardowej implementacji HashSet. Tworzenie tej struktury danych zajmowało sporo czasu. Dowiedzieliśmy się, dlaczego tak było. Wiele lat temu ta struktura danych była używana tylko w kilku miejscach, w których stosowano bardzo duże obiekty HashSet, i została dostosowana do optymalizacji pod tym kątem. Obecnie jest jednak używany w przeciwnym kierunku, ma tylko kilka wpisów i krótki okres ważności. Oznaczało to, że marnowaliśmy cykle, tworząc ten ogromny obiekt HashSet, ale używaliśmy go tylko w przypadku kilku wpisów, a potem go odrzucaliśmy. Dzięki tej zmianie udało nam się skrócić czas kompilacji o ok.1, 3–2%. Dodatkowo wykorzystanie pamięci zmniejszyło się o ok.0,5–1%, ponieważ nie używaliśmy już tak dużych struktur danych jak wcześniej.

Skróciliśmy czas kompilacji o ok.0,5–1% dzięki przekazywaniu struktur danych przez odwołanie do funkcji lambda, aby uniknąć ich kopiowania. To coś, co zostało pominięte w pierwotnej weryfikacji i przez lata znajdowało się w naszym kodzie. Dzięki analizie profili w pprof zauważyliśmy, że te metody tworzyły i usuwały wiele struktur danych, co skłoniło nas do zbadania i zoptymalizowania ich.

Przyspieszyliśmy fazę zapisu skompilowanych danych wyjściowych, buforując obliczone wartości, co przełożyło się na poprawę całkowitego czasu kompilacji o ok. 1,3–2,8%. Niestety dodatkowa księgowość okazała się zbyt skomplikowana, a nasze automatyczne testy wykryły regresję pamięci. Później ponownie przyjrzeliśmy się temu samemu kodowi i wdrożyliśmy nową wersję, która nie tylko rozwiązała problem regresji pamięci, ale także skróciła czas kompilacji o dodatkowe 0,5–1,8%. W ramach tej drugiej zmiany musieliśmy zmodyfikować i przekształcić sposób działania tej fazy, aby pozbyć się jednej z dwóch struktur danych.

W naszym kompilatorze optymalizującym mamy fazę, która wstawia wywołania funkcji w celu zwiększenia wydajności. Aby wybrać metody do wstawienia w kodzie, używamy zarówno heurystyki przed wykonaniem obliczeń, jak i ostatecznych kontroli po wykonaniu pracy, ale tuż przed sfinalizowaniem wstawiania. Jeśli którykolwiek z tych mechanizmów wykryje, że wstawianie nie jest opłacalne (np. dodanych zostanie zbyt wiele nowych instrukcji), nie wstawimy wywołania metody.

Przenieśliśmy 2 sprawdzania z kategorii „sprawdzanie końcowe” do kategorii „heurystyczne”, aby oszacować, czy wstawianie w kodzie się powiedzie, zanim wykonamy czasochłonne obliczenia. Jest to tylko szacunek, więc nie jest on idealny, ale sprawdziliśmy, że nasze nowe heurystyki obejmują 99,9% elementów, które były wcześniej wstawiane, bez wpływu na wydajność. Jedna z tych nowych heurystyk dotyczyła potrzebnych rejestrów DEX (wzrost o ok.0,2–1,3%), a druga – liczby instrukcji (wzrost o ok.2%).

W kilku miejscach używamy niestandardowej implementacji klasy BitVector. Zastąpiliśmy klasę BitVector o zmiennym rozmiarze prostszą klasą BitVectorView w przypadku niektórych wektorów bitowych o stałym rozmiarze. Eliminuje to niektóre pośrednie odwołania i sprawdzanie zakresu w czasie działania oraz przyspiesza tworzenie obiektów wektora bitowego.

Dodatkowo klasa BitVectorView została sparametryzowana na podstawie bazowego typu pamięci (zamiast zawsze używać typu uint32_t jak w przypadku starego typu BitVector). Dzięki temu niektóre operacje, np. Union(), mogą przetwarzać na platformach 64-bitowych 2 razy więcej bitów jednocześnie. Podczas kompilowania systemu operacyjnego Android próbki funkcji, których dotyczy problem, zostały zmniejszone o ponad 1% łącznie. Zostało to zrobione w ramach kilku zmian [1, 2, 3, 4, 5, 6].

Gdybyśmy szczegółowo omówili wszystkie optymalizacje, spędzilibyśmy tu cały dzień. Jeśli interesują Cię inne optymalizacje, zapoznaj się z innymi wprowadzonymi przez nas zmianami:

• Dodaj księgowość, aby skrócić czas kompilacji o ok. 0,6–1,6%.
• Obliczaj dane z opóźnieniem, aby w miarę możliwości uniknąć cykli.
• Przeprowadź refaktoryzację kodu, aby pominąć wstępne obliczenia, gdy nie będą używane.
• Unikaj niektórych łańcuchów ładowania zależnego, gdy alokator można łatwo uzyskać z innych miejsc.
• Kolejny przykład dodania sprawdzania, aby uniknąć niepotrzebnej pracy.
• Unikaj częstego rozgałęziania w przypadku typu rejestru (podstawowy/FP) w alokatorze rejestrów.
• Upewnij się, że niektóre tablice są inicjowane w czasie kompilowania. Nie polegaj na clang.
• Zwolnij miejsce, usuwając niektóre pętle. Używaj pętli zakresowych, które clang może lepiej zoptymalizować, ponieważ nie musi ponownie wczytywać wewnętrznych wskaźników kontenera z powodu efektów ubocznych pętli. Unikaj wywoływania w pętli funkcji wirtualnej `HInstruction::GetInputRecords()` za pomocą wstawionej funkcji `InputAt(.)` dla każdego wejścia.
• Unikaj funkcji Accept() w przypadku wzorca odwiedzającego, wykorzystując optymalizację kompilatora.

Podsumowanie

Nasze wysiłki na rzecz zwiększenia szybkości kompilacji ART przyniosły znaczące postępy, dzięki czemu Android działa płynniej i wydajniej, a bateria dłużej wytrzymuje i urządzenie mniej się nagrzewa. Dzięki starannemu identyfikowaniu i wdrażaniu optymalizacji udało nam się wykazać, że można znacznie skrócić czas kompilacji bez pogarszania wykorzystania pamięci ani jakości kodu.

Podczas naszej pracy korzystaliśmy z profilowania za pomocą narzędzi takich jak pprof, byliśmy gotowi do wprowadzania zmian, a czasami nawet rezygnowaliśmy z mniej owocnych rozwiązań. Dzięki wspólnym wysiłkom zespołu ART udało się nie tylko znacznie skrócić czas kompilacji, ale też stworzyć podstawy dla przyszłych ulepszeń.

Wszystkie te ulepszenia są dostępne w aktualizacji Androida na koniec 2025 r. oraz w przypadku Androida 12 i nowszych wersji w ramach aktualizacji głównej. Mamy nadzieję, że to szczegółowe omówienie naszego procesu optymalizacji dostarczy Ci cennych informacji o złożoności i korzyściach związanych z inżynierią kompilatorów.