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

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;
        }

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.

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.java¹.

gcj -O3 --main=sol01 sol01.java

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.

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:

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…↩