Rendi Java veloce: ottimizza!

Secondo il pioniere dell'informatica Donald Knuth, "L'ottimizzazione prematura è la radice di tutti i mali". Qualsiasi articolo sull'ottimizzazione deve iniziare sottolineando che di solito ci sono più ragioni per non ottimizzare che per ottimizzare.

  • Se il tuo codice funziona già, ottimizzarlo è un modo sicuro per introdurre bug nuovi, e possibilmente sottili

  • L'ottimizzazione tende a rendere il codice più difficile da comprendere e mantenere

  • Alcune delle tecniche qui presentate aumentano la velocità riducendo l'estensibilità del codice

  • L'ottimizzazione del codice per una piattaforma può effettivamente peggiorare la situazione su un'altra piattaforma

  • È possibile dedicare molto tempo all'ottimizzazione, con scarso guadagno in termini di prestazioni, e il codice può risultare offuscato

  • Se sei eccessivamente ossessionato dall'ottimizzazione del codice, le persone ti chiameranno un nerd alle tue spalle

Prima di eseguire l'ottimizzazione, è necessario valutare attentamente se è necessario ottimizzare affatto. L'ottimizzazione in Java può essere un obiettivo sfuggente poiché gli ambienti di esecuzione variano. L'uso di un algoritmo migliore probabilmente produrrà un aumento delle prestazioni maggiore rispetto a qualsiasi quantità di ottimizzazioni di basso livello ed è più probabile che fornisca un miglioramento in tutte le condizioni di esecuzione. Di norma, è necessario considerare le ottimizzazioni di alto livello prima di eseguire le ottimizzazioni di basso livello.

Allora perché ottimizzare?

Se è un'idea così cattiva, perché ottimizzare? Bene, in un mondo ideale non lo faresti. Ma la realtà è che a volte il problema più grande con un programma è che richiede semplicemente troppe risorse e queste risorse (memoria, cicli della CPU, larghezza di banda di rete o una combinazione) possono essere limitate. È probabile che i frammenti di codice che si verificano più volte in un programma dipendono dalle dimensioni, mentre il codice con molte iterazioni di esecuzione può essere sensibile alla velocità.

Rendi Java veloce!

Essendo un linguaggio interpretato con un bytecode compatto, la velocità o la mancanza di esso è ciò che più spesso si presenta come un problema in Java. Vedremo principalmente come rendere Java più veloce piuttosto che adattarlo a uno spazio più piccolo, anche se indicheremo dove e come questi approcci influenzano la memoria o la larghezza di banda della rete. L'attenzione si concentrerà sul linguaggio di base piuttosto che sulle API Java.

A proposito, una cosa che non discuteremo qui è l'uso di metodi nativi scritti in C o in assembly. Sebbene l'utilizzo di metodi nativi possa fornire il massimo incremento delle prestazioni, lo fa a scapito dell'indipendenza dalla piattaforma Java. È possibile scrivere sia una versione Java di un metodo che versioni native per piattaforme selezionate; questo porta ad un aumento delle prestazioni su alcune piattaforme senza rinunciare alla possibilità di funzionare su tutte le piattaforme. Ma questo è tutto quello che dirò sull'argomento della sostituzione di Java con il codice C. (Per ulteriori informazioni su questo argomento, vedere il suggerimento Java, "Scrivere metodi nativi".) Il nostro obiettivo in questo articolo è come rendere veloce Java.

90/10, 80/20, rifugio, rifugio, escursione!

Di norma, il 90 percento del tempo di esecuzione di un programma viene impiegato per eseguire il 10 percento del codice. (Alcune persone usano la regola dell'80% / 20%, ma la mia esperienza di scrittura e ottimizzazione di giochi commerciali in diverse lingue negli ultimi 15 anni ha dimostrato che la formula del 90% / 10% è tipica dei programmi affamati di prestazioni poiché poche attività tendono a essere eseguita con grande frequenza.) L'ottimizzazione dell'altro 90 percento del programma (dove è stato speso il 10 percento del tempo di esecuzione) non ha alcun effetto evidente sulle prestazioni. Se tu fossi in grado di fare in modo che il 90% del codice venga eseguito due volte più velocemente, il programma sarebbe solo il 5% più veloce. Quindi il primo compito nell'ottimizzazione del codice è identificare il 10 percento (spesso è inferiore a questo) del programma che consuma la maggior parte del tempo di esecuzione. Questo non èt sempre dove ti aspetti che sia.

Tecniche generali di ottimizzazione

Esistono diverse tecniche di ottimizzazione comuni che si applicano indipendentemente dalla lingua utilizzata. Alcune di queste tecniche, come l'allocazione dei registri globali, sono strategie sofisticate per allocare le risorse della macchina (ad esempio, i registri della CPU) e non si applicano ai bytecode Java. Ci concentreremo sulle tecniche che fondamentalmente implicano la ristrutturazione del codice e la sostituzione di operazioni equivalenti all'interno di un metodo.

Riduzione della forza

La riduzione della forza si verifica quando un'operazione viene sostituita da un'operazione equivalente che viene eseguita più velocemente. L'esempio più comune di riduzione della forza è l'utilizzo dell'operatore di spostamento per moltiplicare e dividere gli interi per una potenza di 2. Ad esempio, x >> 2può essere utilizzato al posto di x / 4e x << 1sostituisce x * 2.

Eliminazione di sottoespressioni comuni

L'eliminazione delle sottoespressioni comuni rimuove i calcoli ridondanti. Invece di scrivere

double x = d * (lim / max) * sx; double y = d * (lim / max) * sy;

la sottoespressione comune viene calcolata una volta e utilizzata per entrambi i calcoli:

double depth = d * (lim / max); double x = depth * sx; double y = depth * sy;

Movimento del codice

Il movimento del codice sposta il codice che esegue un'operazione o calcola un'espressione il cui risultato non cambia o è invariante . Il codice viene spostato in modo che venga eseguito solo quando il risultato può cambiare, invece di essere eseguito ogni volta che il risultato è richiesto. Questo è più comune con i loop, ma può anche coinvolgere il codice ripetuto a ogni invocazione di un metodo. Di seguito è riportato un esempio di movimento del codice invariante in un ciclo:

for (int i = 0; i < x.length; i++) x [i] * = Math.PI * Math.cos (y); 

diventa

double picosy = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i++)x [i] * = picosy;

