Nowości o produktach

Kompilacja szybsza o 18%, bez kompromisów

Czas czytania: 8 minut
Santiago Aboy Solanes & Vladimír Marko

Zespół środowiska wykonawczego Androida (ART) skrócił czas kompilowania o 18% bez pogorszenia jakości skompilowanego kodu i bez regresji w zakresie maksymalnego wykorzystania pamięci. Ta poprawa była częścią naszej inicjatywy z 2025 r., której celem było skrócenie czasu kompilowania bez pogorszenia jakości skompilowanego kodu i bez zwiększenia wykorzystania pamięci.

Optymalizacja szybkości kompilacji jest kluczowa dla ART. Na przykład w przypadku kompilacji JIT (just-in-time) ma ona bezpośredni wpływ na wydajność aplikacji i ogólną wydajność urządzenia. Szybsze kompilacje skracają czas, zanim zaczną działać optymalizacje, co przekłada się na płynniejsze i bardziej responsywne działanie aplikacji. Ponadto zarówno w przypadku kompilacji JIT, jak i AOT (ahead-of-time) poprawa szybkości kompilacji przekłada się na mniejsze zużycie zasobów podczas 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 czerwcu 2025 r. w wersji Androida, a pozostałe będą dostępne w wersji Androida na koniec roku. Ponadto wszyscy użytkownicy Androida w wersji 12 i nowszej mogą korzystać z tych ulepszeń dzięki aktualizacjom mainline.

Optymalizacja kompilatora optymalizującego

Optymalizacja kompilatora to zawsze gra kompromisów. Nie można po prostu uzyskać szybkości bezpłatnie – trzeba coś poświęcić. Postawiliśmy sobie bardzo jasny i ambitny cel: przyspieszyć kompilator, ale bez regresji w zakresie wykorzystania pamięci i, co najważniejsze, bez pogorszenia jakości generowanego kodu. Jeśli kompilator będzie szybszy, ale aplikacje będą działać wolniej, to znaczy, że nam się nie udało.

Jedynym zasobem, który byliśmy gotowi poświęcić, był nasz czas na opracowywanie rozwiązań. Chcieliśmy dokładnie zbadać problem i znaleźć inteligentne 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 możliwych optymalizacji

Zanim zaczniesz optymalizować dany wskaźnik, musisz mieć możliwość jego pomiaru. W przeciwnym razie nigdy nie będziesz mieć pewności, czy udało Ci się go poprawić. Na szczęście szybkość czasu kompilowania jest dość stała, o ile zachowasz pewne środki ostrożności, takie jak używanie tego samego urządzenia do pomiarów przed i po zmianie oraz upewnienie się, że nie dochodzi do ograniczenia wydajności urządzenia z powodu przegrzania. 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ł nasz czas na opracowywanie rozwiązań, chcieliśmy móc jak najszybciej wprowadzać zmiany. W tym celu wybraliśmy kilka reprezentatywnych aplikacji (mieszankę aplikacji własnych, aplikacji innych firm i samego systemu operacyjnego Android) do prototypowania rozwiązań. Następnie sprawdziliśmy, czy ostateczna implementacja jest opłacalna, przeprowadzając ręczne i automatyczne testy na szeroką skalę.

 

W przypadku tego zestawu wybranych plików APK uruchamialiśmy ręczną kompilację lokalnie, uzyskiwaliśmy profil kompilacji i używaliśmy narzędzia pprof do wizualizacji, gdzie spędzamy najwięcej czasu.

image.png

Przykład wykresu płomieniowego profilu w pprof

Narzędzie pprof jest bardzo wydajne i pozwala nam dzielić, filtrować i sortować dane, aby zobaczyć na przykład, które fazy lub metody kompilatora zajmują najwięcej czasu. Nie będziemy szczegółowo omawiać samego narzędzia 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 do góry”, w którym możesz zobaczyć, które metody zajmują najwięcej czasu. Na obrazie poniżej widzimy metodę o nazwie Kill, która stanowi ponad 1% czasu kompilacji. Niektóre z innych najpopularniejszych metod omówimy później w tym poście.

