Kompilacje szybsze o 18% bez żadnych kompromisów

Zespół środowiska wykonawczego Androida (ART) skrócił czas kompilowania o 18% bez wpływu na skompilowany kod i bez regresji szczytowego wykorzystania pamięci. To ulepszenie było częścią naszej inicjatywy na 2025 r., której celem było skrócenie czasu kompilowania bez negatywnego wpływu na wykorzystanie pamięci i jakość skompilowanego kodu.

Optymalizacja szybkości kompilowania ma kluczowe znaczenie dla ART. Na przykład podczas kompilacji JIT ma to bezpośredni wpływ na wydajność aplikacji i ogólne działanie urządzenia. Szybsza kompilacja skraca czas, zanim optymalizacje zaczną działać, co przekłada się na płynniejsze i bardziej responsywne działanie aplikacji. Ponadto zarówno w przypadku JIT, jak i AOT (ahead-of-time) skrócenie czasu kompilowania przekłada się na mniejsze zużycie zasobów podczas procesu kompilacji, co korzystnie wpływa na czas pracy na baterii i temperaturę urządzenia, zwłaszcza w przypadku urządzeń niższej klasy.

Niektóre z tych ulepszeń szybkości kompilowania zostały wprowadzone w czerwcowej wersji Androida z 2025 r., a pozostałe będą dostępne w wersji Androida wydanej pod koniec roku. Ponadto wszyscy użytkownicy Androida w wersji 12 lub nowszej mogą korzystać z tych ulepszeń dzięki aktualizacjom Mainline.

Optymalizacja kompilatora optymalizującego

Optymalizacja kompilatora zawsze wiąże się z kompromisami. Nie można po prostu zwiększyć szybkości bez opłat – trzeba z czegoś zrezygnować. Wyznaczyliśmy sobie bardzo jasny i wymagający cel: przyspieszyć działanie kompilatora, ale bez wprowadzania regresji pamięci i, co najważniejsze, bez obniżania jakości generowanego kodu. Jeśli kompilator jest szybszy, ale aplikacje działają wolniej, to nie jest to sukces.

Jedynym zasobem, który byliśmy gotowi poświęcić, był nasz czas na programowanie, aby dokładnie zbadać problem i znaleźć sprytne rozwiązania, które spełniałyby te rygorystyczne kryteria. Przyjrzyjmy się bliżej temu, jak pracujemy nad znajdowaniem obszarów do poprawy i odpowiednich rozwiązań różnych problemów.

znajdowanie wartościowych możliwych optymalizacji,

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

Zasobem, który poświęcaliśmy na te ulepszenia, był czas programistów, dlatego chcieliśmy móc wprowadzać zmiany jak najszybciej. Oznaczało to, że do prototypowania rozwiązań wybraliśmy kilka reprezentatywnych aplikacji (mieszankę aplikacji własnych, aplikacji innych firm i samego systemu operacyjnego Android). Później sprawdziliśmy, czy ostateczna implementacja była tego warta, przeprowadzając testy ręczne i automatyczne na szeroką skalę.

Mając ten zestaw starannie wybranych plików APK, uruchamialiśmy ręczną kompilację lokalnie, uzyskiwaliśmy profil kompilacji i używaliśmy narzędzia pprof, aby zwizualizować, na co poświęcamy czas.

Przykład wykresu płomieniowego profilu w pprof

Narzędzie pprof jest bardzo zaawansowane i umożliwia dzielenie, filtrowanie i sortowanie danych, aby na przykład zobaczyć, które fazy lub metody kompilatora zajmują najwięcej czasu. Nie będziemy szczegółowo omawiać pprof. Wystarczy wiedzieć, że im większy pasek, tym więcej czasu zajęła kompilacja.

Jednym z tych widoków jest widok „od dołu”, w którym możesz zobaczyć, które metody zajmują najwięcej czasu. Na obrazie poniżej widzimy metodę o nazwie Kill, która odpowiada za ponad 1% czasu kompilowania. Inne popularne metody zostaną omówione w dalszej części posta na blogu.

Widok profilu od dołu

