Java 8 bad performance , sorting

Question

I solve algorithmic problems on codeforces and I tried pushing the same solution using java 7 and java 8 and to my surprise using java 8 I got much worse solution.

On the last test: Java 7: time: 373 ms., memory: 112 KB

java 8: time: 623 ms., memory: 3664 KB

My code

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


}

Why is that ?

Answer 1

There are many points not clear about the question. These are obvious things, like how you are running the timing test, how you are providing the input numbers, and what the size of the input numbers is.

Also, when you say that storing 2*100000 Integer objects in Java 7 should only need 112KB, then there must be some magic compression involved, because the data itself will already take at least 800 KB, ignoring any further object overhead. Additionally, the sorting should not even take 373ms with the numbers that you mentioned, but maybe only 50ms on a modern PC.

However, there have been some hints in the comments that I'll try to assemble here, hoping that it will be considered helpful (and maybe even answer your question).

---

First of all, microbenchmarking is an art, and there are many things to consider. In order to obtain "reliable" results, you have to use a microbenchmarking toolkit like JMH or Caliper. But to quickly get a rough approximation of the results, you should at least repeat the actual test several times. For your case, this could roughly be done like this:

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

On my machine (omitting some details here, because the reliability is not sooo high anyhow), when started with -Xmx1500m -server, this gives the following results with 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

and these results in 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

You can see that the results are approximately equal, except for the last one. Starting it again, and additionally specifying -verbose:gc shows the reason:

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

It performs a full garbage collection before the last pass. (Something like this would be avoided when using one of the above mentioned benchmarking frameworks!).

Now one could start some GC tuning, and there are many, many articles about that (this is not only an art, this is a black art). But the actual reason for the GC can be derived from the program: It is creating lots and lots of Integer objects that have to be cleaned up.

Depending in the size of the Integer objects in these lists, this may be avoided. The autoboxing from int to Integer internally relies on a cache for "small" int values. The default size of this cache is rather small. But when starting the above mentioned program with -XX:AutoBoxCacheMax=300, nearly all GC pauses will disappear, because there simply are no Integer values larger than 300 in this test.

---

An aside: Here is simple modification of the program to use parallel streams

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

In this case, you may even observe a slight speedup with 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