CODEWITHSUNDEEP
javaparallel-processingjava-8
Muhammad Hewedy
Muhammad Hewedy

Reputation: 30068

Arrays sort vs parallelSort performance comparision

I've downloaded java8-ea release and did a fast comparison between Array.sort and Arrays.parallelSort.

And this was the result: enter image description here

I can understand that the praralleSort should perform at least as Plain old sort, if not faster.. but this is not what happened.

The Comparison done on the following specs:

HP ProBook Intel Core i5 with 4G RAM on Ubuntu 13.04 Linux with JDK of version: Java HotSpot(TM) 64-Bit Server VM (build 25.0-b23, mixed mode)

I've created an array of Custom object of three fields by this way (add object in reserve order):

package com.cmd;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {

        for (int i=100; i <= 10_000_000; i*=10){
            runTest(i);
        }
    }

    private static void runTest(final int size){

        // Fist obtain two Arrays of same data
        Employee[] empArrForSort = createVeryLargeEmpArray(size);
        Employee[] empArrForSortCopy = Arrays.copyOf(empArrForSort, empArrForSort.length);

        long start = System.currentTimeMillis();
        Arrays.sort(empArrForSort, (e1, e2) -> new Integer(e1.getId()).compareTo(e2.getId()));
        logStart(size + ": sort", start);

        start = System.currentTimeMillis();
        Arrays.parallelSort(empArrForSortCopy, (e1, e2) -> new Integer(e1.getId()).compareTo(e2.getId()));
        logStart(size + ": parallel sort", start);
    }


    private static void logStart(String label, long startTimeMillis) {
        System.out.println("End " + label + " the array. It took: " + (System.currentTimeMillis() - startTimeMillis) + " ms");
    }

    private static Employee[] createVeryLargeEmpArray(final int size) {

        Employee[] ret = new Employee[size];

        for (int i = 0; i < ret.length; i++) {
            ret[i] = Employee.createEmployee(ret.length - i, "Mohammad" + i, "");
        }

        return ret;
    }

    static class Employee {

        private int id;
        private String name;
        private String email;

        private Employee(int id, String name, String email) {
            this.id = id;
            this.name = name;
            this.email = email;
        }

        public static Employee createEmployee(int id, String name, String email) {
            return new Employee(id, name, email);
        }

        public int getId() {
            return id;
        }
    }

}

And, Another run shows that, Parallel only perform pad when the list contains 10,000,000, in all other cases it looks better.

>java -Xmx2000m com.cmd.Main
End 100: sort the array. It took: 110 ms
End 100: parallel sort the array. It took: 6 ms
End 1000: sort the array. It took: 2 ms
End 1000: parallel sort the array. It took: 3 ms
End 10000: sort the array. It took: 11 ms
End 10000: parallel sort the array. It took: 11 ms
End 100000: sort the array. It took: 15 ms
End 100000: parallel sort the array. It took: 37 ms
End 1000000: sort the array. It took: 553 ms
End 1000000: parallel sort the array. It took: 187 ms
End 10000000: sort the array. It took: 640 ms
End 10000000: parallel sort the array. It took: 1099 ms

Upvotes: 2

Views: 2266

Answers (3)

msayag
msayag

Reputation: 8665

The point here is that the array is sorted in reverse order. This is a very unique scenario that does not imply anything about the algorithm general performance. I ran the same code but with unordered arrays:

  ret[i] = Employee.createEmployee(rnd.nextInt(ret.length), "Mohammad" + i, "");

The results show a much slower performance compared to reverse order, while parallelSort is much faster than the simple sort.

End 100: sort the array. It took: 139 ms
End 100: parallel sort the array. It took: 4 ms
End 1000: sort the array. It took: 4 ms
End 1000: parallel sort the array. It took: 6 ms
End 10000: sort the array. It took: 35 ms
End 10000: parallel sort the array. It took: 30 ms
End 100000: sort the array. It took: 420 ms
End 100000: parallel sort the array. It took: 144 ms
End 1000000: sort the array. It took: 1341 ms
End 1000000: parallel sort the array. It took: 506 ms
End 10000000: sort the array. It took: 12200 ms
End 10000000: parallel sort the array. It took: 3971 ms

Upvotes: 9

donsasikumar
donsasikumar

Reputation: 31

Modified just 2 lines in the createVeryLargeEmpArray method as follows.

Random random = new Random();
ret[i] = Employee.createEmployee(ret.length - i+random.nextInt(size), "Mohammad" + i, "");

Here are the results

End 100: sort the array. It took: 27 ms
End 100: parallel sort the array. It took: 1 ms

End 1000: sort the array. It took: 1 ms
End 1000: parallel sort the array. It took: 1 ms

End 10000: sort the array. It took: 7 ms
End 10000: parallel sort the array. It took: 145 ms

End 100000: sort the array. It took: 105 ms
End 100000: parallel sort the array. It took: 59 ms

End 1000000: sort the array. It took: 1050 ms
End 1000000: parallel sort the array. It took: 194 ms

End 10000000: sort the array. It took: 12636 ms
End 10000000: parallel sort the array. It took: 2107 ms

As the number of unsorted elements increases, the parallel sort begins to perform a lot better than the regular sort.

Upvotes: 1

user249800
user249800

Reputation: 1

I've created numerous tests and in the great majority of cases parallelSort performs much better than (serial) sort.

Upvotes: -1

Related Questions