Java sort über Comparator<T> verbringt die meiste Zeit in compare(Object,Object)

Question

Ich bemerkte etwas Seltsames beim Profiling unseres Codebases. Es schien, dass das Sortieren mit einem typisierten Vergleicher (z.B. Comparator) immer zuerst eine Methode Comparator.compare(Object, Object) aufrief, die dann die Methode Comparator.compare(MyClass, MyClass) aufrief. Darüber hinaus wurde die überwiegende Mehrheit der Zeit in der Comparator.compare(Object, Object) verbracht. Um dies weiter zu erkunden, habe ich ein kleines Testprogramm erstellt:

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

Der typisierte Comparator:

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

Der untypisierte Comparator, den ich zum Vergleich erstellt habe:

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()

``

Hier sind die Ergebnisse (vom YourKit Profiler; lassen Sie mich wissen, wenn Sie lieber einen Screenshot hätten):

+----------------------------------------------------+-----------------+-----------------+--------------------+
|                        Name                        |    Zeit (ms)    |  Eigene Zeit (ms)  |  Aufrufanzahl  |
+----------------------------------------------------+-----------------+-----------------+--------------------+
|  +---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  |
+----------------------------------------------------+-----------------+-----------------+--------------------+

Ich habe das Profil ohne Filterung ausgeführt, und Sie sehen die rekursiven Aufrufe von mergeSort (die das Lesen erschweren), aber nichts Interessantes.

Was passiert hier? Woher stammt diese Methode SortMeComp.compare(Object,Object)? Wir dachten, dass es etwas ist, das Java intern für den Umgang mit Generics erstellt, aber warum dauert es so lange? Ich würde denken, dass die JVM eine generische Methode einfach wie eine "untypisierte"/Object-Methode behandeln würde. Wie Sie sehen können, ist ein einfacher Cast viel schneller. Außerdem würde ich denken, dass dies genau die Art von Dingen ist, die selbst dann, wenn die JVM upfront Typ-Operationen durchführen müsste, JIT-optimiert werden würde. Was passiert hier?

Übrigens:

$ 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)

Bearbeitung:

Als Antwort auf die Antwort von savino habe ich versucht, den zusätzlichen Methodenaufruf mit einem 'untypisierten' Comparator zu simulieren, der einfach zu einer typisierten compare gecastet hat:

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()

`

Hier sind die Ergebnisse:

+---------------------------------------------------------+-----------------+-----------------+--------------------+
|                          Name                           |    Zeit (ms)    |  Eigene Zeit (ms)  |  Aufrufanzahl  |
+---------------------------------------------------------+-----------------+-----------------+--------------------+
|  +---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  |
+---------------------------------------------------------+-----------------+-----------------+--------------------+

Es scheint also, dass savinos recht hat! Die zusätzliche Zeit betrifft nur den zusätzlichen Methodenaufruf (plus etwas für den Cast). Das erscheint mir verrückt; man würde denken, dass dies JIT-optimiert wäre? Na ja.

Ich habe Bearbeitung 2 entfernt und als Antwort hinzugefügt, da dies von Anfang an so hätte sein sollen.

` `` ``` ````

Answer 1

Ich könnte mich irren, aber ich würde sagen, dass der Unterschied zwischen dem "Objekt"-Komparator und dem typisierten Komparator (der vom generischen Komparator aufgerufen wird) einfach auf den zusätzlichen Funktionsaufruf zurückzuführen ist.

Bedenken Sie, dass Sie 12.352.936 Aufrufe durchführen, was ungefähr 5,7*10^-7 Sekunden pro Funktionsaufruf bedeutet, was nicht unvernünftig ist.

Answer 2

Ein wenig Off-Topic, aber du möchtest, dass es schnell ist...

Die innerhalb von compare() Zeit wird um ca. 50% reduziert, mit zufälligen Daten, wenn du es zu so etwas änderst:

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

Allerdings ist dies nur gültig, wenn die Größenordnung der Eingabebereiche kleiner als 2^31 ist. Wenn größer, überläuft die Differenz.

Answer 3

Woher kommt diese Methode SortMeComp.compare(Object, Object)? Wir haben herausgefunden, dass es etwas ist, das Java intern erstellt, um mit Generics umzugehen,

Das ist richtig. Es wird vom Compiler als ein thunk für die von Ihnen geschriebene Methode SortMeComp.compare(SortMe one, SortMe two) eingefügt.

Answer 4

Ich begann mich zu fragen, ob das Ganze ein Artefakt des Tracings war (ich verwendete Tracing-Profiling, nicht Sampling). Ich habe in der Vergangenheit gesehen, dass Tracing Verzerrungen in bereichen mit vielen Methodenaufrufen verursachen kann. Also habe ich einen einfachen Zeittest gemacht:

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 c) {
        for(int i=0; i

`

Hier sind die Ergebnisse:

[eine Menge von Doubles...]
sortTest(10000, 10000, new SortMeComp()): 18168
[eine Menge von Doubles...]
sortTest(10000, 10000, new SortMeCompTypeless()): 19366

Wie Sie sehen können, dauert der typisierte Test tatsächlich schneller, was zu erwarten ist, da er keinen Cast durchführt. Daher scheint der Unterschied, den ich sah, ausschließlich auf das Tracing zurückzuführen zu sein. Mein Vertrauen in Hotswap wurde wiederhergestellt!

Übrigens habe ich die printlns eingefügt, um sicherzustellen, dass der JVM die Schleife nicht in irgendeiner Weise optimieren würde.

`