Wykonanie sortowania bąbelkowego jest 5 razy wolniejsze z --indy

Question

Napisałem implementację sortowania bąbelkowego, aby zagrać trochę z Groovy i sprawdzić, czy --indy ma jakikolwiek zauważalny wpływ na wydajność.

Zasadniczo sortuje listę tysiąca losowych liczb całkowitych tysiąc razy i mierzy średni czas wykonania sortowania listy.

Połowa czasu na liście to Integer[], druga połowa to ArrayList<Integer>.

Wyniki są bardzo mylące mnie:

$ 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 

Patrząc na wykorzystanie procesora, gdy benchmarki są uruchomione, użycie procesora jest dużo większa, gdy skompilowany z --indy niż bez.

to intryguje mnie tak znowu prowadził kryteriów - ale tym razem ze środkiem YourKit i CPU śledzenie włączone. Oto nagrane drzewa połączeń:

Bez --indy:

Z --indy:

A oto wykresy wydajności - pamiętać, że skala czasowa jest inna, ponieważ kod --indy tyle wolniej.

bez --indy (skali 1s)

z --indy (skala 60s)

Jak można zauważyć, wykorzystanie procesora stabilizuje się w 100% z jednego rdzenia (12,5% wykres), ale kompilowany bez wartości --indy, ale różni się znacznie od 12,5% do około 35% w przypadku kompilacji z --indy. Jeszcze bardziej mylące jest to, że Yourkit zgłasza tylko jeden wątek na żywo (a mój kod wykorzystuje tylko główny wątek), ale nadal udaje mu się zająć dwa i pół rdzenia.

Kod skompilowany za pomocą --indy również używa dużej ilości czasu jądra na początku, ale po pewnym czasie spada i stabilizuje się o 0% - w tym momencie kod wydaje się nieco przyspieszyć (wzrost wykorzystania sterty zwiększa tempo) i rośnie użycie procesora.

Czy ktoś może mi wyjaśnić to zachowanie?

Wersje:

$ 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] 
    } 
} 

Nie jestem zainteresowany optymalizacji na moim realizacji sortowania bąbelkowego, chyba że są one związane z invokedynamic zachowań - celem nie jest tu aby napisać najlepszy możliwy rodzaj bąbelków, ale aby zrozumieć, dlaczego --indy ma tak duży negatywny wpływ na wydajność.

Aktualizacja:

konwertowane mój kod do JRuby i próbował to samo, a wyniki są podobne, chociaż JRuby nie jest tak szybkie bez 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 

Aktualizacja 2:

Po usunięciu kodu, który zmienia listę na Integer[], wydajność w połowie czasu znacznie wzrasta, ale wciąż jest szybsza, bez konieczności uzyskania --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 

Jeśli zrobić to samo z JRuby, invokedynamic jest szybsze:

Answer 1

Odpowiedź jest prosta całkiem proste, Groovy nie ma jeszcze PIC.

... lub możesz powiedzieć, że zwykle mamy wbudowaną pamięć podręczną o rozmiarze 1. Oznacza to, że za każdym razem, gdy zmienisz typ tablicy list, spowoduje to unieważnienie wszystkich pamięci podręcznych, które istniały wcześniej, a wersja z pamięci podręcznej zostanie odrzucona. To jest normalne Groovy prawie tak samo jak dla indy, tylko że normalny Groovy używa klas generowanych przez środowisko wykonawcze, a indy używa form invokedynamic/lambda. Jednak formy lambda są początkowo wolniejsze, a maksymalna wydajność jest lepsza. Zasadniczo, po prostu uruchom hotspot od zera dla większości wywołań metod, co uniemożliwia mu stosowanie optymalizacji przez cały czas. Oczywiście to nie twoja wina, ale wina Groovy za brak PIC. i tylko po to, aby to było jasne ... nie ma problemu z językiem, jest to po prostu coś, czego jeszcze nie wprowadziłem w życie.

JRuby z drugiej strony ma PIC, a tym samym nie musi cierpieć z powodu tworzenia nowych metod obsługi przez cały czas.