JDK 8: Arrays#sort versus Arrays#parallelSort

                      Smart Techie

                   In this article, we will discuss one of the JDK 8 feature called parallelSort. Before getting into the details of 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 are 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 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 distributes 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 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 sort method is taken approximately 1062 milliseconds.

Advertisements

I am Siva Prasad Rao Janapati. Working as a software developer. Has hands on experience on ATG Commerce(DAS/DPS/DCS), Mozu commerce, Broadleaf Commerce, Java, JEE, Spring, Play, JPA, Hibernate, Velocity, JMS, Jboss, Weblogic,Tomcat, Jetty, Apache, Apache Solr, Spring Batch, JQuery, NodeJS, SOAP, REST, MySQL, Oracle, Mongo DB, Memcached, HazelCast, Git, SVN, CVS, Ant, Maven, Gradle, Amazon Web services, Rackspace, Quartz, JMeter, Junit, Open NLP, Facebook Graph,Twitter4J, YouTube Gdata, Bazzarvoice,Yotpo, 4-Tell, Alatest, Shopzilla, Linkshare. I have hands on experience on open sources and commercial technologies.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

DZone

DZone MVB

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