JDK 8: Arrays#sort versus Arrays#parallelSort

                      Smart Techie

                   In this article, we will discuss one of the JDK 8 feature called parallel sort. Before getting into the details of the parallel sort, we will see sort method implementation.

public static void sort(Object[] a) {
 if (LegacyMergeSort.userRequested)
 legacyMergeSort(a);
 else
 ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

             The sort method will use “merge” sort algorithm Or Tim Peters’s list sort algorithm to sort the elements. “Merge” sort will use divide and conquer method to sort the elements. The lager array will be divided into two parts and then each part of the elements will be divided further until there is no possible way to divide. The individual chunks will be sorted based on “insertion” sort algorithm and then the results will be merged. To sort the larger array, it will have a performance problem.java8

            To avoid this, in JDK 8 we have a new feature called “ParallelSort“. This method will make use of “Fork/Join” framework. This will make use of all available processing power(On multicore processors) to increase the performance. Fork/Join framework will distribute the tasks to worker threads available in the thread pool. The framework will use “work stealing” algorithm. The worker threads which doesn’t have work will steal the work from the busy worker threads.

            The Arrays#parallelSort method will decide whether to sort the array in parallel or in serial. If the array size is less than or equal to 8192 or the processor has only one core, then it will use Dual-Pivot Quicksort algorithm. Otherwise, it will use the parallel sort. The Arrays#parallelSort method is given below.

public static void parallelSort(char[] 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.FJChar.Sorter
 (null, a, new char[n], 0, n, 0,
 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
 MIN_ARRAY_SORT_GRAN : g).invoke();
 }

The sample demo code is given below.


import java.util.Arrays;
public class SampleArrayDemo {

/**
 * @param args
 */
 public static void main(String[] args) {
 double[] arr = new double[10000001];
 for (int index = 0; index < 10000000; index++) {
 arr[index]= Math.random();
 }

 System.out.println("The starting time" + System.currentTimeMillis());
 Arrays.parallelSort(arr);
 //Arrays.sort(arr);
 System.out.println("The end time" + System.currentTimeMillis());
 }
}

               The time taken to sort the array having 10000001 elements is approximately 582 milliseconds. To sort the same array using the sort method is taken approximately 1062 milliseconds.

Siva Janapati is an Architect with experience in building Cloud Native Microservices architectures, Reactive Systems, Large scale distributed systems, and Serverless Systems. Siva has hands-on in architecture, design, and implementation of scalable systems using Cloud, Java, Go lang, Apache Kafka, Apache Solr, Spring, Spring Boot, Lightbend reactive tech stack, APIGEE edge & on-premise and other open-source, proprietary technologies. Expertise working with and building RESTful, GraphQL APIs. He has successfully delivered multiple applications in retail, telco, and financial services domains. He manages the GitHub(https://github.com/2013techsmarts) where he put the source code of his work related to his blog posts.

Tagged with: , , ,
Posted in Java

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

DZone

DZone MVB

Java Code Geeks
Java Code Geeks
%d bloggers like this: