Articles

Seeing Escape Analysis Working

Posted on

Potresti aver sentito parlare di una fase di analisi del compilatore chiamata escape analysis. Informa un’ottimizzazione chiamata sostituzione scalare di aggregati che rimuove l’allocazione non necessaria di oggetti Java. Trovo che le persone spesso abbiano un fraintendimento di ciò che questa ottimizzazione fa davvero e un sottovalutazione di ciò di cui è capace. Possiamo conoscerlo meglio vedendolo funzionare nella pratica.

Contesto

Mostrerò come il compilatore GraalVM, come parte di GraalVM e configurato per la compilazione just-in-time nella configurazione ospitata, applica l’analisi di escape e la sostituzione scalare degli aggregati. Il compilatore GraalVM è più potente in questo senso rispetto al compilatore just-in-time più comune a cui probabilmente sei abituato, C2 in HotSpot.

Nota che ogni volta che dico compilatore in questo articolo, intendo la compilazione just-in-time, quindi il tipo di compilazione che avviene in fase di runtime nella JVM. Non intendo il compilatore javac.

Mostrerò come il compilatore capisce i nostri programmi di esempio osservando una delle strutture dati che utilizza durante la compilazione, la sua rappresentazione intermedia più alta. Questo è un grafico che cattura il significato di un programma Java in quanto è ottimizzato e trasformato prima della conversione in codice macchina inizia. Probabilmente sembra molto avanzato, ma penso che per la maggior parte delle persone con una certa esperienza di Java sia in realtà un modo abbastanza accessibile per capire cosa sta facendo il compilatore.

Questa rappresentazione intermedia è diversa da un albero di sintassi astratto, o AST, che è una rappresentazione sintattica del testo nel programma. È anche diverso da un grafico di chiamata, che ti dice solo quali metodi chiamano quali altri metodi.

Userò uno strumento chiamato Seafoam, dal team di implementazione del linguaggio di Shopify, per creare diagrammi delle strutture dati scaricate da Graal. È inoltre possibile utilizzare uno strumento chiamato Ideal Graph Visualizer di Oracle Labs.

Terminologia

L’analisi di fuga è un processo di analisi. Rileva se un oggetto è visibile all’esterno di un’unità di compilazione (un’unità di compilazione è di solito un metodo più altri metodi inseriti in esso.) Un oggetto può diventare visibile all’esterno di un’unità di compilazione venendo restituito, o passato come argomento a un altro metodo, o scritto in un campo o simile.

La sostituzione scalare degli aggregati utilizza il risultato dell’analisi di escape e funziona su oggetti che non sfuggono all’unità di compilazione o la sfuggono solo su alcuni rami. Sostituisce gli oggetti (aggregati) con valori semplici (scalari) simili in effetti alle variabili locali. Lo vedremo più concretamente più avanti.

Allocazione degli oggetti

Lavoreremo con una semplice classe Vector che contiene i campi double x e y. Ha un costruttore, getter e un metodo add che restituisce un nuovo oggetto che è questo Vector aggiunto a un altro.

Ho un metodo main che esegue un ciclo e chiama un metodo

sum

che utilizza

add

per sommare due vettori generati casualmente. Il ciclo è lì per ottenere il codice abbastanza caldo da attivare la compilazione just-in-time, la randomizzazione è lì in modo che i valori non siano profilati per essere effettivamente costanti e il metodo sum separato è lì per creare un blocco di codice pulito da guardare quando si guarda a come viene compilato il codice.

Compilerò ed eseguirò questo usando GraalVM CE su Java 8 20.3.0 su macOS su AMD64. Spengo un’ottimizzazione chiamata sostituzione on-stack perché questa ottimizzazione rende la compilazione un po ‘ più complicata e più difficile da capire. Quindi uso l’opzione

dump

di Graal per chiedergli di scaricare le sue strutture di dati di rappresentazione intermedie.

Ora possiamo usare Seafoam per vedere come il compilatore capisce il metodo sum, subito prima che esegua l’analisi di escape. Il file sum.bgv contiene la struttura dati che il compilatore ha scaricato per noi.

% seafoam sum.bgv:14 render

Cosa stiamo vedendo qui? Questo grafico è il modo in cui Graal comprende il metodo sum mentre lo sta compilando. È codice Java, ma libero dai vincoli di una rappresentazione testuale. Le operazioni sono rappresentate come nodi (le caselle, i diamanti e gli ovali) e le relazioni tra le operazioni sono rappresentate come bordi (le frecce). La spessa freccia rossa significa che un’operazione deve avvenire prima di un’altra. La freccia più sottile indica che l’output dell’operazione viene utilizzato come input per un’altra operazione.

