Sul Java che batteva il C (compiler strikes back again)

coffee-309981_640

Il caso trattato nell’articolo Compilati VS interpretati passo 2 (The compiler strikes back) è intrigante: siamo davvero di fronte a uno di quei pochi casi in cui un linguaggio che non viene compilato riesce a battere uno compilato?

Sembrerebbe proprio di sì.

Però ricordiamoci che non è che la JVM realmente interpreta i bytecode in modo “stupido”: c’è la compilazione Just In Time (JIT) e la JVM è tanto ben fatta da poter profilare il codice a runtime per poter migliorare le ottimizzazioni in fase di compilazione JIT…

Questo potrebbe spiegare perché Java sembra battere il C. (Non prendo in considerazione il Python, e nemmeno l’Objective-C per il quale, comunque, si può fare un discorso simile a quello del C).

Passo passo, sperimentando e provando, andiamo a scoprire come stanno le cose…

Elucubrazioni e ipotesi

Intanto nel codice C ho cambiato long double in double: il double in Java è un “64-bit IEEE 754 floating point”, come il double del C. Invece il long double può essere di più. Comunque non cambia praticamente nulla: le performance continuano ad essere inferiori a quelle del Java.

Quello che ho pensato è questo: in Java l’ottimizzatore in qualche modo si accorge che tutti i calcoli da un certo punto in poi non possono che dare infinito (si va oltre le possibilità del double), per cui il ciclo più interno può essere prematuramente interrotto. Oppure: è inutile eseguire la moltiplicazione se f è già diventanto “infinito”.

Se aggiungiamo a mano questa ottimizzazione, il C torna a brillare (dovete includere math.h):

        for(a = 1; a <= i; a++)
        {
            f *= a;
            if (isinf(f)) break;
        }

sh01

Si comincia a ragionare…

Oppure

        for(a = 1; a <= i; a++)
        {
            if (!isinf(f)) {
                f *= a;
            }
        }

Non l’ho provata ma possiamo dire che molto probabilmente sarà più lenta della versione con il break. Il vantaggio di questa versione è che permette l’esecuzione di altro codice nel caso in cui il corpo del ciclo non fosse costituito solo da f *= a.

(Ho fatto anche un’altra modifica: ho usato difftime per avere il numero di secondi… però non serve a molto quando il tutto dura meno di un secondo, e perciò ho messo time sulla linea di comando)

Si può fare di meglio: interrompere il ciclo esterno. Infatti, raggiunto un certo valore di i (chiamiamolo iMax), tutti quelli maggiori faranno in modo che il ciclo interno porti f a “inf”. Un essere umano ci arriva facilmente; ci può arrivare anche un ottimizzatore? Il codice ottimizzato avrebbe, come equivalente di alto livello C, l’aspetto seguente:

    for (i = 0; i <= iMax; i++) {
        double f = 1;
        int a;
 
        for(a = 1; a <= i; a++)
        {
            f *= a;
        }

        nArray[i] = i * f;
    }
    for (i = iMax + 1; i < MAXLOOP; i++) {
        nArray[i] = INFINITY;
    }

Intermezzo: un’idea sciocca

La JVM è stack based. Può essere che un modello simile in certe circostanze risulti più efficiente di uno register based? L’idea è sciocca perché non c’è modo che del codice ben ottimizzato eseguito da un hardware possa essere battuto da un interprete software (che gira sullo stesso hardware).

Ma non è proprio il caso che stiamo analizzando? No. Infatti stiamo cercando il trucco perché la tesi è che ci sia; poiché non lo vediamo, ci sembra che Java vada meglio… Ma in realtà è come se stessimo paragonando le performance del bubble sort scritto in C e Java, senza sapere che Java dietro le quinte lo sostituisce con un quick sort… (Il C non farebbe mai di questi scherzi:-D)

È possibile che le CPU stack based permettano ottimizzazioni migliori di quelle register based? Secondo questo post no:

Another advantage of the register based model is that it allows for some optimizations that cannot be done in the stack based approach. One such instance is when there are common sub expressions in the code, the register model can calculate it once and store the result in a register for future use when the sub expression comes up again, which reduces the cost of recalculating the expression.

Quindi non è che partendo dai bytecode Java si possa generare codice migliore… altrimenti i compilatori userebbero una rappresentazione intermedia stack based nella fase di ottimizzazione.

