L'esecuzione di bubble sort è 5 volte più lenta con --indy

Question

Ho scritto un'implementazione di bubble sort per giocare un po 'con Groovy e vedere se lo --indy ha un effetto notevole sulle prestazioni.

In sostanza, ordina un migliaio di numeri interi casuali un migliaio di volte e misura il tempo medio di esecuzione per l'ordinamento dell'elenco.

La metà delle volte che l'elenco è un Integer[], l'altra metà è un ArrayList<Integer>.

I risultati sono veramente mi confuse:

$ groovyc BubbleSort.groovy 
$ time java -cp ~/.gvm/groovy/current/embeddable/groovy-all-2.4.3.jar:. BubbleSort 
Average: 22.926ms 
Min: 11.202ms 
[...] 26.48s user 0.84s system 109% cpu 25.033 total 

$ groovyc --indy BubbleSort.groovy 
$ time java -cp ~/.gvm/groovy/current/embeddable/groovy-all-2.4.3-indy.jar:. BubbleSort 
Average: 119.766ms 
Min: 68.251ms 
[...] 166.05s user 1.52s system 135% cpu 2:03.82 total 

Guardando l'utilizzo della CPU quando i parametri di riferimento sono in esecuzione, l'utilizzo della CPU è molto più alto quando viene compilato con --indy che senza.

Questo mi ha incuriosito così ho corse nuovamente i parametri di riferimento - ma questa volta con l'agente Yourkit e CPU traccia abilitata. Qui ci sono gli alberi delle chiamate registrate:

Senza --indy:

Con --indy:

Ed ecco i grafici delle prestazioni - di notare che la scala temporale è diverso perché il codice --indy è tanto Più lentamente.

Senza --indy (scala 1s):

Con --indy (60s scala):

Come si può vedere, l'utilizzo della CPU si stabilizza al 100% di un nucleo (12,5% nel grafico) quando è compilato senza --indy ma varia tra il 12,5% e il ~ 35% quando compilato con --indy. Ciò che è ancora più confuso è che Yourkit riporta solo un thread live (e il mio codice usa solo il thread principale), ma riesce comunque a tenere occupati due core e mezzo.

Il codice compilato con --indy utilizza anche molto tempo del kernel all'inizio, anche se questo scende e si stabilizza allo 0% dopo un po '- a quel punto il codice sembra accelerare un po' (il tasso di crescita dell'utilizzo dell'heap aumenta) e l'utilizzo della CPU aumenta.

Qualcuno può spiegarmi questo comportamento?

Versioni:

$ groovy -v 
Groovy Version: 2.4.3 JVM: 1.8.0_45 Vendor: Oracle Corporation OS: Linux 

$ java -version 
java version "1.8.0_45" 
Java(TM) SE Runtime Environment (build 1.8.0_45-b14) 
Java HotSpot(TM) 64-Bit Server VM (build 25.45-b02, mixed mode) 

BubbleSort.groovy:

class BubbleSort { 
    final def array 

    BubbleSort(final def array) { 
     this.array = array 
    } 

    private void swap(int a, int b) { 
     def tmp = array[a]; 
     array[a] = array[b] 
     array[b] = tmp; 
    } 

    private void rise(int index) { 
     for(int i = index; i > 0; i--) { 
      if(array[i] < array[i - 1]) { 
       swap(i, i-1) 
      } else { 
       break 
      } 
     } 
    } 

    void sort() { 
     for(int i = 1; i < array.size(); i++) { 
      rise i 
     } 
    } 

    final static Random random = new Random() 

    static void main(String[] args) { 
     def n = 1000 
     def size = 1000 
     // Warm up 
     doBenchmark 100, size 
     def results = doBenchmark n, size 
     printf("Average: %.3fms%n", results.total/1e6/n) 
     printf("Min: %.3fms%n", results.min/1e6) 
    } 

    private static def doBenchmark(int n, int size) { 
     long total = 0 
     long min = Long.MAX_VALUE 
     n.times { 
      def array = (1..size).collect { random.nextInt() } 
      if(it % 2) { 
       array = array as Integer[] 
      } 
      def start = System.nanoTime() 
      new BubbleSort<Integer>(array).sort() 
      def end = System.nanoTime() 
      def time = end - start 
      total += time 
      min = Math.min min, time 
     } 
     return [total: total, min: min] 
    } 
} 

io non sono interessato a ottimizzazioni su mia implementazione sorta di bolla meno che non siano correlate a invokedynamic comportamento - l'obiettivo qui non è per scrivere il miglior bubble sort possibile ma per capire perché --indy ha un impatto così negativo sulle prestazioni.

Aggiornamento:

ho convertito il mio codice di JRuby e provato la stessa cosa ed i risultati sono simili, anche se JRuby non è così veloce senza invokedynamic:

$ JAVA_OPTS="-Djruby.compile.invokedynamic=false" jruby bubblesort.rb 
Average: 78.714ms 
Min: 35.000ms 

$ JAVA_OPTS="-Djruby.compile.invokedynamic=true" jruby bubblesort.rb 
Average: 136.287ms 
Min: 92.000ms 

Aggiornamento 2:

Se rimuovo il codice che modifica l'elenco in un tempo pari a Integer[], le prestazioni aumentano in modo significativo, sebbene sia ancora più veloce senza --indy:

$ groovyc BubbleSort.groovy 
$ java -cp ~/.gvm/groovy/current/embeddable/groovy-all-2.4.3.jar:. BubbleSort 
Average: 29.794ms 
Min: 26.577ms 

$ groovyc --indy BubbleSort.groovy 
$ java -cp ~/.gvm/groovy/current/embeddable/groovy-all-2.4.3-indy.jar:. BubbleSort 
Average: 37.506ms 
Min: 33.555ms 

Se faccio lo stesso con JRuby, invokedynamic è più veloce:

Answer 1

La risposta è semplice in realtà abbastanza facile, Groovy non ha ancora una foto.

... oppure si può dire che di solito abbiamo una cache inline di dimensione 1. Ciò significa che ogni volta che si modifica il tipo di matrice di elenchi, verranno invalidate tutte le cache esistenti prima e la versione memorizzata nella cache verrà eliminata. Questo è per Groovy normale quasi come per indy, solo che Groovy normale usa le classi generate in runtime e indy usa le forme invokedynamic/lambda. Ma le forme lambda sono inizialmente più lente, mentre le prestazioni di picco sono migliori. Fondamentalmente ciò che fai è far sì che l'hotspot inizi da zero per la maggior parte delle chiamate al metodo, impedendogli di applicare le ottimizzazioni in ogni momento. Ovviamente non è colpa tua, ma è colpa di Groovy per non avere ancora un PIC. e solo per rendere questo molto chiaro ... questo non è un problema del linguaggio, è semplicemente qualcosa che non ho ancora potuto implementare.

JRuby d'altra parte ha un PIC e quindi non deve soffrire per l'overhead di creare nuovi handle di metodo tutto il tempo.