Abbiamo detto che il programma è stato liberato dai vincoli di una rappresentazione testuale. Guarda ad esempio l’operazione Aggiungi nel nodo 14. Sappiamo che deve accadere dopo aver caricato i due valori dai due campi x e prima di memorizzare il valore nel campo x nel nodo 19, ma non ci interessa se accade prima o dopo che i due campi y vengono caricati. Nel codice sorgente testuale Java, tutto è scritto in un ordine lineare. Il grafico rilassa questo vincolo e codifica solo i vincoli che la specifica del linguaggio Java richiede effettivamente. Il compilatore è quindi libero di scegliere l’ordine finale in cui viene eseguito tutto.

Leggendo questo grafico, possiamo vedere che creiamo un nuovo Vector, quindi carichiamo i campi x e y dei due oggetti di input, li aggiungiamo insieme e poi li memorizziamo nel nuovo Vector che abbiamo creato prima di restituirlo. Ci sono alcuni dettagli extra nel grafico, come il controllo null, la barriera di campo finale e altro perché questo è un vero grafico del compilatore, ma ignoreremo quelli per questo articolo per renderlo breve.

La cosa fondamentale da vedere qui ora è che c’è un punto preciso in cui viene creato il nuovo oggetto Vector.

Sostituzione scalare di base

Diamo un’occhiata allo stesso metodo subito dopo l’esecuzione dell’analisi di escape e della sostituzione scalare degli aggregati.

% seafoam sum.bgv:15 render

Ora il grafico è stato ancora più rilassato da come appare nel testo. Invece di un’operazione New Vector l’abbiamo ora scomposta in un’operazione generica per allocare un oggetto, prendendo il valore dei campi di quell’oggetto. Non c’è più StoreField qui.

In questo particolare metodo, questo non ha ottenuto nulla di utile – il grafico è stato rilassato ma non ha rivelato alcuna ottimizzazione davvero utile. Questo perché l’unico oggetto che abbiamo allocato ha davvero bisogno di essere allocato perché lascia il metodo. L’analisi di escape è stata eseguita ma l’oggetto è sfuggito, quindi non è stata eseguita alcuna sostituzione scalare degli aggregati.

Per andare oltre, diamo un’occhiata a un metodo che somma tre oggetti Vector.

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

Il grafico prima dell’analisi di escape e della sostituzione scalare degli aggregati ha la stessa struttura del metodo precedente. Abbiamo due operazioni New Vector. Il risultato di a.add(b)viene scritto nel primo nuovo oggetto e quindi letto di nuovo per il successivo .add(c). Possiamo vedere come questo è uno spreco – l’oggetto intermedio non è mai visibile al di fuori dell’unità di compilazione perché non è memorizzato o passato da nessuna parte – quindi perché allocarlo e perché memorizzare i campi in esso che leggiamo immediatamente di nuovo?

Se guardiamo il grafico dopo l’analisi di escape e la sostituzione scalare degli aggregati vediamo che l’intermedio Vector è stato rimosso completamente. C’è solo uno Alloc, non due. L’aggregato dei campi dell’oggetto intermedio è stato sostituito con i valori scalari dei bordi che collegano direttamente il produttore e il consumatore, senza fare un intermedio StoreFielde quindi LoadField.

L’efficacia della sostituzione scalare

Alcuni altri esempi mostreranno come questa ottimizzazione sia un po ‘ più potente di quanto spesso si supponga.

Se sommiamo un array di oggetti Vector creeremo logicamente uno Vector per iterazione.

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

Questo grafico è ora piuttosto complicato, ma il punto chiave è che puoi vedere un’operazione New Vector all’interno del ciclo (all’interno del cerchio formato da spesse frecce rosse.)

Dopo l’analisi di escape parziale e la sostituzione scalare degli aggregati, ora non c’è New Vector all’interno del ciclo. C’è una singola allocazione alla fine per il Vector finale che viene restituito, ei valori per x e y vengono accumulati accumulando valori (i piccoli loop attorno ai nodi 33 e 92 e ai nodi 36 e 93.) Ciò significa che non viene più allocata memoria nel ciclo interno di questo metodo.

A volte le persone parlano di oggetti che non sfuggono a un’unità di compilazione allocata nello stack. Ecco perché questo è un malinteso. Questo metodo somma due oggetti Vector ma restituisce solo il componente x.

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

Prima dell’esecuzione dell’analisi di escape, questo metodo appare esattamente come l’originale sum, tranne che il campo x viene quindi caricato e restituito. Il campo y viene memorizzato ma mai utilizzato e l’intermedio Vector non sfugge all’unità di compilazione.

Dopo l’analisi di escape e la sostituzione scalare degli aggregati, possiamo vedere un punto importante da notare: dopo che l’oggetto è stato sostituito con gli scalari, non c’era alcun consumatore del valore y, quindi il codice per generarlo non aveva nulla per collegarlo al grafico e quindi è stato rimosso.

Se stessimo letteralmente allocando l’oggetto nello stack, memorizzando l’oggetto nello stesso formato solo nella memoria dello stack piuttosto che nella memoria dell’heap, dovremmo comunque generare il valore intermedio y. Non allochiamo l’oggetto da nessuna parte, l’abbiamo sostituito con i bordi del flusso di dati.

Nota che l’allocazione dello stack di oggetti è davvero una cosa, e viene proposta per HotSpot standard e C2, ma è per uno scopo leggermente diverso che non andremo qui per semplicità.

Rispetto all’ottimizzazione manuale

Riscriveresti alcuni di questi metodi per accumulare x e y in variabili locali e non creare oggetti intermedi Vector? Ad esempio, potresti riscrivere sum su un array di Vector oggetti come questo:

Questo grafico è infatti più efficiente del grafico della nostra somma con oggetti intermedi Vector prima dell’analisi di escape. Non c’è allocazione all’interno del ciclo.

Ma se guardiamo al nostro precedente ciclo di somma con oggetti intermedi Vector dopo l’analisi di escape e la sostituzione scalare degli aggregati, sembrano fondamentalmente uguali. Non c’era alcun vantaggio nella riscrittura di questo metodo dalla versione di alto livello con semplici oggetti intermedi Vector alla versione ottimizzata manualmente.

(In realtà forse c’è – la versione ottimizzata manualmente è più veloce da compilare e viene eseguita più rapidamente mentre viene interpretata fino a quando non viene compilata.)

Analisi di escape parziale

Qualcosa che Graal può fare che C2 non può, e un vantaggio chiave di Graal, è l’analisi di escape parziale. Invece di determinare un valore binario se un oggetto sfugge all’unità di compilazione o meno, questo può determinare su quali rami un oggetto sfugge e spostare l’allocazione dell’oggetto solo su quei rami in cui sfugge.

Questo metodo artificioso somma due oggetti Vector e quindi in base a una condizione s lo passa come parametro a un altro metodo chiamato blackhole, che lo fa scappare, oppure aggiunge un terzo vettore e quindi lo restituisce.

L’intermedio Vector memorizzato in x sfugge al primo ramo, ma non al secondo.

Impediamo che blackhole venga inserito specificando -XX:CompileCommand=dontinline,Vector.blackhole.

Prima che venga eseguita l’analisi di escape parziale, possiamo vedere New Vector per x in esecuzione per entrambi i rami.

Dopo l’analisi di fuga parziale e la sostituzione scalare degli aggregati, l’intermedio New Vector è scomparso. Invece, sul ramo in cui sfugge abbiamo l’oggetto Alloc, che fa riferimento ai valori che dovrebbe avere di x e y, e sull’altro ramo in cui l’oggetto non sfugge ai valori per x e y sono usati direttamente.

L’allocazione è stata spostata solo nel ramo in cui è effettivamente necessaria.

Speriamo che tutto ti aiuti a capire quale sia l’analisi di fuga e la sostituzione scalare degli aggregati vedendolo funzionare nella pratica. Inoltre spero che ti mostri che non è davvero l’allocazione dello stack ed è in realtà qualcosa di più potente di quello, e che ti mostri ciò che il Compilatore GraalVM può fare per te.

Ulteriori informazioni

L’algoritmo di analisi di escape parziale di Graal è descritto in Analisi di escape parziale e sostituzione scalare per Java.

Ho scritto di più su questi grafici del compilatore e su come leggerli nella comprensione dei grafici Graal di base.

Autore: Chris Seaton

Chris è un ricercatore (Senior Staff Engineer) presso Shopify, dove lavora sul linguaggio di programmazione Ruby, e un visitatore presso l’Università di Manchester.

In precedenza era un Research Manager presso Oracle Labs Virtual Machine Research Group, dove ha guidato l’implementazione TruffleRuby di Ruby, e ha lavorato su altri progetti di linguaggio e macchine virtuali. Prima di questo ha completato un dottorato di ricerca a Manchester, dove ha studiato linguaggi di programmazione e parallelismo irregolare, e un MEng presso l’Università di Bristol su linguaggi con sintassi e semantica mutabili.

Nel suo tempo libero è capo squadrone del Cheshire Yeomanry squadron del Queen’s Own Yeomanry, lo storico squadrone di cavalleria leggera di riserva del Cheshire.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.