W naszym kompilatorze optymalizującym występuje faza o nazwie Global Value Numbering (GVN). Nie musisz się martwić o to, co robi jako całość, ale istotne jest to, że ma metodę o nazwie `Kill`, która usuwa niektóre węzły zgodnie z filtrem. Jest to czasochłonne, ponieważ wymaga iteracji przez wszystkie węzły i sprawdzania ich po kolei. Zauważyliśmy, że w niektórych przypadkach wiemy z góry, że wynik sprawdzenia będzie fałszywy, niezależnie od tego, które węzły są w danym momencie aktywne. W takich przypadkach możemy całkowicie pominąć iterację, co pozwala zmniejszyć jej udział z 1,023% do około 0,3% i skrócić czas działania GVN o około 15%.

Wdrażanie wartościowych optymalizacji

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

Zwykle w przypadku takim jak powyższy `Kill` sprawdzamy, jak iterujemy po węzłach, i przyspieszamy ten proces, na przykład wykonując czynności równolegle lub ulepszając sam algorytm. Właściwie to właśnie tego próbowaliśmy na początku i dopiero gdy nie mogliśmy znaleźć nic do zrobienia, zdaliśmy sobie sprawę, że rozwiązaniem jest (w niektórych przypadkach) brak iteracji. Podczas przeprowadzania tego rodzaju optymalizacji łatwo jest stracić z oczu szerszy obraz.

W innych przypadkach stosowaliśmy różne techniki, takie jak:

• używanie 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ć kod;
• unikanie wielokrotnego wczytywania często używanego wskaźnika,

Skąd wiadomo, czy warto wprowadzić optymalizacje?

To jest najlepsze – nie musisz. Czasami po wykryciu, że dany obszar wymaga dużo czasu kompilowania, i poświęceniu czasu na jego ulepszenie, nie można znaleźć rozwiązania. Może nie ma nic do zrobienia, wdrożenie zajmie zbyt dużo czasu, spowoduje znaczne pogorszenie innych danych, zwiększy złożoność bazy kodu itp. Na każdą udaną optymalizację, którą można zobaczyć w tym poście na blogu, przypada niezliczona liczba innych, które po prostu nie przyniosły efektów.

Jeśli jesteś w podobnej sytuacji, spróbuj oszacować, o ile możesz poprawić dany wskaźnik, wykonując jak najmniej pracy. Oznacza to, że:

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

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

Szczegółowe informacje

Bez zbędnych wstępów przyjrzyjmy się niektórym wprowadzonym zmianom.

Wprowadziliśmy zmianę mającą na celu optymalizację metody FindReferenceInfoOf. Ta metoda wykonywała wyszukiwanie liniowe wektora, aby znaleźć wpis. Zaktualizowaliśmy tę strukturę danych, aby była indeksowana według identyfikatora instrukcji, dzięki czemu FindReferenceInfoOf będzie mieć złożoność O(1) zamiast O(n). Wstępnie 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, ale było to niewielkie poświęcenie, ponieważ szczytowe wykorzystanie pamięci nie wzrosło. Przyspieszyło to fazę LoadStoreAnalysis o 34–66%, co z kolei skróciło czas kompilowania o około 0,5–1,8%.

Mamy niestandardową implementację HashSet, której używamy w kilku miejscach. Tworzenie tej struktury danych zajmowało dużo czasu i dowiedzieliśmy się, dlaczego tak było. Wiele lat temu ta struktura danych była używana tylko w kilku miejscach, w których używano bardzo dużych zbiorów HashSet, i została dostosowana pod tym kątem. Jednak obecnie jest używany w przeciwnym kierunku, z niewielką liczbą wpisów i krótkim czasem życia. Oznaczało to, że marnowaliśmy cykle, tworząc ten ogromny HashSet, ale używaliśmy go tylko do kilku wpisów, zanim go odrzuciliśmy. Dzięki tej zmianie udało się skrócić czas kompilowania o około 1, 3–2%. Dodatkową korzyścią było zmniejszenie wykorzystania pamięci o około 0,5–1%, ponieważ nie używaliśmy już tak dużych struktur danych jak wcześniej.

Skróciliśmy czas kompilowania o około 0,5–1% dzięki przekazywaniu struktur danych przez odwołanie do funkcji lambda, aby uniknąć ich kopiowania. Zostało to przeoczone podczas pierwotnej weryfikacji i pozostało w naszej bazie kodu przez lata. Dzięki analizie profili w pprof zauważyliśmy, że te metody tworzą i niszczą wiele struktur danych, co skłoniło nas do ich zbadania i zoptymalizowania.

