Articles

Sehen Sie, wie die Escape-Analyse funktioniert

Posted on

Möglicherweise haben Sie von einer Compiler-Analysephase namens Escape Analysis gehört. Es ist eine Optimierung namens skalarer Ersatz von Aggregaten, die unnötige Zuweisung von Java-Objekten entfernt. Ich finde, dass die Leute oft ein Missverständnis darüber haben, was diese Optimierung wirklich tut, und eine Unterschätzung dessen, wozu sie fähig ist. Wir können es besser wissen, wenn wir sehen, wie es in der Praxis funktioniert.

Kontext

Ich werde zeigen, wie der GraalVM-Compiler als Teil von GraalVM und konfiguriert für Just-in-Time-Kompilierung in gehosteter Konfiguration Escape-Analyse und skalaren Ersatz von Aggregaten anwendet. Der GraalVM-Compiler ist in dieser Hinsicht leistungsfähiger als der gängigste Just-in-Time-Compiler, an den Sie wahrscheinlich gewöhnt sind, insbesondere C2.

Beachten Sie, dass ich jedes Mal, wenn ich in diesem Artikel Compiler sage, eine Just-in-Time-Kompilierung meine, also die Art der Kompilierung, die zur Laufzeit in der JVM stattfindet. Ich meine nicht den javac Compiler.

Ich werde zeigen, wie der Compiler unsere Beispielprogramme versteht, indem ich mir eine der Datenstrukturen ansehe, die er während der Kompilierung verwendet, seine höhere Zwischendarstellung. Dies ist ein Diagramm, das die Bedeutung eines Java-Programms erfasst, während es optimiert und transformiert wird, bevor die Konvertierung in Maschinencode beginnt. Das klingt wahrscheinlich sehr fortgeschritten, aber ich denke, für die meisten Leute mit etwas Erfahrung mit Java ist es eigentlich eine ziemlich zugängliche Art zu verstehen, was der Compiler tut.

Diese Zwischendarstellung unterscheidet sich von einem abstrakten Syntaxbaum oder AST, der eine syntaktische Darstellung des Textes in Ihrem Programm darstellt. Es unterscheidet sich auch von einem Aufrufdiagramm, das nur angibt, welche Methoden welche anderen Methoden aufrufen.

Ich werde ein Tool namens Seafoam vom Sprachimplementierungsteam von Shopify verwenden, um Diagramme der aus Graal abgelegten Datenstrukturen zu erstellen. Sie können auch ein Tool namens Ideal Graph Visualizer von Oracle Labs verwenden.

Terminologie

Escape-Analyse ist ein Analyseprozess. Es erkennt, ob ein Objekt außerhalb einer Kompilierungseinheit sichtbar ist (eine Kompilierungseinheit ist normalerweise eine Methode plus alle anderen darin eingebetteten Methoden.) Ein Objekt kann außerhalb einer Kompilierungseinheit sichtbar werden, indem es zurückgegeben oder als Argument an eine andere Methode übergeben oder in ein Feld oder ähnliches geschrieben wird.

Das skalare Ersetzen von Aggregaten verwendet das Ergebnis der Escape-Analyse und arbeitet mit Objekten, die der Kompilierungseinheit nicht oder nur in einigen Zweigen entkommen. Es ersetzt Objekte (Aggregate) durch einfache Werte (Skalare), die in ihrer Wirkung lokalen Variablen ähneln. Wir werden das später konkreter sehen.

Objektzuordnung

Wir arbeiten mit einer einfachen Vector Klasse, die double x und y Felder enthält. Es verfügt über einen Konstruktor, Getter und eine add -Methode, die ein neues Objekt zurückgibt, bei dem es sich um dieses Vector handelt, das einem anderen hinzugefügt wurde.

Ich habe eine main -Methode, die eine Schleife ausführt und eine

sum

-Methode aufruft, die

add

verwendet, um zwei zufällig generierte Vektoren zu summieren. Die Schleife ist da, um den Code heiß genug zu machen, um eine Just-in-Time-Kompilierung auszulösen, die Randomisierung ist da, damit die Werte nicht so profiliert werden, dass sie effektiv konstant sind, und die separate sum -Methode ist da, um einen ordentlichen Codeblock zu erstellen Schauen Sie sich an, wie Code kompiliert wird.

