18% schnellere Kompilierung, 0% Kompromisse

Das Android Runtime (ART)-Team hat die Kompilierungszeit um 18% reduziert, ohne den kompilierten Code oder die maximale Speichernutzung zu beeinträchtigen. Diese Verbesserung war Teil unserer Initiative für 2025, die Kompilierungszeit zu verbessern, ohne die Arbeitsspeichernutzung oder die Qualität des kompilierten Codes zu beeinträchtigen.

Die Optimierung der Kompilierzeit ist für ART entscheidend. Bei der Just-in-Time-Kompilierung (JIT) wirkt sich dies beispielsweise direkt auf die Effizienz von Anwendungen und die Gesamtleistung des Geräts aus. Durch die schnellere Kompilierung werden die Optimierungen früher wirksam, was zu einer reibungsloseren und reaktionsschnelleren Nutzung führt. Darüber hinaus führen Verbesserungen bei der Kompilierungsgeschwindigkeit sowohl bei JIT als auch bei Ahead-of-Time (AOT) zu einem geringeren Ressourcenverbrauch während des Kompilierungsprozesses. Das wirkt sich positiv auf die Akkulaufzeit und die Gerätetemperatur aus, insbesondere bei Geräten mit geringerer Leistung.

Einige dieser Verbesserungen der Kompilierungsgeschwindigkeit wurden im Android-Release vom Juni 2025 eingeführt, die restlichen werden im Android-Release am Ende des Jahres verfügbar sein. Außerdem können alle Android-Nutzer mit Version 12 und höher diese Verbesserungen über Mainline-Updates erhalten.

Optimierungs-Compiler optimieren

Die Optimierung eines Compilers ist immer ein Spiel mit Kompromissen. Geschwindigkeit ist nicht kostenlos zu haben. Sie müssen dafür etwas aufgeben. Wir haben uns ein sehr klares und anspruchsvolles Ziel gesetzt: den Compiler schneller zu machen, aber ohne Speicherregressionen einzuführen und vor allem ohne die Qualität des erzeugten Codes zu beeinträchtigen. Wenn der Compiler schneller ist, die Apps aber langsamer laufen, haben wir versagt.

Die einzige Ressource, die wir bereit waren, zu investieren, war unsere eigene Entwicklungszeit, um tief einzutauchen, zu recherchieren und clevere Lösungen zu finden, die diese strengen Kriterien erfüllen. Sehen wir uns genauer an, wie wir Bereiche mit Verbesserungspotenzial finden und die richtigen Lösungen für die verschiedenen Probleme entwickeln.

Sinnvolle Optimierungsmöglichkeiten finden

Bevor Sie einen Messwert optimieren können, müssen Sie ihn messen können. Andernfalls können Sie nie sicher sein, ob Sie es verbessert haben oder nicht. Glücklicherweise ist die Kompilierungszeit ziemlich konsistent, solange Sie einige Vorsichtsmaßnahmen treffen, z. B. dasselbe Gerät für die Messung vor und nach einer Änderung verwenden und darauf achten, dass Ihr Gerät nicht thermisch gedrosselt wird. Darüber hinaus haben wir auch deterministische Messungen wie Compilerstatistiken, die uns helfen, die Vorgänge im Hintergrund zu verstehen.

Da die Ressource, die wir für diese Verbesserungen opfern mussten, unsere Entwicklungszeit war, wollten wir so schnell wie möglich iterieren können. Dazu haben wir eine Handvoll repräsentativer Apps (eine Mischung aus eigenen Apps, Drittanbieter-Apps und dem Android-Betriebssystem selbst) ausgewählt, um Prototypen für Lösungen zu entwickeln. Anschließend haben wir die endgültige Implementierung sowohl manuell als auch automatisiert umfassend getestet, um sicherzustellen, dass sich der Aufwand gelohnt hat.

Mit diesen ausgewählten APKs haben wir lokal eine manuelle Kompilierung ausgelöst, ein Profil der Kompilierung erstellt und mit pprof visualisiert, wo wir unsere Zeit verbringen.

Beispiel für ein Flame-Diagramm eines Profils in pprof

Das pprof-Tool ist sehr leistungsstark und ermöglicht es uns, die Daten zu segmentieren, zu filtern und zu sortieren, um beispielsweise zu sehen, welche Compilerphasen oder -methoden die meiste Zeit in Anspruch nehmen. Wir gehen hier nicht näher auf pprof ein. Sie müssen nur wissen, dass ein größerer Balken bedeutet, dass die Kompilierung länger gedauert hat.