Anelli di srotolamento

Lo srotolamento dei cicli riduce il sovraccarico del codice di controllo del ciclo eseguendo più di un'operazione ogni volta attraverso il ciclo e di conseguenza eseguendo meno iterazioni. Lavorando dall'esempio precedente, se sappiamo che la lunghezza di x[]è sempre un multiplo di due, potremmo riscrivere il ciclo come:

double picosy = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i += 2) {x [i] * = picosy; x [i + 1] * = picosy; }

In pratica, lo srotolamento di cicli come questo - in cui il valore dell'indice del ciclo viene utilizzato all'interno del ciclo e deve essere incrementato separatamente - non produce un aumento apprezzabile della velocità in Java interpretato perché i bytecode mancano di istruzioni per combinare in modo efficiente il " +1"nell'indice dell'array.

Tutti i suggerimenti per l'ottimizzazione in questo articolo incorporano una o più delle tecniche generali elencate sopra.

Mettere il compilatore al lavoro

I moderni compilatori C e Fortran producono codice altamente ottimizzato. I compilatori C ++ generalmente producono codice meno efficiente, ma sono ancora ben avviati verso la produzione di codice ottimale. Tutti questi compilatori hanno attraversato molte generazioni sotto l'influenza di una forte concorrenza di mercato e sono diventati strumenti finemente affinati per spremere fino all'ultima goccia di prestazioni dal codice ordinario. Quasi certamente usano tutte le tecniche di ottimizzazione generali presentate sopra. Ma ci sono ancora molti trucchi per fare in modo che i compilatori generino codice efficiente.

javac, JIT e compilatori di codice nativo

Il livello di ottimizzazione che viene javaceseguito durante la compilazione del codice a questo punto è minimo. L'impostazione predefinita prevede le seguenti operazioni:

  • Ripiegamento costante: il compilatore risolve tutte le espressioni costanti in modo tale da i = (10 *10)eseguire la compilazione i = 100.

  • Branch Folding (la maggior parte delle volte): gotosi evitano bytecode non necessari .

  • Eliminazione limitata del codice morto: non viene prodotto alcun codice per istruzioni come if(false) i = 1.

Il livello di ottimizzazione fornito da javac dovrebbe migliorare, probabilmente drasticamente, man mano che il linguaggio matura e i fornitori di compilatori iniziano a competere seriamente sulla base della generazione di codice. Java solo ora sta ottenendo compilatori di seconda generazione.

Poi ci sono compilatori just-in-time (JIT) che convertono i bytecode Java in codice nativo in fase di esecuzione. Molti sono già disponibili e, sebbene possano aumentare notevolmente la velocità di esecuzione del programma, il livello di ottimizzazione che possono eseguire è limitato perché l'ottimizzazione avviene in fase di esecuzione. Un compilatore JIT è più interessato a generare il codice rapidamente che a generare il codice più veloce.

I compilatori di codice nativo che compilano Java direttamente in codice nativo dovrebbero offrire le massime prestazioni ma a scapito dell'indipendenza dalla piattaforma. Fortunatamente, molti dei trucchi presentati qui saranno realizzati dai futuri compilatori, ma per ora ci vuole un po 'di lavoro per ottenere il massimo dal compilatore.

javacoffre un'opzione di prestazioni che puoi abilitare: invocare l' -Oopzione per far sì che il compilatore inline alcune chiamate di metodo:

javac -O MyClass

L'inlining di una chiamata al metodo inserisce il codice per il metodo direttamente nel codice che effettua la chiamata al metodo. Ciò elimina il sovraccarico della chiamata al metodo. Per un metodo piccolo questo sovraccarico può rappresentare una percentuale significativa del suo tempo di esecuzione. Si noti che solo i metodi dichiarati come sia private, statico finalpossono essere considerate per inlining, perché solo questi metodi sono staticamente risolti dal compilatore. Inoltre, i synchronizedmetodi non saranno inline. Il compilatore inserirà solo metodi piccoli in genere costituiti da una o due righe di codice.