image.png

Widok profilu od dołu do góry

W naszym kompilatorze optymalizującym jest faza o nazwie Global Value Numbering (GVN). Nie musisz się martwić tym, co robi w całości, ale istotne jest, aby wiedzieć, że ma metodę o nazwie `Kill`, która usuwa niektóre węzły zgodnie z filtrem. Jest to czasochłonne, ponieważ trzeba przejść przez wszystkie węzły i sprawdzić je jeden po drugim. Zauważyliśmy, że w niektórych przypadkach z góry wiemy, że sprawdzenie będzie fałszywe, niezależnie od tego, które węzły są w danym momencie aktywne. W takich przypadkach możemy całkowicie pominąć iterację, co zmniejszy czas kompilacji z 1,023% do ok.0,3% i poprawi czas działania GVN o ok.15%.

Wdrażanie optymalizacji

Omówiliśmy, jak mierzyć i jak wykrywać, gdzie jest spędzany czas, ale to dopiero początek. Następnym krokiem jest optymalizacja czasu spędzanego na kompilacji.

Zwykle w przypadku takim jak opisany powyżej `Kill` sprawdzamy, jak iterujemy przez węzły, i przyspieszamy ten proces, np. wykonując działania równolegle lub ulepszając sam algorytm. W rzeczywistości to właśnie zrobiliśmy na początku. Dopiero gdy nie mogliśmy niczego znaleźć, mieliśmy moment „Zaraz, zaraz…” i zobaczyliśmy, że rozwiązaniem jest (w niektórych przypadkach) całkowite pominięcie iteracji. Podczas wykonywania tego typu optymalizacji łatwo jest nie dostrzec całości obrazu.

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

  • używanie heurystyki do określania, czy optymalizacja nie przyniesie wartościowych wyników i czy można ją pominąć;
  • używanie dodatkowych struktur danych do buforowania obliczonych danych;
  • zmienianie bieżących struktur danych w celu zwiększenia szybkości;
  • leniwe obliczanie wyników, aby w niektórych przypadkach uniknąć cykli;
  • używanie odpowiedniej abstrakcji – niepotrzebne funkcje mogą spowolnić kod;
  • unikanie śledzenia często używanego wskaźnika przez wiele wczytań.

Skąd wiemy, czy warto dążyć do optymalizacji?

To jest właśnie ta trudna część – nie wiemy. Po wykryciu, że dany obszar zajmuje dużo czasu kompilacji, i po poświęceniu czasu na opracowywanie rozwiązań, aby go poprawić, czasami nie można po prostu znaleźć rozwiązania. Może nie ma nic do zrobienia, implementacja zajmie zbyt dużo czasu, spowoduje znaczną regresję innego wskaźnika, 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, przypada niezliczona liczba innych, które nie przyniosły oczekiwanych rezultatów.

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

  1. Oszacuj na podstawie zebranych już danych lub po prostu na podstawie intuicji.
  2. Oszacuj na podstawie szybkiego i prostego 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 użyć?

Szczegółowe informacje

Bez zbędnych ceregieli przyjrzyjmy się niektórym wprowadzonym przez nas zmianom.

Wprowadziliśmy zmianę, aby zoptymalizować metodę o nazwie FindReferenceInfoOf. Ta metoda wykonywała liniowe wyszukiwanie wektora w celu znalezienia wpisu. Zaktualizowaliśmy tę strukturę danych, aby była indeksowana według identyfikatora instrukcji, dzięki czemu FindReferenceInfoOf będzie O(1) zamiast O(n). Ponadto wstępnie przydzieliliśmy wektor, aby uniknąć zmiany jego rozmiaru. Nieznacznie zwiększyliśmy ilość pamięci, 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ż maksymalne wykorzystanie pamięci nie wzrosło. Dzięki temu przyspieszyliśmy fazę LoadStoreAnalysis o 34–66%, co z kolei daje ok. 0,5–1,8% poprawy czasu kompilacji.