Eine dieser Ansichten ist die „Bottom-up“-Ansicht, in der Sie sehen können, welche Methoden die meiste Zeit in Anspruch nehmen. In der Abbildung unten sehen wir eine Methode namens „Kill“, die mehr als 1% der Kompilierungszeit ausmacht. Einige der anderen Top-Methoden werden später im Blogpost besprochen.

Ansicht eines Profils von unten

In unserem optimierenden Compiler gibt es eine Phase namens Global Value Numbering (GVN). Sie müssen sich nicht darum kümmern, was sie insgesamt tut. Der relevante Teil ist, dass sie eine Methode namens „Kill“ hat, die einige Knoten gemäß einem Filter löscht. Das ist zeitaufwendig, da alle Knoten einzeln durchlaufen und geprüft werden müssen. Wir haben festgestellt, dass es einige Fälle gibt, in denen wir im Voraus wissen, dass die Prüfung fehlschlägt, unabhängig davon, welche Knoten zu diesem Zeitpunkt aktiv sind. In diesen Fällen können wir die Iteration ganz überspringen, wodurch der Anteil von 1,023% auf etwa 0,3% sinkt und die Laufzeit von GVN um etwa 15 % verbessert wird.

Sinnvolle Optimierungen implementieren

Wir haben uns angesehen, wie Sie die Zeit messen und herausfinden können, wo sie verbracht wird. Das ist aber nur der Anfang. Im nächsten Schritt geht es darum, die für die Kompilierung aufgewendete Zeit zu optimieren.

In einem Fall wie dem obigen „Kill“-Beispiel würden wir uns normalerweise ansehen, wie wir die Knoten durchlaufen, und dies beschleunigen, indem wir beispielsweise Dinge parallel ausführen oder den Algorithmus selbst verbessern. Tatsächlich haben wir das zuerst versucht. Erst als wir nichts mehr fanden, was wir tun konnten, hatten wir einen „Moment mal…“-Moment und erkannten, dass die Lösung (in einigen Fällen) darin bestand, überhaupt nicht zu iterieren! Bei solchen Optimierungen kann man leicht den Wald vor lauter Bäumen übersehen.

In anderen Fällen haben wir verschiedene Techniken verwendet, darunter:

• Heuristiken verwenden, um zu entscheiden, ob eine Optimierung keine nennenswerten Ergebnisse liefert und daher übersprungen werden kann
• Verwendung zusätzlicher Datenstrukturen zum Zwischenspeichern berechneter Daten
• Ändern der aktuellen Datenstrukturen, um einen Geschwindigkeitsschub zu erhalten
• Ergebnisse werden in einigen Fällen verzögert berechnet, um Zyklen zu vermeiden
• Verwenden Sie die richtige Abstraktion – unnötige Funktionen können den Code verlangsamen.
• Vermeiden Sie es, einen häufig verwendeten Zeiger durch viele Ladevorgänge zu verfolgen.

Woher wissen wir, ob sich die Optimierungen lohnen?

Das ist das Tolle daran: Sie müssen es gar nicht. Wenn Sie feststellen, dass ein Bereich viel Kompilierungszeit in Anspruch nimmt, und Sie Entwicklungszeit investieren, um ihn zu verbessern, finden Sie manchmal einfach keine Lösung. Vielleicht gibt es nichts zu tun, die Implementierung dauert zu lange, ein anderer Messwert wird erheblich verschlechtert, die Komplexität der Codebasis wird erhöht usw. Für jede erfolgreiche Optimierung, die Sie in diesem Blogpost sehen, gibt es unzählige andere, die einfach nicht zum Tragen kamen.

Wenn Sie sich in einer ähnlichen Situation befinden, versuchen Sie, mit möglichst wenig Aufwand abzuschätzen, wie stark Sie den Messwert verbessern können. Das bedeutet in der Reihenfolge:

1. Schätzung anhand von bereits erhobenen Messwerten oder einfach nach Bauchgefühl
2. Schätzung mit einem schnellen und unsauberen Prototyp
3. Lösung implementieren

Vergessen Sie nicht, die Nachteile Ihrer Lösung abzuschätzen. Wenn Sie beispielsweise zusätzliche Datenstrukturen verwenden, wie viel Arbeitsspeicher sind Sie bereit, zu nutzen?

