Ordinamento Java tramite Comparatore <T> trascorre la maggior parte del tempo a confronto (Oggetto, Oggetto)

Question

Ho notato qualcosa di strano mentre eseguivo il profiling del nostro codice base. Sembrava che l'ordinamento con un comparatore tipizzato (ad esempio Comparator<MyClass>) chiamasse sempre prima un metodo Comparator<MyClass>.compare(Object,Object) che poi chiamava il metodo Comparator<MyClass>.compare(MyClass,MyClass). Inoltre, la maggior parte del tempo è stata spesa nel Comparator<MyClass>.compare(Object,Object). Per esplorare ulteriormente, ho fatto un piccolo programma di test:

public class Sandbox { 
    public static void main(String argv[]) { 
     for(int j=0; j<100; j++) { 
      int n = 10000; 
      SortMe[] sortMes = new SortMe[n]; 
      for (int i=0; i<n; i++) { 
       sortMes[i] = new SortMe(Math.random()); 
      } 
      Arrays.sort(sortMes, new SortMeComp()); 
      System.out.println(Arrays.toString(sortMes)); 
     } 
     for(int j=0; j<100; j++) { 
      int n = 10000; 
      SortMe[] sortMes = new SortMe[n]; 
      for (int i=0; i<n; i++) { 
       sortMes[i] = new SortMe(Math.random()); 
      } 
      Arrays.sort(sortMes, new SortMeCompTypeless()); 
      System.out.println(Arrays.toString(sortMes)); 
     } 
    } 
} 

Il comparatore digitato:

public class SortMeComp implements Comparator<SortMe>{ 
    public int compare(SortMe one, SortMe two) { 
     if(one.getValue()>two.getValue()) { 
      return -1; 
     } else if (one.getValue()<two.getValue()) { 
      return 1; 
     } else { 
      return 0; 
     } 
    } 
} 

Il comparatore non tipizzata che ho fatto per il confronto:

public class SortMeCompTypeless implements Comparator{ 
    public int compare(Object oneObj, Object twoObj) { 
     SortMe one = (SortMe) oneObj; 
     SortMe two = (SortMe) twoObj; 
     if(one.getValue()>two.getValue()) { 
      return -1; 
     } else if (one.getValue()<two.getValue()) { 
      return 1; 
     } else { 
      return 0; 
     } 
    } 
} 

Ecco i risultati (da YourKit profiler; fammi sapere se preferisci avere uno screenshot):

+----------------------------------------------------+-----------------+-----------------+--------------------+ 
|      Name      | Time (ms) | Own Time (ms) | Invocation Count | 
+----------------------------------------------------+-----------------+-----------------+--------------------+ 
| +---java.util.Arrays.sort(Object[], Comparator) | 23,604 100 % |   8,096 |    200 | 
| |            |     |     |     | 
| +---SortMeComp.compare(Object, Object)   | 11,395 48 % |   7,430 |  12,352,936 | 
| | |            |     |     |     | 
| | +---SortMeComp.compare(SortMe, SortMe)  | 3,965 17 % |   3,965 |  12,352,936 | 
| |            |     |     |     | 
| +---SortMeCompTypeless.compare(Object, Object) | 4,113 17 % |   4,113 |  12,354,388 | 
+----------------------------------------------------+-----------------+-----------------+--------------------+ 

Ho eseguito il profilo senza filtrare e vengono visualizzate le chiamate ricorsive a mergeSort (che rendono difficile la lettura), ma non di interesse.

Quindi cosa sta succedendo qui? Da dove proviene il metodo SortMeComp.compare (Object, Object)? Abbiamo pensato che fosse qualcosa che Java crea internamente per trattare con i generici, ma cosa potrebbe richiedere così tanto tempo? Penserei che jvm tratterà semplicemente un metodo generico come un metodo "non tipizzato"/Object. Come puoi vedere, un cast semplice è molto più veloce. Oltre a ciò, penserei che questo sia esattamente il tipo di cosa che sarebbe JIT via anche se il jvm avesse bisogno di fare cose di tipo upfront. Cosa sta succedendo qui?

A proposito:

$ java -version 
java version "1.6.0_26" 
Java(TM) SE Runtime Environment (build 1.6.0_26-b03) 
Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode) 

Edit:

In risposta a savinos risposta, ho provato simulando la chiamata di metodo in più con un comparatore 'non tipizzata' che semplicemente gettato in un dattiloscritto confrontare:

