Das Android Runtime (ART)-Team hat die Kompilierungszeit um 18% verkürzt, ohne den kompilierten Code oder Speicher-Regressionen zu beeinträchtigen. Diese Verbesserung war Teil unserer Initiative von 2025, die Kompilierungszeit zu verkürzen, ohne die Speichernutzung oder die Qualität des kompilierten Codes zu beeinträchtigen.

Die Optimierung der Kompilierungszeit ist für ART von entscheidender Bedeutung. Bei der Just-in-Time-Kompilierung (JIT) wirkt sie sich beispielsweise direkt auf die Effizienz von Anwendungen und die Gesamtleistung des Geräts aus. Schnellere Kompilierungen verkürzen die Zeit, bis die Optimierungen wirksam werden, was zu einer reibungsloseren und reaktionsschnelleren Nutzererfahrung führt. Darüber hinaus führen Verbesserungen der Kompilierungszeit sowohl bei JIT als auch bei der Ahead-of-Time-Kompilierung (AOT) zu einem geringeren Ressourcenverbrauch während des Kompilierungsprozesses, was sich positiv auf die Akkulaufzeit und die Wärmeentwicklung des Geräts auswirkt, insbesondere bei Geräten der unteren Preisklasse.

Einige dieser Verbesserungen der Kompilierungszeit wurden im Juni 2025 in der Android-Version eingeführt. Die restlichen Verbesserungen werden in der Android-Version zum Jahresende verfügbar sein. Außerdem können alle Android-Nutzer mit Version 12 und höher diese Verbesserungen über Mainline-Updates erhalten.

Optimierung des Optimierungs-Compilers

Die Optimierung eines Compilers ist immer ein Abwägen von Kompromissen. Geschwindigkeit gibt es nicht kostenlos, man muss etwas dafür aufgeben. Wir haben uns ein sehr klares und anspruchsvolles Ziel gesetzt: den Compiler schneller zu machen, aber ohne Speicher-Regressionen 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 in die Materie einzutauchen, zu recherchieren und clevere Lösungen zu finden, die diese strengen Kriterien erfüllen. Sehen wir uns genauer an, wie wir nach Bereichen suchen, in denen Verbesserungen möglich sind, und wie wir die richtigen Lösungen für die verschiedenen Probleme finden.

Mögliche Optimierungen finden, die sich lohnen

Bevor Sie einen Messwert optimieren können, müssen Sie ihn messen können. Andernfalls können Sie nie sicher sein, ob Sie ihn verbessert haben oder nicht. Glücklicherweise ist die Kompilierungszeit recht konstant, 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 die Wärmeentwicklung Ihres Geräts nicht gedrosselt wird. Außerdem haben wir deterministische Messungen wie Compiler-Statistiken, die uns helfen zu verstehen, was unter der Haube passiert.

Da wir für diese Verbesserungen unsere Entwicklungszeit opferten, wollten wir so schnell wie möglich iterieren. Dazu haben wir eine Reihe repräsentativer Apps (eine Mischung aus eigenen Apps, Apps von Drittanbietern und dem Android-Betriebssystem selbst) verwendet, um Prototypen für Lösungen zu erstellen. Später haben wir mit manuellen und automatisierten Tests in großem Umfang überprüft, ob sich die endgültige Implementierung gelohnt hat.

Mit diesen ausgewählten APKs haben wir eine manuelle Kompilierung lokal 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 Compiler-Phasen oder -Methoden die meiste Zeit in Anspruch nehmen. Wir werden nicht ins Detail gehen, was pprof selbst betrifft. Sie müssen nur wissen, dass ein größerer Balken bedeutet, dass die Kompilierung mehr Zeit in Anspruch genommen hat.

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

Bottom-up-Ansicht eines Profils

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

Sinnvolle Optimierungen implementieren

Wir haben besprochen, wie man misst und wie man erkennt, wo die Zeit verbracht wird. Das ist aber erst der Anfang. Der nächste Schritt besteht darin, die Zeit zu optimieren, die für die Kompilierung aufgewendet wird.

In einem Fall wie dem oben genannten `Kill` würden wir normalerweise untersuchen, wie wir die Knoten durchlaufen, und den Vorgang beschleunigen, indem wir beispielsweise Dinge parallel ausführen oder den Algorithmus selbst verbessern. Tatsächlich haben wir das zuerst versucht. Erst als wir nichts finden konnten, hatten wir einen „Moment mal“-Moment und stellten fest, dass die Lösung darin bestand, (in einigen Fällen) gar nicht zu iterieren. Bei solchen Optimierungen kann man leicht den Wald vor lauter Bäumen nicht sehen.

In anderen Fällen haben wir eine Reihe verschiedener Techniken verwendet, darunter:

• Heuristiken verwenden, um zu entscheiden, ob eine Optimierung keine lohnenswerten Ergebnisse liefert und daher übersprungen werden kann
• Zusätzliche Datenstrukturen verwenden, um berechnete Daten zu cachen
• Die aktuellen Datenstrukturen ändern, um die Geschwindigkeit zu erhöhen
• Ergebnisse verzögert berechnen, um in einigen Fällen Zyklen zu vermeiden
• Die richtige Abstraktion verwenden – unnötige Funktionen können den Code verlangsamen
• Vermeiden, einen häufig verwendeten Pointer durch viele Ladevorgänge zu verfolgen

Woher wissen wir, ob sich die Optimierungen lohnen?

Das ist der Clou: Sie wissen es nicht. Nachdem Sie festgestellt haben, dass ein Bereich viel Kompilierungszeit in Anspruch nimmt, und nachdem Sie Entwicklungszeit investiert haben, um ihn zu verbessern, finden Sie manchmal einfach keine Lösung. Vielleicht gibt es nichts zu tun, die Implementierung dauert zu lange, eine andere Messgröße wird dadurch erheblich beeinträchtigt, die Komplexität der Codebasis steigt usw. Für jede erfolgreiche Optimierung, die Sie in diesem Blogpost sehen, gibt es unzählige andere, die einfach nicht umgesetzt wurden.

Wenn Sie sich in einer ähnlichen Situation befinden, versuchen Sie, abzuschätzen, wie viel Sie die Messgröße verbessern können, indem Sie so wenig Arbeit wie möglich investieren. Das bedeutet in der Reihenfolge:

1. Schätzen Sie anhand von Messwerten, die Sie bereits erhoben haben, oder einfach nach Bauchgefühl.
2. Schätzen Sie anhand eines schnellen und unsauberen Prototyps.
3. Implementieren Sie eine Lösung.

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

Detailliertere Informationen

Sehen wir uns nun einige der Änderungen an, die wir implementiert haben.

Wir haben eine Änderung implementiert, um eine Methode namens FindReferenceInfoOf zu optimieren. Diese Methode führte eine lineare Suche in einem Vektor durch, um einen Eintrag zu finden. Wir haben diese Datenstruktur so aktualisiert, dass sie nach der ID der Anweisung indexiert wird, sodass FindReferenceInfoOf O(1) anstelle von O(n) ist. Außerdem haben wir den Vektor vorab zugewiesen, um eine Größenänderung zu vermeiden. Wir haben den Speicher leicht erhöht, da wir ein zusätzliches Feld hinzufügen mussten, das zählte, wie viele Einträge wir in den Vektor eingefügt haben. Das war aber ein kleiner Kompromiss, da der maximale Speicher nicht gestiegen ist. Dadurch wurde unsere LoadStoreAnalysis-Phase um 34–66% beschleunigt, was wiederum zu einer Verbesserung der Kompilierungszeit um etwa 0,5–1,8% führt.

Wir haben eine benutzerdefinierte Implementierung von HashSet, die wir an mehreren Stellen verwenden. Das Erstellen dieser Datenstruktur hat viel Zeit in Anspruch genommen. Wir haben herausgefunden, warum. Vor vielen Jahren wurde diese Datenstruktur nur an wenigen Stellen verwendet, an denen sehr große HashSets verwendet wurden. Sie wurde so angepasst, dass sie dafür optimiert war. Heutzutage wurde sie jedoch in der entgegengesetzten Richtung verwendet, mit nur wenigen Einträgen und einer kurzen Lebensdauer. Das bedeutete, dass wir Zyklen verschwendeten, indem wir dieses riesige HashSet erstellten, es aber nur für einige Einträge verwendeten, bevor wir es verworfen. Mit dieser Änderung haben wir die Kompilierungszeit um etwa 1, 3–2% verbessert. Ein weiterer Vorteil ist, dass die Speichernutzung um etwa 0,5–1% gesunken ist, da wir nicht mehr so große Datenstrukturen verwenden.

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

Wir haben die Phase, in der die kompilierte Ausgabe geschrieben wird, beschleunigt, indem wir berechnete Werte gecacht haben. Das führte zu einer Verbesserung der gesamten Kompilierungszeit um etwa 1,3–2,8 %. Leider war der zusätzliche Verwaltungsaufwand zu hoch und unsere automatisierten Tests haben uns auf die Speicher-Regression aufmerksam gemacht. Später haben wir uns denselben Code noch einmal angesehen und eine neue Version implementiert, die nicht nur die Speicher-Regression behoben, sondern auch die Kompilierungszeit um weitere 0,5–1,8 % verbessert hat. Bei dieser zweiten Änderung mussten wir den Code umgestalten und neu überdenken, wie diese Phase funktionieren sollte, um eine der beiden Datenstrukturen zu entfernen.

In unserem Optimierungs-Compiler gibt es eine Phase, in der Funktionsaufrufe inline ausgeführt werden, um die Leistung zu verbessern. Um auszuwählen, welche Methoden inline ausgeführt werden sollen, verwenden wir sowohl Heuristiken, bevor wir Berechnungen durchführen, als auch abschließende Überprüfungen, nachdem wir die Arbeit erledigt haben, aber kurz bevor wir die Inline-Ausführung abschließen. Wenn eine dieser Überprüfungen ergibt, dass sich die Inline-Ausführung nicht lohnt (z. B. weil zu viele neue Anweisungen hinzugefügt würden), führen wir den Methodenaufruf nicht inline aus.

Wir haben zwei Überprüfungen aus der Kategorie „Abschließende Überprüfungen“ in die Kategorie „Heuristik“ verschoben, um abzuschätzen, ob eine Inline-Ausführung erfolgreich sein wird oder nicht, bevor wir zeitaufwendige Berechnungen durchführen. 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 ausgeführten Vorgänge abdecken, ohne die Leistung zu beeinträchtigen. Eine dieser neuen Heuristiken betraf die erforderlichen DEX-Register (Verbesserung um etwa 0,2–1,3 %) und die andere die Anzahl der Anweisungen (Verbesserung um etwa 2 %).

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

Außerdem wurde die BitVectorView-Klasse für den zugrunde liegenden Speichertyp als Vorlage verwendet (anstatt immer uint32_t wie beim alten BitVector zu verwenden). Dadurch können bei einigen Vorgängen, z. B. Union(), auf 64-Bit-Plattformen doppelt so viele Bits gleichzeitig verarbeitet werden. Die Stichproben der betroffenen Funktionen wurden beim Kompilieren des Android-Betriebssystems insgesamt um mehr als 1% reduziert. Das wurde durch mehrere Änderungen erreicht [1, 2, 3, 4, 5, 6]

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

• Verwaltungsaufwand hinzufügen, um die Kompilierungszeiten um etwa 0,6–1,6 % zu verbessern.
• Daten nach Bedarf berechnen, um Zyklen zu vermeiden, wenn möglich.
• Code umgestalten, um die Vorabberechnung zu überspringen, wenn sie nicht verwendet wird.
• Einige abhängige Ladeketten vermeiden, wenn der Allocator problemlos von anderen Stellen abgerufen werden kann.
• Ein weiterer Fall, in dem eine Überprüfung hinzugefügt wurde, um unnötige Arbeit zu vermeiden.
• Häufige Verzweigungen nach dem Registertyp (Core/FP) im Register-Allocator vermeiden.
• Sicherstellen, dass einige Arrays initialisiert werden zur Kompilierungszeit. Sich nicht darauf verlassen, dass Clang das erledigt.
• Einige Schleifen bereinigen. Bereichsschleifen verwenden, die von Clang besser optimiert werden können, da die internen Pointer des Containers aufgrund von Nebeneffekten der Schleife nicht neu geladen werden müssen. Vermeiden, die virtuelle Funktion `HInstruction::GetInputRecords()` in der Schleife über die inline ausgeführte Funktion `InputAt(.)` für jede Eingabe aufzurufen.
• Die Accept()-Funktionen für das Visitor-Muster vermeiden, indem eine Compiler-Optimierung genutzt wird.

Fazit

Unser Engagement für die Verbesserung der Kompilierungszeit von ART hat zu erheblichen Verbesserungen geführt, wodurch Android flüssiger und effizienter geworden ist und gleichzeitig die Akkulaufzeit und die Wärmeentwicklung des Geräts verbessert wurden. Durch die sorgfältige Identifizierung und Implementierung von Optimierungen haben wir gezeigt, dass erhebliche Verbesserungen der Kompilierungszeit möglich sind, ohne die Speichernutzung oder die Codequalität zu beeinträchtigen.

Unser Weg umfasste die Profilerstellung mit Tools wie pprof, die Bereitschaft zur Iteration und manchmal sogar das Aufgeben weniger vielversprechender Ansätze. Die gemeinsamen Bemühungen des ART-Teams haben nicht nur die Kompilierungszeit um einen bemerkenswerten Prozentsatz verkürzt, sondern auch die Grundlage für zukünftige Fortschritte gelegt.

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 über die Komplexität und die Vorteile der Compiler-Entwicklung bietet.