Comunque, prima di arrivare a realizzare quanto l’idea fosse sciocca, mi sono cimentato nel gioco che vedete nell’immagine.

sh02

Il disassemblato della classe (a destra nell’immagine) si ottiene con javap -c. Tutte le funzioni che vedete a sinistra hanno inline e lavorano su uno “stack” (un array) di strutture contenenti un enum che specifica il tipo (intero, double, array…) e una union.

Inutile dire che i tempi peggiorano…

real        0m6.052s
user        0m6.028s

Il codice lo potete trovare sul mio repository. (Prima o poi cambierà un po’: devo aggiungere un riferimento al post, riordinare e ripulire e commentare ecc.)

gcj

Proviamo ad usare gcj per generare un vero e proprio eseguibile da sol01.java1.

gcj -O3 --main=sol01 sol01.java

sh03

I tempi sono più o meno quelli del C. A questo punto togliamo --main e mettiamo -S per vedere il codice generato. Nessuna sorpresa: a meno di un controllo sull’indice dell’array (per poter throware BadArrayIndex) e qualche altro dettaglio, assomiglia tremendamente a quello generato dalla versione C… del resto il compilatore sotto il cofano è lo stesso.

Dubbio: possibile che il gcc non implementi delle ottimizzazione che invece una VM è in grado di fare a runtime al momento della compilazione JIT?

(Per cercare di essere breve non lo metto :-D, ma ho fatto pure la prova con --profile-generate / esecuzione / --profile-use, giro di giostra che dovrebbe permettere al gcc di fare alcune ottimizzazione eventuali in più… Se non ho sbagliato qualcosa… Niente da fare…)

Sembra quasi che altri marchingegni che compilano Just In Time riescano a capire qualcosa che il gcc non capisce.

Tuttavia, non abbiamo finito di esplorare le possibilità…

clang!

Non ci stiamo dimenticando di qualcosa? gcc è un ottimo compilatore, ma non è l’unico. Proviamo con clang.

sh04

Sorpresa!

E uno sguardo al codice assembly generato rivela qual è il trucco della JVM (e di clang e di pypy e di…): sfruttare meglio le possibilità del processore della macchina che eseguirà materialmente il codice compilato JIT!

Sembra che il gcc di default preferisca generare codice “generico”.

Torniamo a gcc, ma questa volta aggiungiamo qualche opzione di compilazione e riproviamo:

sh05

Bingo.


  1. Per non so quale motivo avevo salvato il file come sol01.java; poi, invece di rinominarlo in base al nome della classe, ho rinominato la classe… Quando si fanno le cose con criterio…

Annunci
Post a comment or leave a trackback: Trackback URL.

Commenti

  • dikiyvolk  On 19 ottobre 2015 at 10:11

    Quando la classe non è acqua 🙂 grazie per l’articolo che ha spiegato i perché e i per come assenti nella mia stesura.
    Effettivamente io non avevo impostato alcuna ottimizzazione e non avevo minimamente pensato al discorso dell'”infinito”.

    Vado a fare 2 ore di penitenza in ginocchio sui ceci…

    • shintakezou  On 19 ottobre 2015 at 18:57

      mi sarei aspettato che non fossero necessarie particolari accortezze, come nel caso clang… La differenza la fa l’uso delle istruzioni SSE più che l’ottimizzazione con -O3.

  • juhan  On 19 ottobre 2015 at 13:28

    Über 😀 Forse sarebbe bello esaminare anche il lentissimo Python. Che sarà lentissimo ma ha (quasi) tutto quello che riesci a immaginarti.

  • Gabriele Di Bari  On 29 marzo 2016 at 13:10

    Che versione d GCC hai usato?
    Quali sono i flags di compilazione?
    Hai abilitato l’Auto-vectorization?
    E le simd instruction?
    I tempi come li prendi? Usi QueryPerformanceCounter?

    • shintakezou  On 29 marzo 2016 at 19:37

      Hai letto l’articolo? Sei arrivato fino in fondo a leggere l’articolo? Hai letto quei due commenti che ci sono?

      P.S.
      L’unica info che non puoi dedurre dall’articolo stesso è la versione. Era il gcc del repo di Debian 7, perciò dovrebbe essere 4.7. Ma con il 5.2.0 (l’ultima versione a mia disposizione) è uguale: senza opzioni il default dato dalla compilazione di default di GCC medesimo non usa istruzioni SSE o altre amenità, a differenza di clang (e del Java…)

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: