We often need to sort array while programming. For this, we use inbuilt method provided by Java in Arrays class i.e sort(). sort() method uses merge sort or Time Sort to sort the array elements. In both the cases sort() method sequentially sort the elements of an array.
In Java 8, there is a new API introduced for sorting which is Parallel Sorting. Parallel Sort uses Fork/Join framework introduced in Java 7 to assign the sorting tasks to multiple threads available in the thread pool. Fork/Join implements a work stealing algorithm where in a idle thread can steal tasks queued up in another thread.
For Example, the following code is a program that sorts a randomized array of doubles using Arrays.sort() and Arrays.parallelSort(). This program simply measures the performance difference between this two approaches. :
java
// Java program to demonstrate time taken by sort()// and parallelSort() methods.import java.util.Arrays; public class ParallelSortTest{ private static final int BASE_ARRAY_SIZE = 10000; // A utility function to generate and return // an array of given size filled with randomly // generated elements. public static double[] generateArray(int size) { if (size <= 0 || size > Integer.MAX_VALUE) return null; double[] result = new double[size]; for (int i = 0; i < size; i++) result[i] = Math.random(); return result; } // Driver code to compare two sortings public static void main(String[] args) { for (int i = 1; i < 10000; i *= 10) { int size = BASE_ARRAY_SIZE * i; double[] arr1 = generateArray(size); // Creating a copy of arr1 so that we can // use same content for both sortings. double[] arr2 = Arrays.copyOf(arr1, arr1.length); System.out.println("Array Size: " + size); // Sorting arr1[] using serial sort long startTime = System.currentTimeMillis(); Arrays.sort(arr1); long endTime = System.currentTimeMillis(); System.out.println("Time take in serial: " + (endTime - startTime) + "ms."); // Sorting arr2[] using serial sort startTime = System.currentTimeMillis(); Arrays.parallelSort(arr2); endTime = System.currentTimeMillis(); System.out.println("Time take in parallel: " + (endTime - startTime) + "ms."); System.out.println(); } }} |
Environment :
2.6 GHz Intel Core i7 java version "1.8.0_25"
Time Complexity: O(N log(N))
Auxiliary Space: O(N)
Note : Required Time may vary due to random values in the array. The key differences between both the algorithm are as follow : 1) Arrays.sort() : is a sequential sorting.
- The API uses single thread for the operation.
- It takes bit longer time to perform the operation.
2. Arrays.ParallelSort() : is a parallel sorting.
- The API uses multiple threads for the operation.
- It’s faster when there are a lot of elements whereas slower for lesser elements.
Analysis : The results show that parallel sorting on a multicore machine can achieve performance improvements at 1 million or more elements. While below this threshold it may actually be slower than sequential sorting. This result meets the expectation, and the suitable size here may be 1 million. Your mileage may vary, it depends on your environment. Explanation : Now, let’s take a look at the code to figure out how this parallel sorting works.
public static void parallelSort(double[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJDouble.Sorter
(null, a, new double[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
As we can see, there is a minimum granularity (java.util.Arrays.MIN_ARRAY_SORT_GRAN = 8192 [0x2000]), and if the length of the array is less than the minimum granularity, it is sorted using the DualPivotQuicksort.sort directly instead of the sorting task partition. Typically, using smaller sizes results in memory contention across tasks that makes parallel speedups unlikely.
Another notable judgement is ForkJoinPool.getCommonPoolParallelism() which returns the targeted parallelism level of the common pool (by default, equal to the number of available processors Runtime.getRuntime().availableProcessors()). And if your machine has only 1 worker thread, it will not use parallel task either.
When the array length reaches a minimum granularity and you got more than 1 worker thread, the array is sorted using the parallel sort method. And the ForkJoin common pool is used to execute parallel tasks here.
Reference : http://download.java.net/lambda/b84/docs/api/java/util/Arrays.html#parallelSort%28int
This article is contributed by Saumya Mishra. If you like Lazyroar and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the Lazyroar main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
