Produktneuheiten

18% schnellere Kompilierungen, 0% Kompromisse

Lesezeit: 8 Minuten
Santiago Aboy Solanes & Vladimír Marko

Das Android Runtime (ART)-Team hat die Kompilierungszeit um 18% reduziert, ohne den kompilierten Code oder Speicher-Regressionen zu beeinträchtigen. Diese Verbesserung war Teil unserer Initiative für 2025, die Kompilierdauer zu verkürzen, ohne die Arbeitsspeichernutzung 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 Android eingeführt, die übrigen sind im Release zum Jahresende von Android verfügbar. 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. 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 gründlich 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

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 Handvoll 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 lokal eine manuelle Kompilierung ausgelöst, ein Profil der Kompilierung erstellt und mit pprof visualisiert, wo wir unsere Zeit verbringen.

image.png

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 am meisten Zeit in Anspruch nehmen. Wir werden nicht im Detail auf pprof eingehen. 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 am meisten 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.

image.png

Bottom-up-Ansicht eines Profils

In unserem Optimierungs-Compiler gibt es eine Phase namens Global Value Numbering (GVN). Sie müssen sich keine Gedanken darüber machen, 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 sie von 1,023% auf etwa 0,3% sinkt und die Laufzeit von GVN um etwa 15 % verbessert wird.

Sinnvolle Optimierungen implementieren

Wir haben beschrieben, wie man misst und wie man erkennt, wo die Zeit verbracht wird. Das ist aber erst der Anfang. Im nächsten Schritt geht es darum, 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 das schneller tun, indem wir beispielsweise Dinge parallel ausführen oder den Algorithmus selbst verbessern. Tatsächlich haben wir das zuerst versucht. Erst als wir nichts gefunden haben, was wir tun 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 Zeiger durch viele Lasten 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, sie verschlechtert einen anderen Messwert erheblich, erhöht die Komplexität der Codebasis usw. Für jede erfolgreiche Optimierung, die Sie in diesem Blogpost sehen, gibt es unzählige andere, die einfach nicht zustande gekommen sind.

Wenn Sie sich in einer ähnlichen Situation befinden, versuchen Sie zu schätzen, wie viel Sie den Messwert verbessern können, indem Sie so wenig Arbeit wie möglich investieren. Das bedeutet in der Reihenfolge:

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

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

Detailliertere Informationen

Sehen wir uns 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 kleines Opfer, 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 und wir haben herausgefunden, warum. Vor vielen Jahren wurde diese Datenstruktur nur an wenigen Stellen verwendet, die sehr große HashSets nutzten, und sie wurde für diesen Zweck optimiert. Heutzutage wurde sie jedoch in umgekehrter 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 haben. Mit dieser Änderung haben wir die Kompilierungszeit um etwa 1, 3–2% verbessert. Ein weiterer Vorteil ist, dass die Arbeitsspeichernutzung um etwa 0,5–1% gesunken ist, da wir nicht mehr so große Datenstrukturen verwendet haben wie zuvor.

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. Erst als wir uns die Profile in pprof angesehen haben, haben wir bemerkt, dass diese Methoden viele Datenstrukturen erstellt und zerstört haben, 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, was zu einer Verbesserung der gesamten Kompilierungszeit um etwa 1,3–2,8% geführt hat. 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 dabei festgestellt wird, 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 zu schä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 Fälle abdecken, ohne die Leistung zu beeinträchtigen. Eine dieser neuen Heuristiken betraf die benötigten 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 Laufzeit-Bereichsüberprüfungen vermieden und die Erstellung der Bitvektor-Objekte beschleunigt.

Außerdem wurde die BitVectorView-Klasse für den zugrunde liegenden Speichertyp als Vorlage erstellt (anstatt immer uint32_t wie beim alten 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. 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:

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 auch 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 Kompilierdauer 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 das Aufgeben weniger vielversprechender Ansätze. Die gemeinsamen Bemühungen des ART-Teams haben nicht nur die Kompilierungszeit um einen bemerkenswerten Prozentsatz reduziert, 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.

Verfasst von:

Weiterlesen