Przyspieszyliśmy etap zapisywania skompilowanych danych wyjściowych przez buforowanie obliczonych wartości, co przełożyło się na skrócenie łącznego czasu kompilacji o około 1,3–2,8%. Niestety dodatkowe operacje księgowania były zbyt obciążające, a nasze automatyczne testy ostrzegły nas o regresji pamięci. Później przyjrzeliśmy się temu samemu kodowi i wdrożyliśmy nową wersję, która nie tylko rozwiązała problem z regresją pamięci, ale też skróciła czas kompilowania o kolejne 0,5–1,8%. W ramach tej drugiej zmiany musieliśmy przeprowadzić refaktoryzację i przemyśleć na nowo, jak powinna działać ta faza, aby pozbyć się jednej z 2 struktur danych.

W naszym kompilatorze optymalizującym mamy etap, który wstawia wywołania funkcji, aby zwiększyć wydajność. Aby wybrać metody do wstawienia, używamy zarówno heurystyki przed wykonaniem jakichkolwiek obliczeń, jak i ostatecznych kontroli po wykonaniu pracy, ale tuż przed sfinalizowaniem wstawiania. Jeśli którykolwiek z nich wykryje, że wstawianie nie jest opłacalne (np. dodanych zostanie zbyt wiele nowych instrukcji), nie wstawiamy wywołania metody.

Przenieśliśmy 2 testy z kategorii „testy końcowe” do kategorii „heurystyka”, aby oszacować, czy wstawianie się powiedzie, zanim wykonamy czasochłonne obliczenia. Ponieważ jest to wartość szacunkowa, nie jest idealna, ale sprawdziliśmy, że nasze nowe heurystyki obejmują 99,9% tego, co było wcześniej wstawiane, bez wpływu na wydajność. Jedna z tych nowych heurystyk dotyczyła potrzebnych rejestrów DEX (poprawa o ok.0,2–1,3%), a druga – liczby instrukcji (poprawa o ok.2%).

Mamy niestandardową implementację BitVector, której używamy w kilku miejscach. Zastąpiliśmy klasę BitVector, której rozmiar można zmieniać, 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 wektorów bitowych.

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

Gdybyśmy chcieli szczegółowo omówić wszystkie optymalizacje, zajęłoby nam to cały dzień. Jeśli chcesz poznać więcej optymalizacji, zapoznaj się z innymi wprowadzonymi przez nas zmianami:

• Dodaj księgowanie, aby skrócić czas kompilacji o około 0,6–1,6%.
• Obliczaj dane w sposób leniwy, aby w miarę możliwości uniknąć cykli.
• Zrefaktoryzujemy nasz kod, aby pomijać wstępne obliczenia, gdy nie będą używane.
• Unikaj niektórych zależnych łańcuchów wczytywania, gdy alokator można łatwo uzyskać z innych miejsc.
• Kolejny przypadek dodania sprawdzenia, aby uniknąć niepotrzebnych czynności.
• Unikaj częstego rozgałęziania według typu rejestru (rdzeń/FP) w alokatorze rejestrów.
• Upewnij się, że niektóre tablice są inicjowane w czasie kompilowania. Nie polegaj na clang.
• Usuń niektóre pętle. Używaj pętli zakresu, które kompilator clang może lepiej optymalizować, ponieważ nie musi ponownie wczytywać wewnętrznych wskaźników kontenera z powodu efektów ubocznych pętli. Unikaj wywoływania funkcji wirtualnej `HInstruction::GetInputRecords()` w pętli za pomocą wbudowanej funkcji `InputAt(.)` dla każdego wejścia.
• Unikaj funkcji Accept() we wzorcu odwiedzającego, wykorzystując optymalizację kompilatora.

Podsumowanie

Nasze wysiłki na rzecz skrócenia czasu kompilowania w ART przyniosły znaczące rezultaty. Android działa teraz płynniej i wydajniej, a bateria i urządzenie mniej się nagrzewają. Dzięki starannemu identyfikowaniu i wdrażaniu optymalizacji wykazaliśmy, że można znacznie skrócić czas kompilowania bez negatywnego wpływu na wykorzystanie pamięci czy jakość kodu.

Nasza podróż obejmowała profilowanie za pomocą narzędzi takich jak pprof, gotowość do iteracji, a czasem nawet porzucanie mniej owocnych ścieżek. Wspólne wysiłki zespołu ART nie tylko skróciły czas kompilowania o znaczący procent, ale też położyły podwaliny pod przyszłe ulepszenia.

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