W kilku miejscach używamy niestandardowej implementacji HashSet. Tworzenie tej struktury danych zajmowało sporo czasu i dowiedzieliśmy się dlaczego. 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 do optymalizacji pod tym kątem. Obecnie jednak była używana w przeciwnym kierunku – tylko z kilkoma wpisami i krótkim czasem życia. Oznaczało to, że marnowaliśmy cykle, tworząc ten ogromny zbiór HashSet, ale używaliśmy go tylko do kilku wpisów, zanim go odrzuciliśmy. Dzięki tej zmianie poprawiliśmy 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.

Poprawiliśmy czas kompilacji o ok.0,5–1%, przekazując struktury danych przez odwołanie do lambdy, aby uniknąć ich kopiowania. To było coś, co zostało pominięte w pierwotnej recenzji i przez lata znajdowało się w naszej bazie kodu. Dzięki przyjrzeniu się profilom w pprof zauważyliśmy, że te metody tworzyły i niszczyły wiele struktur danych, co skłoniło nas do zbadania i zoptymalizowania ich.

Przyspieszyliśmy fazę, która zapisuje skompilowane dane wyjściowe, przez buforowanie obliczonych wartości, co przełożyło się na ok. 1,3–2,8% poprawy całkowitego czasu kompilacji. Niestety dodatkowe księgowanie było zbyt duże i nasze automatyczne testy ostrzegły nas o regresji w zakresie wykorzystania 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 w zakresie wykorzystania pamięci, ale też dodatkowo poprawiła czas kompilacji o ok.0,5–1,8%. W tej drugiej zmianie musieliśmy przeprowadzić refaktoryzację i ponownie przemyśleć, jak ta faza powinna działać, aby pozbyć się jednej z dwóch struktur danych.

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

Przenieśliśmy 2 sprawdzenia z kategorii „sprawdzenia końcowe” do kategorii „heurystyka”, aby oszacować, czy wstawienie się powiedzie, zanim wykonamy jakiekolwiek czasochłonne obliczenia. Ponieważ jest to szacunek, nie jest on idealny, ale sprawdziliśmy, że nasza nowa heurystyka obejmuje 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%).

W kilku miejscach używamy niestandardowej implementacji BitVector. W przypadku niektórych wektorów bitowych o stałym rozmiarze zastąpiliśmy klasę BitVector z możliwością zmiany rozmiaru prostszą klasą BitVectorView. 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 sparametryzowana na podstawie bazowego typu pamięci (zamiast zawsze używać uint32_t jak w przypadku starej klasy 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ły zmiany, zostały zmniejszone o ponad 1% w sumie. 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:

Podsumowanie

Nasze zaangażowanie w poprawę szybkości kompilacji ART przyniosło znaczące ulepszenia, dzięki czemu Android działa płynniej i wydajniej, a także przyczynia się do wydłużenia czasu pracy na baterii i zmniejszenia temperatury urządzenia. Dzięki starannemu identyfikowaniu i wdrażaniu optymalizacji udowodniliśmy, że można uzyskać znaczne oszczędności czasu kompilowania bez pogorszenia jakości kodu i bez zwiększenia wykorzystania pamięci.

Nasza praca obejmowała profilowanie za pomocą narzędzi takich jak pprof, gotowość do wprowadzania zmian, a czasami nawet porzucanie mniej owocnych ścieżek. Wspólne wysiłki zespołu ART nie tylko skróciły czas kompilacji o znaczący procent, ale też stworzyły podstawy do przyszłych ulepszeń.

Wszystkie te ulepszenia są dostępne w aktualizacji Androida na koniec 2025 r. oraz w Androidzie 12 i nowszym dzięki aktualizacjom mainline. Mamy nadzieję, że to szczegółowe omówienie naszego procesu optymalizacji dostarczy Ci cennych informacji o złożoności i korzyściach inżynierii kompilatorów.

Autorzy:

Czytaj dalej