Sfortunatamente, le versioni 1.0 del compilatore javac hanno un bug che genera codice che non può passare il verificatore bytecode quando -Oviene utilizzata l' opzione. Questo problema è stato risolto in JDK 1.1. (Il verificatore bytecode controlla il codice prima che ne sia consentito l'esecuzione per assicurarsi che non violi alcuna regola Java.) Metterà in linea metodi che fanno riferimento a membri della classe inaccessibili alla classe chiamante. Ad esempio, se le seguenti classi vengono compilate insieme utilizzando l' -Oopzione

classe A {int statico privato x = 10; public static void getX () {return x; }} classe B {int y = A.getX (); }

la chiamata ad A.getX () nella classe B verrà inserita nella classe B come se B fosse stata scritta come:

classe B {int y = Ax; }

Tuttavia, questo farà sì che la generazione di bytecode acceda alla variabile Ax privata che verrà generata nel codice di B. Questo codice verrà eseguito correttamente, ma poiché viola le restrizioni di accesso di Java, verrà contrassegnato dal verificatore con una IllegalAccessErrorla prima volta che il codice viene eseguito.

Questo bug non rende l' -Oopzione inutile, ma devi stare attento a come la usi. Se invocato su una singola classe, può incorporare determinate chiamate di metodo all'interno della classe senza rischi. Diverse classi possono essere allineate insieme a condizione che non ci siano potenziali restrizioni di accesso. E alcuni codici (come le applicazioni) non sono soggetti al verificatore bytecode. Puoi ignorare il bug se sai che il tuo codice verrà eseguito solo senza essere sottoposto al verificatore. Per ulteriori informazioni, vedere le mie domande frequenti su javac-O.

Profiler

Fortunatamente, JDK viene fornito con un profiler integrato per aiutare a identificare dove viene trascorso il tempo in un programma. Terrà traccia del tempo trascorso in ogni routine e scriverà le informazioni nel file java.prof. Per eseguire il profiler, utilizzare l' -profopzione quando si richiama l'interprete Java:

java -prof myClass

O per l'uso con un'applet:

java -prof sun.applet.AppletViewer myApplet.html

Ci sono alcuni avvertimenti per l'utilizzo del profiler. L'output del profiler non è particolarmente facile da decifrare. Inoltre, in JDK 1.0.2 tronca i nomi dei metodi a 30 caratteri, quindi potrebbe non essere possibile distinguere alcuni metodi. Sfortunatamente, con il Mac non è possibile richiamare il profiler, quindi gli utenti Mac sono sfortunati. Inoltre, la pagina del documento Java di Sun (vedere Risorse) non include più la documentazione per l' -profopzione). Tuttavia, se la tua piattaforma supporta l' -profopzione, è possibile utilizzare HyperProf di Vladimir Bulatov o ProfileViewer di Greg White per interpretare i risultati (vedi Risorse).

È anche possibile "profilare" il codice inserendo una temporizzazione esplicita nel codice:

long start = System.currentTimeMillis(); // do operation to be timed here long time = System.currentTimeMillis() - start;

System.currentTimeMillis()restituisce il tempo in 1/1000 di secondo. Tuttavia, alcuni sistemi, come un PC Windows, hanno un timer di sistema con una risoluzione inferiore (molto inferiore) a 1/1000 di secondo. Anche 1/1000 di secondo non è abbastanza lungo per cronometrare accuratamente molte operazioni. In questi casi, o su sistemi con timer a bassa risoluzione, può essere necessario calcolare il tempo necessario per ripetere l'operazione n volte e poi dividere il tempo totale per n per ottenere il tempo effettivo. Anche quando è disponibile la creazione di profili, questa tecnica può essere utile per temporizzare un'attività o un'operazione specifica.

Ecco alcune note di chiusura sulla profilazione:

  • Cronometrare sempre il codice prima e dopo aver apportato le modifiche per verificare che, almeno sulla piattaforma di test, le modifiche abbiano migliorato il programma

  • Prova a fare ogni prova di cronometraggio in condizioni identiche

  • Se possibile, ideare un test che non si basi sull'input dell'utente, poiché le variazioni nella risposta dell'utente possono far fluttuare i risultati

L'applet Benchmark

L'applet Benchmark misura il tempo necessario per eseguire un'operazione migliaia (o addirittura milioni) di volte, sottrae il tempo impiegato per eseguire operazioni diverse dal test (come l'overhead del ciclo) e quindi utilizza queste informazioni per calcolare la durata di ciascuna operazione ha preso. Esegue ogni test per circa un secondo. Nel tentativo di eliminare i ritardi casuali da altre operazioni che il computer può eseguire durante un test, esegue ogni test tre volte e utilizza il miglior risultato. Tenta inoltre di eliminare la raccolta dei rifiuti come fattore nei test. Per questo motivo, maggiore è la memoria disponibile per il benchmark, più accurati saranno i risultati del benchmark.