Ich werde dies mit GraalVM CE auf Java 8 20.3.0 unter macOS auf AMD64 kompilieren und ausführen. Ich deaktiviere eine Optimierung namens On-Stack-Replacement, da diese Optimierung die Kompilierung etwas komplizierter und verständlicher macht. Ich benutze dann Graals

dump

Option, um es zu bitten, seine Zwischenrepräsentationsdatenstrukturen auszugeben.

Wir können jetzt Seafoam verwenden, um zu sehen, wie der Compiler die sum -Methode versteht, kurz bevor sie die Escape-Analyse ausführt. Die Datei sum.bgv enthält die Datenstruktur, die der Compiler für uns ausgegeben hat.

% seafoam sum.bgv:14 render

Was sehen wir hier? Dieses Diagramm ist die Art und Weise, wie Graal die sum -Methode versteht, während sie kompiliert wird. Es ist Java-Code, aber frei von den Einschränkungen einer textuellen Darstellung. Operationen werden als Knoten (die Kästchen, Rauten und Ovale) und die Beziehungen zwischen Operationen als Kanten (die Pfeile) dargestellt. Der dicke rote Pfeil bedeutet, dass eine Operation vor der anderen stattfinden muss. Der dünnere Pfeil bedeutet, dass die Ausgabe der Operation als Eingabe für eine andere Operation verwendet wird.

Wir sagten, das Programm sei von den Einschränkungen einer Textdarstellung befreit. Sehen Sie sich zum Beispiel die Add-Operation in Knoten 14 an. Wir wissen, dass dies geschehen muss, nachdem wir die beiden Werte aus den beiden x -Feldern geladen haben und bevor wir den Wert im Feld x in Knoten 19 speichern, aber es ist uns egal, ob dies vor oder nach dem Laden der beiden y -Felder geschieht. Im Java-Textquellcode wird alles in einer linearen Reihenfolge geschrieben. Das Diagramm lockert diese Einschränkung und codiert nur die Einschränkungen, die die Java-Sprachspezifikation tatsächlich erfordert. Der Compiler kann dann die endgültige Reihenfolge auswählen, in der alles ausgeführt wird.

Wenn wir dieses Diagramm lesen, können wir sehen, dass wir ein neues Vector erstellen, dann die Felder x und y der beiden Eingabeobjekte laden, sie addieren und dann in dem neuen Vector speichern, das wir erstellt haben, bevor wir es zurückgeben. Es gibt einige zusätzliche Details in der Grafik, wie die null -Prüfung, die endgültige Feldbarriere und mehr, da dies eine echte Compiler-Grafik ist, aber wir werden diese für diesen Artikel ignorieren, um sie kurz zu halten.

Das Wichtigste, was Sie hier sehen können, ist, dass es einen bestimmten Punkt gibt, an dem das neue Vector -Objekt erstellt wird.

Grundlegender skalarer Ersatz

Schauen wir uns die gleiche Methode direkt nach der Escape-Analyse und dem skalaren Austausch von Aggregaten an.

% seafoam sum.bgv:15 render

Jetzt wurde das Diagramm noch weiter von der Darstellung im Text gelockert. Anstelle einer New Vector -Operation haben wir sie jetzt in eine generische Operation zerlegt, um ein Objekt zuzuweisen, wobei der Wert der Felder dieses Objekts verwendet wird. Hier gibt es keine StoreField mehr.

In dieser speziellen Methode hat dies nichts Nützliches erreicht – das Diagramm wurde gelockert, aber es wurden keine wirklich nützlichen Optimierungen angezeigt. Das liegt daran, dass das einzige Objekt, das wir zugewiesen haben, wirklich zugewiesen werden muss, weil es die Methode verlässt. Die Escape-Analyse wurde ausgeführt, aber das Objekt ist entkommen, sodass kein skalarer Ersatz von Aggregaten erfolgte.

Um dies weiter zu führen, schauen wir uns eine Methode an, die drei Vector Objekte summiert.

private static Vector sum(Vector a, Vector b, Vector c) {return a.add(b).add(c);}

Das Diagramm vor der Analyse und dem skalaren Ersetzen von Aggregaten hat die gleiche Struktur wie die vorherige Methode. Wir haben zwei New Vector Operationen. Das Ergebnis von a.add(b) wird in das erste neue Objekt geschrieben und dann für das nachfolgende .add(c) erneut ausgelesen. Wir können sehen, wie verschwenderisch dies ist – das Zwischenobjekt ist außerhalb der Kompilierungseinheit nie sichtbar, weil es nirgendwo gespeichert oder übergeben wird – warum also zuweisen und warum Felder darin speichern, die wir sofort wieder auslesen?

Wenn wir uns die Grafik nach der Analyse und dem skalaren Ersetzen von Aggregaten ansehen, sehen wir, dass das Zwischenprodukt Vector vollständig entfernt wurde. Es gibt nur einen Alloc, nicht zwei. Das Aggregat der Felder des Zwischenobjekts wurde durch die Skalarwerte von Kanten ersetzt, die den Produzenten und den Konsumenten direkt verbinden, ohne ein Zwischenprodukt StoreField und dann LoadField .

Die Wirksamkeit des Skalarersatzes

Ein paar weitere Beispiele werden zeigen, wie diese Optimierung etwas leistungsfähiger ist, als oft angenommen.

Wenn wir ein Array von Vector Objekten summieren, erstellen wir logisch ein Vector pro Iteration.

private static Vector sum(Vector first, Vector... rest) {Vector sum = first;for (Vector vector : rest) {sum = sum.add(vector);}return sum;}

Dieses Diagramm ist jetzt ziemlich kompliziert, aber der entscheidende Punkt ist, dass Sie eine New Vector -Operation innerhalb der Schleife sehen können (innerhalb des Kreises aus dicken roten Pfeilen.)

Nach partieller Escape-Analyse und skalarem Ersetzen von Aggregaten gibt es jetzt kein New Vector innerhalb der Schleife. Am Ende gibt es eine einzige Zuweisung für das finale Vector, das zurückgegeben wird, und die Werte für x und y werden durch Akkumulieren von Werten aufgebaut (die kleinen Schleifen um die Knoten 33 und 92 sowie die Knoten 36 und 93.) Dies bedeutet, dass in der inneren Schleife dieser Methode kein Speicher mehr zugewiesen wird.

Manchmal wird über Objekte gesprochen, die einer Kompilierungseinheit nicht entkommen, die auf dem Stapel zugewiesen wird. Deshalb ist das ein Missverständnis. Diese Methode summiert zwei Vector -Objekte, gibt jedoch nur die x -Komponente zurück.

private static double sumX(Vector a, Vector b) {return a.add(b).getX();}

Bevor die Escape-Analyse ausgeführt wird, sieht diese Methode genau wie die ursprüngliche sum aus, außer dass das x -Feld dann geladen und zurückgegeben wird. Das Feld y wird gespeichert, aber nie verwendet, und das Zwischenelement Vector entgeht der Kompilierungseinheit nicht.

Nach der Escape-Analyse und dem skalaren Ersetzen von Aggregaten können wir einen wichtigen Punkt feststellen: Nachdem das Objekt durch Skalare ersetzt wurde, gab es keinen Verbraucher des Werts y, sodass der zu generierende Code nichts hatte, um ihn mit dem Diagramm zu verbinden, und so wurde es entfernt.

Wenn wir das Objekt buchstäblich auf dem Stapel zuweisen und das Objekt im selben Format nur im Stapelspeicher und nicht im Heapspeicher speichern würden, müssten wir immer noch den Zwischenwert y generieren. Wir weisen das Objekt nirgendwo zu – wir haben es stattdessen durch Datenflusskanten ersetzt.

Beachten Sie, dass die Stapelzuweisung von Objekten wirklich eine Sache ist und für Standard-HotSpot und C2 vorgeschlagen wird, aber für einen etwas anderen Zweck, auf den wir hier der Einfachheit halber nicht eingehen werden.

Im Vergleich zur manuellen Optimierung

Würden Sie einige dieser Methoden neu schreiben, um die x und y in lokalen Variablen zu akkumulieren und keine Vector Zwischenobjekte zu erstellen? Könnten Sie beispielsweise sum über ein Array von Vector Objekten wie folgt umschreiben:

Dieser Graph ist in der Tat effizienter als der Graph unserer Summe mit intermediären Vector Objekten vor der Escape-Analyse. Es gibt keine Zuordnung innerhalb der Schleife.

Wenn wir jedoch nach der Escape-Analyse und dem skalaren Ersetzen von Aggregaten auf unsere vorherige Summenschleife mit intermediären Vector Objekten zurückblicken, sehen sie im Grunde gleich aus. Es war kein Vorteil, diese Methode von der High-Level-Version mit einfachen intermediate Vector -Objekten in die manuell optimierte Version umzuschreiben.

(Nun, vielleicht gibt es das – die manuell optimierte Version ist schneller zu kompilieren und läuft schneller, während sie interpretiert wird, bis sie kompiliert ist.)

Partielle Escape-Analyse

Etwas, das Graal kann, was C2 nicht kann, und ein wesentlicher Vorteil von GraalVM ist die partielle Escape-Analyse. Anstatt einen Binärwert zu bestimmen, ob ein Objekt der Kompilierungseinheit entkommt oder nicht, kann dies bestimmen, auf welchen Zweigen ein Objekt ihm entgeht, und die Zuordnung des Objekts nur zu den Zweigen verschieben, in denen es entweicht.

Diese erfundene Methode summiert zwei Vector Objekte und übergibt sie dann basierend auf einer Bedingung s entweder als Parameter an eine andere Methode namens blackhole , wodurch sie entkommen kann, oder sie fügt einen dritten Vektor hinzu und gibt ihn dann zurück.

Der in x gespeicherte Zwischenzweig Vector entweicht im ersten Zweig, aber nicht im zweiten.

Wir verhindern, dass blackhole inline ist, indem wir -XX:CompileCommand=dontinline,Vector.blackhole angeben.

Bevor die partielle Escape-Analyse ausgeführt wird, können wir sehen, dass New Vector für x für beide Zweige ausgeführt wird.

Nach partieller Escape-Analyse und skalarem Austausch von Aggregaten ist das Zwischenprodukt New Vector verschwunden. Stattdessen haben wir in dem Zweig, in dem es entweicht, das Objekt Alloc , das auf die Werte verweist, die es von x und y haben sollte, und in dem anderen Zweig, in dem das Objekt nicht entweicht, die Werte für x und y werden nur direkt verwendet.

Die Zuordnung wurde nur in den Zweig verschoben, in dem sie tatsächlich benötigt wird.

Hoffentlich hilft Ihnen das alles zu verstehen, was Escape-Analyse und skalarer Ersatz von Aggregaten sind, indem Sie sehen, wie es in der Praxis funktioniert. Ich hoffe auch, dass es Ihnen zeigt, dass es sich nicht wirklich um eine Stapelzuweisung handelt und tatsächlich etwas Leistungsfähigeres ist, und dass es Ihnen zeigt, was der GraalVM-Compiler zusätzlich für Sie tun kann.

Weitere Informationen

Graal’s partial escape analysis algorithm is described in Partial Escape Analysis and Scalar Replacement for Java.

Ich habe mehr über diese Compiler-Graphen geschrieben und wie man sie in Understanding Basic Graal Graphs liest.

Autor: Chris Seaton

Chris ist Forscher (Senior Staff Engineer) bei Shopify, wo er an der Programmiersprache Ruby arbeitet, und Besucher an der University of Manchester.

Er war früher Research Manager bei der Oracle Labs Virtual Machine Research Group, wo er die TruffleRuby-Implementierung von Ruby leitete und an anderen Sprach- und Virtual Machine-Projekten arbeitete. Zuvor promovierte er in Manchester, wo er Programmiersprachen und unregelmäßige Parallelität erforschte, und an der University of Bristol über Sprachen mit veränderlicher Syntax und Semantik.

In seiner Freizeit ist er Geschwaderführer des Cheshire Yeomanry Squadron der Queen’s Own Yeomanry, Cheshires Historic Reserve Light Cavalry Squadron.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.