public class SortMeCompMethodCalls implements Comparator{ 
    public int compare(Object oneObj, Object twoObj) { 
     return compare((SortMe)oneObj, (SortMe)twoObj); 
    } 
    public int compare(SortMe one, SortMe two) { 
     if(one.getValue()>two.getValue()) { 
      return -1; 
     } else if (one.getValue()<two.getValue()) { 
      return 1; 
     } else { 
      return 0; 
     } 
    } 
} 

Ecco i risultati:

+---------------------------------------------------------+-----------------+-----------------+--------------------+ 
|       Name       | Time (ms) | Own Time (ms) | Invocation Count | 
+---------------------------------------------------------+-----------------+-----------------+--------------------+ 
| +---java.util.Arrays.sort(Object[], Comparator)  | 31,044 100 % |   8,061 |    200 | 
| |             |     |     |     | 
| +---SortMeComp.compare(Object, Object)    | 11,554 37 % |   7,617 |  12,354,392 | 
| | |             |     |     |     | 
| | +---SortMeComp.compare(SortMe, SortMe)    | 3,936 13 % |   3,936 |  12,354,392 | 
| |             |     |     |     | 
| +---SortMeCompMethodCalls.compare(Object, Object) | 11,427 37 % |   7,613 |  12,352,146 | 
|  |             |     |     |     | 
|  +---SortMeCompMethodCalls.compare(SortMe, SortMe) | 3,814 12 % |   3,814 |  12,352,146 | 
+---------------------------------------------------------+-----------------+-----------------+--------------------+ 

Quindi sembra che il savino abbia ragione! Il tempo extra è solo la chiamata al metodo extra (più un po 'per il cast). Mi sembra pazzesco; penseresti che sarebbe JITed via? Ah bene.

Ho rimosso la modifica 2 e l'ho aggiunta come risposta come avrebbe dovuto essere originariamente.

Answer 1

Ho iniziato a chiedermi se tutta questa faccenda fosse un artefatto del tracciamento (io usavo tracciare profili, non campionare). Ho visto che le tracce causano distorsioni nel passato nelle aree di chiamata di metodo pesante. Così ho fatto un test dritto tempistica:

public class Sandbox { 
    public static void main(String argv[]) { 
     long startTime = System.currentTimeMillis(); 
     sortTest(10000, 10000, new SortMeComp()); 
     System.err.println("\n"+(System.currentTimeMillis()-startTime)); 
     startTime = System.currentTimeMillis(); 
     sortTest(10000, 10000, new SortMeCompTypeless()); 
     System.err.println("\n"+(System.currentTimeMillis()-startTime)); 
    } 

    public static void sortTest(int n, int l, Comparator<SortMe> c) { 
     for(int i=0; i<n; i++) { 
      SortMe[] sortMes = new SortMe[l]; 
      for(int j=0; j<l; j++) { 
       sortMes[j] = new SortMe(Math.random()); 
      } 
      System.out.print(sortMes[(int)(Math.random()*l)].getValue()); 
      Arrays.sort(sortMes, c); 
     } 
    } 
} 

Ecco i risultati:

[bunch of doubles...] 
sortTest(10000, 10000, new SortMeComp()): 18168 
[bunch of doubles...] 
sortTest(10000, 10000, new SortMeCompTypeless()): 19366 

Come si può vedere, la digitato uno adempie di fatto più veloce, che è prevedibile in quanto non sta facendo un cast. Quindi, sembra che la differenza che stavo vedendo era interamente dovuta al tracciamento. La mia fiducia in Hotswap è stata ripristinata!

A proposito, inserisco le stampe solo per assicurarmi che jvm non ottimizzi il ciclo in alcun modo.

Answer 2

Potrei sbagliarmi, ma direi che il delta tra il comparatore "Object" e il comparatore tipizzato (che è chiamato da quello generico) è semplicemente dovuto alla chiamata di funzione extra.

Si consideri che si stanno facendo 12,352,936 invocazioni, il che significa circa 5,7 * 10^-7 secondi per chiamata di funzione, il che non è irragionevole.

Answer 3

Un po 'fuori tema, ma devi volere che sia veloce ...

Potrai ridurre il tempo interiore confrontare() di circa il 50%, con dati casuali, se si cambia a qualcosa come:

public int compare(SortMe one, SortMe two) { 
    return one.getValue() - two.getValue(); 
} 

Tuttavia, questo è valido solo se l'entità del la gamma di input è inferiore a 2^31. Se più grande, la differenza trabocca.

Answer 4

Da dove proviene il metodo SortMeComp.compare(Object,Object)? Abbiamo pensato che fosse qualcosa che Java crea internamente per occuparsi di generici,

Che è corretto. Viene inserito dal compilatore come thunk per il metodo che hai scritto SortMeComp.compare(SortMe one, SortMe two).