Detailliertere Informationen

Sehen wir uns also einige der Änderungen an, die wir vorgenommen haben.

Wir haben eine Änderung zur Optimierung einer Methode namens „FindReferenceInfoOf“ vorgenommen. Bei dieser Methode wurde ein Vektor linear durchsucht, um einen Eintrag zu finden. Wir haben diese Datenstruktur so aktualisiert, dass sie nach der ID der Anweisung indexiert wird, sodass FindReferenceInfoOf O(1) statt O(n) ist. Außerdem haben wir den Vektor vorab zugewiesen, um eine Größenänderung zu vermeiden. Wir haben den Arbeitsspeicher leicht erhöht, da wir ein zusätzliches Feld hinzufügen mussten, das die Anzahl der in den Vektor eingefügten Einträge zählt. Das war jedoch ein kleines Opfer, da der maximale Arbeitsspeicher nicht erhöht wurde. Dadurch wurde die LoadStoreAnalysis-Phase um 34–66% beschleunigt, was wiederum die Kompilierungszeit um etwa 0,5–1,8% verbessert.

Wir haben eine benutzerdefinierte Implementierung von HashSet, die wir an mehreren Stellen verwenden. Das Erstellen dieser Datenstruktur hat sehr viel Zeit in Anspruch genommen und wir haben herausgefunden, warum. Vor vielen Jahren wurde diese Datenstruktur nur an wenigen Stellen verwendet, an denen sehr große HashSets zum Einsatz kamen, und sie wurde dafür optimiert. Heutzutage wird sie jedoch in die entgegengesetzte Richtung verwendet, mit nur wenigen Einträgen und einer kurzen Lebensdauer. Das bedeutete, dass wir durch das Erstellen dieses riesigen HashSets Zyklen verschwendeten, es aber nur für ein paar Einträge verwendeten, bevor wir es verwarfen. Mit dieser Änderung haben wir die Kompilierungszeit um etwa 1, 3–2% verbessert. Als zusätzlicher Bonus sank die Arbeitsspeichernutzung um etwa 0,5–1 %, da wir nicht mehr so große Datenstrukturen wie zuvor verwendeten.

Wir haben die Kompilierungszeit um etwa 0,5–1% verbessert, indem wir Datenstrukturen per Referenz an das Lambda übergeben haben, um das Kopieren zu vermeiden. Dies wurde bei der ursprünglichen Überprüfung übersehen und blieb jahrelang in unserer Codebasis. Dank der Profile in pprof haben wir festgestellt, dass diese Methoden viele Datenstrukturen erstellen und zerstören. Das hat uns dazu veranlasst, sie zu untersuchen und zu optimieren.

Wir haben die Phase, in der die kompilierte Ausgabe geschrieben wird, durch das Caching berechneter Werte beschleunigt. Dadurch wurde die Gesamtkompilierungszeit um etwa 1,3–2,8% verbessert. Leider war die zusätzliche Buchführung zu viel und unsere automatisierten Tests haben uns auf die Speicherregression aufmerksam gemacht. Später haben wir uns denselben Code noch einmal angesehen und eine neue Version implementiert, die nicht nur die Speicherregression behoben, sondern auch die Kompilierzeit um weitere ca.0,5–1,8 % verbessert hat. Bei dieser zweiten Änderung mussten wir die Funktionsweise dieser Phase refaktorieren und neu gestalten, um eine der beiden Datenstrukturen zu entfernen.

In unserem optimierenden Compiler gibt es eine Phase, in der Funktionsaufrufe inline eingefügt werden, um die Leistung zu verbessern. Um zu entscheiden, welche Methoden inline eingefügt werden sollen, verwenden wir sowohl Heuristiken vor der Berechnung als auch abschließende Prüfungen nach der Arbeit, aber direkt vor dem Abschluss des Inlining. Wenn eine dieser Prüfungen ergibt, dass sich das Inlining nicht lohnt (z. B. weil zu viele neue Anweisungen hinzugefügt würden), wird der Methodenaufruf nicht inline eingefügt.

Wir haben zwei Prüfungen von der Kategorie „Letzte Prüfungen“ in die Kategorie „Heuristik“ verschoben, um vor einer zeitaufwendigen Berechnung abzuschätzen, ob ein Inlining erfolgreich sein wird oder nicht. Da es sich um eine Schätzung handelt, ist sie nicht perfekt.Wir haben jedoch überprüft, dass unsere neuen Heuristiken 99,9% der zuvor inline eingefügten Elemente abdecken, ohne die Leistung zu beeinträchtigen. Eine dieser neuen Heuristiken betraf die erforderlichen DEX-Register (Verbesserung um ca.0,2–1,3 %) und die andere die Anzahl der Anweisungen (Verbesserung um ca.2 %).

