Why sorting Long array is slower than sorting long array using Arrays.sort()?

Question

I get a result that sorting time of a Long array using Arrays.sort() is taking more time than sorting a long array using Arrays.sort(). Here is the code.

public class ABtest {

public static void main(String[] args) {
    long startTime;
    long endTime;

    //code block 1
    startTime = System.nanoTime();
    Long a[] = new Long[10000];
    for (int i = 0; i < a.length; i++) {
        a[i] = 12l;
    }
    Arrays.sort(a);
    endTime = System.nanoTime();
    System.out.println("code block (has Long array) 1 = " + (endTime - startTime));



    //code block 2
    startTime = System.nanoTime();
    long c[] = new long[10000];
    for (int i = 0; i < c.length; i++) {
        c[i] = 12l;
    }
    Arrays.sort(c);
    endTime = System.nanoTime();
    System.out.println("code block (has long array) 2 = " + (endTime - startTime));

}
}

The running times :

code block (has Long array) 1 = 3076331

code block (has long array) 2 = 741501

Can anyone explain this behavior. or Am i doing some mistake here ??

You need to really careful while bench marking. There are lot of what-if cases arises. http://www.ibm.com/developerworks/java/library/j-benchmark1/index.html — kosa, Dec 28 '13 at 05:13
`Long` must be unboxed to sort; `long` can be sorted as is. Plus the usual hazards re benchmarking. (In particular you're including the time to load up the array, which in the `Long` case requires boxing each value and the object creation that implies.) — Hot Licks, Dec 28 '13 at 05:23
This question appears to be off-topic because it is about benchmarking and isn't an actual question, just a blog post about how they are incorrectly micro-benchmarking something. — , Dec 28 '13 at 05:43
In effect, what your "benchmark" is measuring is the time required to create 10K `Long` objects. — Hot Licks, Dec 28 '13 at 14:30

score 3 · Answer 1 · edited May 23 '17 at 11:49

The answer is the same as the answer to your other benchmarking Question. Your benchmark is badly designed, and the timing numbers you seeing are not valid / meaningful.

However, sorting a Long[] will be slower than sorting an equivalent long[] anyway:

This is in part because comparing a pair of Long values takes longer than comparing a pair of long values.
In addition, if you look at the source code you will see that a different algorithm is used for sorting long[] and Object[]. The former uses a form of Quicksort, and the latter uses either a form of MergeSort or TimSort.

My understanding is that algorithms are different because the sort algorithm has to be stable; i.e. if a pair of elements are equal, the original ordering of the elements must be preserved. For primitive types you can ignore that, but for reference types (such as Long) this constrains the sort algorithm that can be used.

(Based on the results posted by @S.Yavari, I suspect that the difference in algorithm is the more significant issue.)

S.Yavari · Answer 2 · 2013-12-28T05:40:34.497

This is the result of your code on my machine:

1st run:

code block (has Long array) 1 = 6070325
code block (has long array) 2 = 8739868

2nd run:

code block (has Long array) 1 = 4449868
code block (has long array) 2 = 6224883

3rd run:

code block (has Long array) 1 = 5773081
code block (has long array) 2 = 1160343

I think that your benchmark is badly designed. And if we change the code to this:

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println("Benchmark " + (i + 1));
            benchmark();
            System.out.println();
        }
    }

    public static void benchmark() {
        long startTime;
        long endTime;

        Long a[] = new Long[10000];
        long b[] = new long[10000];

        for (int i = 0; i < a.length; i++)
            a[i] = 12l;

        for (int i = 0; i < b.length; i++)
            b[i] = 12l;

        //code block 1
        startTime = System.nanoTime();
        Arrays.sort(a);
        endTime = System.nanoTime();
        System.out.println("\tcode block (has Long array) 1 = " + (endTime - startTime));

        //code block 2
        startTime = System.nanoTime();
        Arrays.sort(b);
        endTime = System.nanoTime();
        System.out.println("\tcode block (has long array) 2 = " + (endTime - startTime));
    }
}

We can see the result you said. This is because of compare method difference in long data type and Long object. You know that the long is a primitive data type but Long is an object. So, to comparing two long value, system can compare them without using any complicated compare method but for comparing two Long object, JVM should use the compare method of Long object and that method takes more time.

Note that this is the result of 2nd code:

Benchmark 1
code block (has Long array) 1 = 2957778
code block (has long array) 2 = 751911

Benchmark 2
code block (has Long array) 1 = 2081759
code block (has long array) 2 = 392857

Benchmark 3
code block (has Long array) 1 = 2031473
code block (has long array) 2 = 410946

Benchmark 4
code block (has Long array) 1 = 2016387
code block (has long array) 2 = 360241

Benchmark 5
code block (has Long array) 1 = 2070235
code block (has long array) 2 = 360870

Benchmark 6
code block (has Long array) 1 = 2105156
code block (has long array) 2 = 360801

Benchmark 7
code block (has Long array) 1 = 2020928
code block (has long array) 2 = 386013

Benchmark 8
code block (has Long array) 1 = 1976229
code block (has long array) 2 = 359682

Benchmark 9
code block (has Long array) 1 = 5213093
code block (has long array) 2 = 363664

Benchmark 10
code block (has Long array) 1 = 3999880
code block (has long array) 2 = 361638

Good work. These numbers are believable. – Stephen C Dec 29 '13 at 01:13 — Stephen C, Dec 29 '13 at 01:13

score 1 · Answer 3 · answered Dec 28 '13 at 05:33

long values can just be compared whilst the boxed value Long needs to be extracted before comparison (just a hunch).

There are issues with your test though. You are including the time to allocate the array and fill it. You aren't giving the JVM much time to work out the hot spots for tuning and you may also be running into garbage collection time.

You could also use better test data. Is there a difference in timing for an array that is already ordered in ascending or descending order? How do they fair when the array is more random?

Why sorting Long array is slower than sorting long array using Arrays.sort()?

3 Answers3