Java 通过 Comparator进行排序大部分时间都花在比较（对象，对象）上

Question

在分析我们的代码库时，我注意到一些奇怪的事情。似乎使用类型化比较器（例如 Comparator）进行排序总是首先调用方法 Comparator.compare(Object,Object) 然后调用该方法比较器.compare(MyClass,MyClass)。此外，绝大多数时间都花在Comparator.compare(Object,Object)上。为了进一步探索，我做了一个小测试程序：

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

类型化比较器：

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

我为比较而制作的非类型化比较器：

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

以下是结果（来自 YourKit profiler; 如果您想要屏幕截图，请告诉我）：

+----------------------------------------------------+-----------------+-----------------+--------------------+
|                        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  |
+----------------------------------------------------+-----------------+-----------------+--------------------+

我在没有过滤的情况下运行了配置文件，您会看到对 mergeSort 的递归调用（这只会使其难以阅读），但没有什么有趣的。

那么这是怎么回事呢？该方法 SortMeComp.compare(Object,Object) 来自哪里？我们认为这是 Java 在内部创建的用于处理泛型的东西，但是什么会花费这么长时间呢？我认为 jvm 只会将通用方法视为“无类型”/对象方法。正如您所看到的，简单的转换要快得多。除此之外，我认为即使 jvm 需要做预先类型的事情，这也正是会被 JIT 掉的事情。这是怎么回事？

顺便说一句：

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

编辑：

为了回应 savinos 的回答，我尝试使用“无类型”比较器来模拟额外的方法调用，该比较器只是转换为类型化比较：

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

结果如下：

+---------------------------------------------------------+-----------------+-----------------+--------------------+
|                          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  |
+---------------------------------------------------------+-----------------+-----------------+--------------------+

所以看起来 savinos 是正确的！额外的时间只是额外的方法调用（再加上一点转换时间）。这对我来说似乎很疯狂；你认为这会被 JIT 掉吗？啊好吧。

我删除了编辑 2 并将其添加为答案，因为它本来应该是这样。

Answer 1

我可能是错的，但我想说“对象”比较器和类型化比较器（由通用比较器调用）之间的增量仅仅是由于额外的函数调用所致。

考虑一下您正在执行 12,352,936 次调用，这意味着每个函数调用大约需要 5.7*10^-7 秒，这并非不合理。

Answer 2

有点偏离主题，但您必须希望它很快...

您将使用随机数据将内部compare()时间减少大约50%，如果您将其更改为类似以下内容：

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

然而，这是仅当输入范围的大小小于 2^31 时才有效。如果更大，差异就会溢出。

Answer 3

该方法 SortMeComp.compare(Object,Object) 来自哪里？我们认为这是 Java 在内部创建的用于处理泛型的东西，

这是正确的。它由编译器作为您编写的 SortMeComp.compare(SortMe one, SortMe Two) 方法的 thunk 插入。

Answer 4

我开始想知道这整件事是否是跟踪的产物（我使用的是跟踪分析，而不是采样）。我过去曾见过跟踪在方法调用频繁的区域中导致扭曲。所以我做了一个直接的计时测试：

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

这是结果：

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

正如您所看到的，类型化的实际上执行得更快，这是可以预料的，因为它没有进行强制转换。因此，看来我所看到的差异完全是由于追踪造成的。我对 Hotswap 的信心又恢复了！

顺便说一句，我放入 printlns 只是为了确保 jvm 不会以任何方式优化循环。