Java 8性能不好，排序错误

Question

我在codeforces上解决算法问题，并尝试使用java7和java8推出相同的解决方案，令我惊讶的是，使用java8我得到了更糟糕的解决方案

在最后一次测试中： Java 7： 时间：373毫秒，内存：112 KB

java 8： 时间：623毫秒，内存：3664 KB

我的代码

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    List<Integer> list1 = new ArrayList<>(n);
    List<Integer> list2 = new ArrayList<>(m);
    for(int i=0;i<n;i++) {
        list1.add(in.nextInt());
    }
    for (int i = 0; i < m; i++) {
        list2.add(in.nextInt());
    }

    Collections.sort(list1);
    Collections.sort(list2, Collections.reverseOrder());

    int max = Math.min(list1.size(), list2.size());
    int a,b;
    long result = 0;
    for(int i=0;i<max;i++) {
        a = list1.get(i);
        b = list2.get(i);
        if(b > a) result += ( b- a);
        else break;
    }

    System.out.println(result);


}

为什么呢

Answer 1

关于这个问题，有许多观点尚不清楚。这些都是显而易见的事情，比如如何运行计时测试，如何提供输入数字，以及输入数字的大小

另外，当你说在Java 7中存储2*100000Integer个对象只需要112KB时，肯定会涉及到一些神奇的压缩，因为数据本身至少需要800KB，忽略任何进一步的对象开销。此外，对你提到的数字进行排序甚至不需要373毫秒，但在现代PC上可能只需要50毫秒

然而，在我将在这里收集的评论中有一些提示，希望它会被认为是有用的（甚至可能会回答你的问题）

---

首先，微标杆是一门艺术，有很多事情要考虑。为了获得“可靠”的结果，必须使用像JMH或Caliper这样的微基准标记工具包。但要快速获得大致的结果，您至少应该重复实际测试几次。对于您的情况，大致可以这样做：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class SortingSpeedTest {

    private static List<Integer> createList(int n, int offset, int range) {
        Random random = new Random(0);
        List<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(random.nextInt(range) + offset);
        }
        return list;
    }

    public static void main(String[] args) {
        for (int m = 1000; m <= 1000000; m *= 10) {
            for (int n = 1000; n <= 1000000; n *= 10) {

                runTest(m, n);
            }
        }

    }

    private static void runTest(int m, int n) {
        List<Integer> list1 = createList(m, 0, 100);
        List<Integer> list2 = createList(n, 100, 100);

        long before = System.nanoTime();
        Collections.sort(list1);
        Collections.sort(list2, Collections.reverseOrder());
        int max = Math.min(list1.size(), list2.size());
        int a, b;
        long result = 0;
        for (int i = 0; i < max; i++) {
            a = list1.get(i);
            b = list2.get(i);
            if (b > a)
                result += (b - a);
            else
                break;
        }
        long after = System.nanoTime();
        System.out.printf("m=%7d n=%7d result=%14d duration %8.3f\n", m, n,
                result, (after - before) / 1e6);
    }
}

在我的机器上（这里省略了一些细节，因为可靠性无论如何都不是很高），当从-Xmx1500m -server开始时，这会在Java 7中给出以下结果

m=   1000 n=   1000 result=        100000 duration    5,985
m=   1000 n=  10000 result=        144379 duration   26,641
m=   1000 n= 100000 result=        149303 duration   38,308
m=   1000 n=1000000 result=        149336 duration  148,365
m=  10000 n=   1000 result=        145269 duration    9,068
m=  10000 n=  10000 result=       1000000 duration   11,799
m=  10000 n= 100000 result=       1450247 duration   16,218
m=  10000 n=1000000 result=       1494798 duration  134,486
m= 100000 n=   1000 result=        149664 duration   18,795
m= 100000 n=  10000 result=       1449668 duration   18,451
m= 100000 n= 100000 result=      10000000 duration   27,568
m= 100000 n=1000000 result=      14490326 duration  149,033
m=1000000 n=   1000 result=        149664 duration  153,541
m=1000000 n=  10000 result=       1495165 duration  129,903
m=1000000 n= 100000 result=      14510529 duration  141,377
m=1000000 n=1000000 result=     100000000 duration  278,689

