Hoe performantie verbeteren met ParallelSort in JDK 8?
Dit artikel bespreekt een nieuwe mogelijkheid in JDK 8 om perfomantie te verbeteren bij het sorteren van arrays.
Hieronder wordt er voorbeeld code getoond dat een array kan sorteren.
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
De sort methode gebruikt de merge sort algoritme of Tim Peter's list sort algoritme om de elementen te sorteren. “Merge” sort gebruikt verdeel en heers methodes om elementen te sorteren. De grotere array wordt verdeeld in twee delen en dan elk deel van de elementen worden verder verdeeld totdat er geen mogelijkheid is om meer te verdelen. De individuele delen worden gesorteerd op basis van een “insertie” algortime en de resultaten worden gemerged. Om de grotere array te kunnen sorteren, kunnen er performantie problemen optreden.
Om dit te vermijden, is er in JDK 8 een nieuwe feature genaamd ParallelSort. Deze methode maakt gebruik van het “Fork/Join” framework. Dit zal gebruik maken van alle verkrijgbare processor kracht om de performantie te verbeteren. Fork/Join frameworks distribueren de taken naar alle worker threads in de thread pool. Het framework maakt gebruikt van het “work stealing” algoritme. De worker threads dat geen werk hebben stelen het werk van de actieve threads.
De Arrays#parallelSort beslist of het de array in parallel of serieel te sorteren. Als de array size minder is of gelijk is aan 8192 of de processor heeft maar een core, dan wordt er gebruikt gemaakt van de Dual-Pivot Quicksort algoritme. Anders gebruikt het de parallel sort. De Arrays#parallelSort methode wordt hieronder getoond.
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();
}
Het volgende voorbeeld code wordt getoond:
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());
}
}
De tijd om een array te sorteren met 10000001 elementen duurt het ongeveer 582 milliseconden. Om dezelfde array te sorteren via de sort methode neemt het ongeveer 1062 milliseconden in beslag.
Door Stefaan: Java consultant bij ABC-groep