Wir haben eine benutzerdefinierte Implementierung eines BitVectors, die wir an mehreren Stellen verwenden. Wir haben die BitVector-Klasse, deren Größe angepasst werden kann, für bestimmte Bitvektoren mit fester Größe durch eine einfachere BitVectorView ersetzt. Dadurch werden einige Indirektionen und Laufzeitbereichsprüfungen vermieden und die Erstellung der Bitvektorobjekte wird beschleunigt.

Außerdem wurde die Klasse „BitVectorView“ auf dem zugrunde liegenden Speichertyp templatisiert (anstatt immer uint32_t wie der alte BitVector zu verwenden). Dadurch können einige Vorgänge, z. B. Union(), auf 64-Bit-Plattformen doppelt so viele Bits gleichzeitig verarbeiten. Die Stichproben der betroffenen Funktionen wurden beim Kompilieren des Android-Betriebssystems insgesamt um mehr als 1% reduziert. Dies wurde im Rahmen mehrerer Änderungen umgesetzt [1, 2, 3, 4, 5, 6].

Wenn wir alle Optimierungen im Detail besprechen würden, wären wir den ganzen Tag beschäftigt. Wenn Sie an weiteren Optimierungen interessiert sind, sehen Sie sich einige andere Änderungen an, die wir vorgenommen haben:

• Buchführung hinzufügen, um die Kompilierungszeiten um ca. 0,6–1,6 % zu verbessern.
• Berechnen Sie Daten nach Möglichkeit verzögert, um Zyklen zu vermeiden.
• Refaktorieren Sie den Code, um die Vorberechnung zu überspringen, wenn sie nicht verwendet wird.
• Vermeiden Sie einige abhängige Ladeketten, wenn der Allocator leicht von anderen Stellen abgerufen werden kann.
• Ein weiterer Fall, in dem eine Prüfung hinzugefügt wird, um unnötige Arbeit zu vermeiden.
• Vermeiden Sie häufige Verzweigungen nach Registertyp (Core/FP) im Register-Allocator.
• Achten Sie darauf, dass einige Arrays zur Kompilierzeit initialisiert werden. Verlassen Sie sich nicht darauf, dass Clang das erledigt.
• Schleifen bereinigen Verwenden Sie Bereichsschleifen, die von clang besser optimiert werden können, da die internen Zeiger des Containers aufgrund von Schleifennebenwirkungen nicht neu geladen werden müssen. Vermeiden Sie es, die virtuelle Funktion „HInstruction::GetInputRecords()“ in der Schleife über die Inline-Funktion „InputAt(.)“ für jede Eingabe aufzurufen.
• Vermeiden Sie Accept()-Funktionen für das Besuchermuster, indem Sie eine Compiler-Optimierung nutzen.

Fazit

Unser Engagement für die Verbesserung der Kompilierungsgeschwindigkeit von ART hat zu erheblichen Verbesserungen geführt. Android ist dadurch flüssiger und effizienter geworden, was auch zu einer besseren Akkulaufzeit und einem besseren Schutz vor Überhitzung beiträgt. Durch die sorgfältige Identifizierung und Implementierung von Optimierungen haben wir gezeigt, dass erhebliche Verbesserungen der Kompilierungszeit möglich sind, ohne die Arbeitsspeichernutzung oder die Codequalität zu beeinträchtigen.

Unser Weg umfasste die Profilerstellung mit Tools wie pprof, die Bereitschaft zur Iteration und manchmal sogar die Aufgabe weniger fruchtbarer Ansätze. Die gemeinsamen Bemühungen des ART-Teams haben nicht nur die Kompilierungszeit um einen beachtlichen Prozentsatz reduziert, sondern auch die Grundlage für zukünftige Fortschritte geschaffen.

Alle diese Verbesserungen sind im Android-Update zum Jahresende 2025 und für Android 12 und höher über Mainline-Updates verfügbar. Wir hoffen, dass dieser detaillierte Einblick in unseren Optimierungsprozess wertvolle Informationen zu den komplexen Anforderungen und Vorteilen des Compiler-Engineerings liefert.