Java 8中的这些结果：

m=   1000 n=   1000 result=        100000 duration    4,271
m=   1000 n=  10000 result=        144379 duration   10,414
m=   1000 n= 100000 result=        149303 duration   45,413
m=   1000 n=1000000 result=        149336 duration  179,397
m=  10000 n=   1000 result=        145269 duration    7,422
m=  10000 n=  10000 result=       1000000 duration    6,464
m=  10000 n= 100000 result=       1450247 duration   54,259
m=  10000 n=1000000 result=       1494798 duration  158,869
m= 100000 n=   1000 result=        149664 duration   17,863
m= 100000 n=  10000 result=       1449668 duration   16,904
m= 100000 n= 100000 result=      10000000 duration   33,613
m= 100000 n=1000000 result=      14490326 duration  158,988
m=1000000 n=   1000 result=        149664 duration  133,977
m=1000000 n=  10000 result=       1495165 duration  139,210
m=1000000 n= 100000 result=      14510529 duration  156,483
m=1000000 n=1000000 result=     100000000 duration 1080,306

你可以看到，除了最后一个，结果大致相等。再次启动它，并另外指定-verbose:gc显示原因：

...
m=1000000 n= 100000 result=      14510529 duration  156,934
...
[Full GC (Ergonomics)  64237K->24095K(79360K), 0.7443466 secs]
m=1000000 n=1000000 result=     100000000 duration 1056,624

它在最后一次传递之前执行完整的垃圾收集。（使用上述基准测试框架时，可以避免类似的情况！）

现在我们可以开始一些GC调优了，有很多很多关于这方面的文章（这不仅仅是一门艺术，这是一门黑色艺术）。但是GC的实际原因可以从程序中得到：它正在创建大量需要清理的Integer对象

根据这些列表中Integer对象的大小，可以避免这种情况。从int到Integer的自动装箱在内部依赖于“小”值的缓存。此缓存的默认大小相当小。但是当用-XX:AutoBoxCacheMax=300启动上述程序时，几乎所有的GC暂停都会消失，因为在这个测试中没有大于300的Integer值

---

旁白：下面是对程序的简单修改，以使用并行流

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

public class ParallelSortingSpeedTest {

    private static List<Integer> createList(int n, int offset, int range) {
        Random random = new Random(0);
        List<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(random.nextInt(range) + offset);
        }
        return list;
    }

    public static void main(String[] args) {
        for (int m = 1000; m <= 1000000; m *= 10) {
            for (int n = 1000; n <= 1000000; n *= 10) {

                runTest(m, n);
            }
        }

    }

    private static void runTest(int m, int n) {
        List<Integer> list1 = createList(m, 0, 100);
        List<Integer> list2 = createList(n, 100, 100);

        long before = System.nanoTime();
        list1 = list1.parallelStream().sorted().collect(Collectors.toList());
        list2 = list2.parallelStream().sorted(
            Collections.reverseOrder()).collect(Collectors.toList());
        int max = Math.min(list1.size(), list2.size());
        int a, b;
        long result = 0;
        for (int i = 0; i < max; i++) {
            a = list1.get(i);
            b = list2.get(i);
            if (b > a)
                result += (b - a);
            else
                break;
        }
        long after = System.nanoTime();
        System.out.printf("m=%7d n=%7d result=%14d duration %8.3f\n", m, n,
                result, (after - before) / 1e6);
    }
}

在这种情况下，您甚至可以观察到Java 8的轻微加速：

....
m=1000000 n=  10000 result=       1495165 duration   95,386
m=1000000 n= 100000 result=      14510529 duration   95,467
m=1000000 n=1000000 result=     100000000 duration  172,782

Answer 2

可能有几个原因，但我的第一个猜测是，Java8附带了许多附加功能，因此初始加载时间更大

如果我们假设n不是很大，可以说处理时间可以忽略不计

你用哪个数字顺序（n和m）执行程序

您还可以使用stdin提供数字。我猜你用的是某种管子？否则输入值当然是处理时间的一部分

为了更有效地测试这一点，你需要在同一次跑步中多次重复你的实验。。。只有这样，加工时间才成为主要因素