1,3c1,3 < --- old/src/java.base/share/classes/java/util/Arrays.java 2019-07-17 17:04:35.860314325 +0200 < +++ new/src/java.base/share/classes/java/util/Arrays.java 2019-07-17 17:04:35.556314329 +0200 < @@ -1,8927 +1,8716 @@ --- > --- old/src/java.base/share/classes/java/util/Arrays.java 2019-07-26 10:05:32.132098858 +0200 > +++ new/src/java.base/share/classes/java/util/Arrays.java 2019-07-26 10:05:31.992098859 +0200 > @@ -1,8927 +1,8717 @@ 9316a9317,9321 > + * Common pool parallelism for paralle sorting. > + */ > + private static final int COMMON_PARALLELISM = ForkJoinPool.getCommonPoolParallelism(); > + > + /** 9329c9334 < + DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length); --- > + DualPivotQuicksort.sort(a, COMMON_PARALLELISM, 0, a.length); 9355c9360 < + DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex); --- > + DualPivotQuicksort.sort(a, COMMON_PARALLELISM, fromIndex, toIndex); 9371c9376 < + DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length); --- > + DualPivotQuicksort.sort(a, COMMON_PARALLELISM, 0, a.length); 9397c9402 < + DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex); --- > + DualPivotQuicksort.sort(a, COMMON_PARALLELISM, fromIndex, toIndex); 9547c9552 < + DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length); --- > + DualPivotQuicksort.sort(a, COMMON_PARALLELISM, 0, a.length); 9581c9586 < + DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex); --- > + DualPivotQuicksort.sort(a, COMMON_PARALLELISM, fromIndex, toIndex); 9605c9610 < + DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), 0, a.length); --- > + DualPivotQuicksort.sort(a, COMMON_PARALLELISM, 0, a.length); 9639c9644 < + DualPivotQuicksort.sort(a, ForkJoinPool.getCommonPoolParallelism(), fromIndex, toIndex); --- > + DualPivotQuicksort.sort(a, COMMON_PARALLELISM, fromIndex, toIndex); 9727,9728c9732 < + if (n <= MIN_ARRAY_SORT_GRAN || < + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) --- > + if (n <= MIN_ARRAY_SORT_GRAN || (p = COMMON_PARALLELISM) == 1) 9786,9787c9790 < + if (n <= MIN_ARRAY_SORT_GRAN || < + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) --- > + if (n <= MIN_ARRAY_SORT_GRAN || (p = COMMON_PARALLELISM) == 1) 9835,9836c9838 < + if (n <= MIN_ARRAY_SORT_GRAN || < + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) --- > + if (n <= MIN_ARRAY_SORT_GRAN || (p = COMMON_PARALLELISM) == 1) 9896,9897c9898 < + if (n <= MIN_ARRAY_SORT_GRAN || < + (p = ForkJoinPool.getCommonPoolParallelism()) == 1) --- > + if (n <= MIN_ARRAY_SORT_GRAN || (p = COMMON_PARALLELISM) == 1) 17647,17648c17648,17649 < --- old/src/java.base/share/classes/java/util/ArraysParallelSortHelpers.java 2019-07-17 17:04:36.548314315 +0200 < +++ new/src/java.base/share/classes/java/util/ArraysParallelSortHelpers.java 2019-07-17 17:04:36.248314319 +0200 --- > --- old/src/java.base/share/classes/java/util/ArraysParallelSortHelpers.java 2019-07-26 10:05:32.784098849 +0200 > +++ new/src/java.base/share/classes/java/util/ArraysParallelSortHelpers.java 2019-07-26 10:05:32.664098850 +0200 18887,18888c18888,18889 < --- old/src/java.base/share/classes/java/util/DualPivotQuicksort.java 2019-07-17 17:04:37.096314307 +0200 < +++ new/src/java.base/share/classes/java/util/DualPivotQuicksort.java 2019-07-17 17:04:36.780314312 +0200 --- > --- old/src/java.base/share/classes/java/util/DualPivotQuicksort.java 2019-07-26 10:05:33.332098841 +0200 > +++ new/src/java.base/share/classes/java/util/DualPivotQuicksort.java 2019-07-26 10:05:33.212098843 +0200 18944c18945 < + * @since 14 --- > + * @since 1.7 * 14 18948c18949 < @@ -51,3131 +55,4319 @@ --- > @@ -51,3131 +55,4102 @@ 19248c19249 < + if (parallelism > 0 && size > MIN_PARALLEL_SORT_SIZE) { --- > + if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) { 19376,19378c19377 < + * Sort these elements in place by the combination < + * of 4-element sorting network and insertion sort. < * --- > - * 19386c19385,19387 < - * --- > + * Sort these elements in place by the combination > + * of 4-element sorting network and insertion sort. > * 19394c19395 < + * 5 ------o-----------o----------- --- > + * 5 ------o-----------o------------ 19396c19397 < + * 4 ------|-----o-----o-----o----- --- > + * 4 ------|-----o-----o-----o------ 19398c19399 < + * 2 ------o-----|-----o-----o----- --- > + * 2 ------o-----|-----o-----o------ 19400c19401 < + * 1 ------------o-----o----------- --- > + * 1 ------------o-----o------------ 19471,19472c19472 < /* < - * Skip elements, which are equal to pivot values. --- > + /* 19476,19478c19476 < */ < - while (a[less] == pivot1) { < - ++less; --- > + */ 19492c19490,19491 < + /* --- > /* > - * Skip elements, which are equal to pivot values. 19494c19493,19495 < + */ --- > */ > - while (a[less] == pivot1) { > - ++less; 19561,19562c19562 < /* < - * Partitioning: --- > + /* 19577c19577,19578 < + /* --- > /* > - * Partitioning: 19883c19884 < } --- > + } 19926c19927 < + } --- > } 19957a19959,19966 > + > + /* > + * Find the end index of the current run. > + */ > + if (a[k - 1] < a[k]) { > + > + // Identify ascending sequence > + while (++k < high && a[k - 1] <= a[k]); 19972,19979d19980 < + /* < + * Find the end index of the current run. < + */ < + if (a[k - 1] < a[k]) { < + < + // Identify ascending sequence < + while (++k < high && a[k - 1] <= a[k]); < + 20166c20167 < + } --- > } 20186c20187 < } --- > + } 20371,20374c20372 < < - // Pointers < - int less = left; // The index of the first element of center part < - int great = right; // The index before the first element of right part --- > + 20395c20393 < + if (parallelism > 0 && size > MIN_PARALLEL_SORT_SIZE) { --- > + if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) { 20403c20401,20404 < + --- > > - // Pointers > - int less = left; // The index of the first element of center part > - int great = right; // The index before the first element of right part 20418,20425d20418 < + < + /* < + * Run mixed insertion sort on small non-leftmost parts. < + */ < + if (size < MAX_MIXED_INSERTION_SORT_SIZE && (bits & 1) > 0) { < + mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high); < + return; < + } 20432c20425 < + * Invoke insertion sort on small leftmost part. --- > + * Run mixed insertion sort on small non-leftmost parts. 20436,20437c20429,20430 < + if (size < MAX_INSERTION_SORT_SIZE) { < + insertionSort(a, low, high); --- > + if (size < MAX_MIXED_INSERTION_SORT_SIZE && (bits & 1) > 0) { > + mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high); 20446,20447c20439 < + * Check if the whole array or large non-leftmost < + * parts are nearly sorted and then merge runs. --- > + * Invoke insertion sort on small leftmost part. 20451,20452c20443,20444 < + if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0) < + && tryMergeRuns(sorter, a, low, size)) { --- > + if (size < MAX_INSERTION_SORT_SIZE) { > + insertionSort(a, low, high); 20458,20459c20450,20451 < + * Switch to heap sort if execution < + * time is becoming quadratic. --- > + * Check if the whole array or large non-leftmost > + * parts are nearly sorted and then merge runs. 20463,20464c20455,20456 < + if ((bits += 2) > MAX_RECURSION_DEPTH) { < + heapSort(a, low, high); --- > + if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0) > + && tryMergeRuns(sorter, a, low, size)) { 20483a20476,20484 > + * Switch to heap sort if execution > + * time is becoming quadratic. > + */ > + if ((bits += 2) > MAX_RECURSION_DEPTH) { > + heapSort(a, low, high); > + return; > + } > + > + /* 20507c20508 < + * 5 ------o-----------o----------- --- > + * 5 ------o-----------o------------ 20509c20510 < + * 4 ------|-----o-----o-----o----- --- > + * 4 ------|-----o-----o-----o------ 20511c20512 < + * 2 ------o-----|-----o-----o----- --- > + * 2 ------o-----|-----o-----o------ 20513c20514 < + * 1 ------------o-----o----------- --- > + * 1 ------------o-----o------------ 20592c20593,20594 < + /* --- > /* > - * Skip elements, which are equal to pivot values. 20602,20603c20604 < /* < - * Skip elements, which are equal to pivot values. --- > + /* 20605,20607c20606 < */ < - while (a[less] == pivot1) { < - ++less; --- > + */ 20629c20628,20630 < + */ --- > */ > - while (a[less] == pivot1) { > - ++less; 20680,20681c20681 < /* < - * Partitioning: --- > + /* 20690c20690,20691 < + /* --- > /* > - * Partitioning: 20892,20894c20893 < } < - a[great] = ak; < - --great; --- > + } 20917c20916,20918 < + } --- > } > - a[great] = ak; > - --great; 21022c21023,21026 < + --- > > - do { > - a[--k] = value; > - } while (--s > 0); 21035,21038c21039 < < - do { < - a[--k] = value; < - } while (--s > 0); --- > + 21106a21108,21109 > + > + } else if (a[k - 1] > a[k]) { 21121,21122d21123 < + } else if (a[k - 1] > a[k]) { < + 21307c21308 < + } --- > } 21327c21328 < } --- > + } 21484,21489d21484 < - < - // Sort these elements using insertion sort < - if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; } < - < - if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t; < - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } 21497,21500c21492 < } < - if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t; < - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; < - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } --- > + } 21504,21509c21496,21497 < } < } < - if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t; < - if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t; < - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; < - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } --- > + } > + } 21511c21499,21501 < + --- > > - // Sort these elements using insertion sort > - if (a[e2] < a[e1]) { short t = a[e2]; a[e2] = a[e1]; a[e1] = t; } 21513c21503,21505 < + --- > > - if (a[e3] < a[e2]) { short t = a[e3]; a[e3] = a[e2]; a[e2] = t; > - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } 21527c21519,21522 < + } --- > } > - if (a[e4] < a[e3]) { short t = a[e4]; a[e4] = a[e3]; a[e3] = t; > - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; > - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } 21544c21539 < } --- > + } 21547a21543,21547 > - if (a[e5] < a[e4]) { short t = a[e5]; a[e5] = a[e4]; a[e4] = t; > - if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t; > - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; > - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } > - } 21549,21552c21549 < < - // Pointers < - int less = left; // The index of the first element of center part < - int great = right; // The index before the first element of right part --- > + 21581,21584c21578,21597 < + for (int k = high, i = MAX_BYTE_INDEX; --i > Byte.MAX_VALUE; ) { < + int value = i & 0xFF; < + for (low = k - count[value]; k > low; a[--k] = (byte) value); < + } --- > + if (high - low > NUM_BYTE_VALUES) { > + for (int i = MAX_BYTE_INDEX; --i > Byte.MAX_VALUE; ) { > + int value = i & 0xFF; > + > + for (low = high - count[value]; high > low; > + a[--high] = (byte) value > + ); > + } > + } else { > + for (int i = MAX_BYTE_INDEX; high > low; ) { > + while (count[--i & 0xFF] == 0); > + > + int value = i & 0xFF; > + int c = count[value]; > + > + do { > + a[--high] = (byte) value; > + } while (--c > 0); > } > } 21604c21617,21620 < + --- > > - // Pointers > - int less = left; // The index of the first element of center part > - int great = right; // The index before the first element of right part 21624c21640 < + * Run mixed insertion sort on small non-leftmost parts. --- > + * Invoke insertion sort on small leftmost part. 21628,21629c21644,21645 < + if (size < MAX_MIXED_INSERTION_SORT_SIZE && (bits & 1) > 0) { < + mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high); --- > + if (size < MAX_INSERTION_SORT_SIZE) { > + insertionSort(a, low, high); 21638c21654,21655 < + * Invoke insertion sort on small leftmost part. --- > + * Switch to counting sort if execution > + * time is becoming quadratic. 21642,21643c21659,21660 < + if (size < MAX_INSERTION_SORT_SIZE) { < + insertionSort(a, low, high); --- > + if ((bits += 2) > MAX_RECURSION_DEPTH) { > + countingSort(a, low, high); 21649,21650c21666,21667 < + * Switch to counting sort if execution < + * time is becoming quadratic. --- > + * Use an inexpensive approximation of the golden ratio > + * to select five sample elements and determine pivots. 21654,21657c21671 < + if ((bits += 2) > MAX_RECURSION_DEPTH) { < + countingSort(a, low, high); < + return; < + } --- > + int step = (size >> 3) * 3 + 3; 21675,21680d21688 < + * Use an inexpensive approximation of the golden ratio < + * to select five sample elements and determine pivots. < + */ < + int step = (size >> 3) * 3 + 3; < + < + /* 21698c21706 < + * 5 ------o-----------o----------- --- > + * 5 ------o-----------o------------ 21700c21708 < + * 4 ------|-----o-----o-----o----- --- > + * 4 ------|-----o-----o-----o------ 21702c21710 < + * 2 ------o-----|-----o-----o----- --- > + * 2 ------o-----|-----o-----o------ 21704c21712 < + * 1 ------------o-----o----------- --- > + * 1 ------------o-----o------------ 21799,21800c21807,21809 < + < + /* --- > > /* > - * Partitioning: 21805,21807c21814,21815 < < /* < - * Partitioning: --- > + > + /* 21877a21886,21888 > - } > - a[great] = ak; > - --great; 21881,21883c21892,21897 < + } < + } < + --- > } > } > - } > > - // Sort center part recursively > - sort(a, less, great, false); 21889c21903,21909 < + --- > > - } else { // Partitioning with one pivot > - /* > - * Use the third of the five sorted elements as pivot. > - * This value is inexpensive approximation of the median. > - */ > - short pivot = a[e3]; 21896c21916,21962 < + --- > > - /* > - * Partitioning degenerates to the traditional 3-way > - * (or "Dutch National Flag") schema: > - * > - * left part center part right part > - * +-------------------------------------------------+ > - * | < pivot | == pivot | ? | > pivot | > - * +-------------------------------------------------+ > - * ^ ^ ^ > - * | | | > - * less k great > - * > - * Invariants: > - * > - * all in (left, less) < pivot > - * all in [less, k) == pivot > - * all in (great, right) > pivot > - * > - * Pointer k is the first index of ?-part. > - */ > - for (int k = less; k <= great; ++k) { > - if (a[k] == pivot) { > - continue; > - } > - short ak = a[k]; > - if (ak < pivot) { // Move a[k] to left part > - a[k] = a[less]; > - a[less] = ak; > - ++less; > - } else { // a[k] > pivot - Move a[k] to right part > - while (a[great] > pivot) { > - --great; > - } > - if (a[great] < pivot) { // a[great] <= pivot > - a[k] = a[less]; > - a[less] = a[great]; > - ++less; > - } else { // a[great] == pivot > - /* > - * Even though a[great] equals to pivot, the > - * assignment a[k] = pivot may be incorrect, > - * if a[great] and pivot are floating-point > - * zeros of different signs. Therefore in float > - * and double sorting methods we have to use > - * more accurate assignment a[k] = a[great]. > - */ 21937c22003 < + a[k] = pivot; --- > a[k] = pivot; 21948,21950c22014 < } < - a[great] = ak; < - --great; --- > + } 21951a22016,22017 > - a[great] = ak; > - --great; 21970,21971c22036,22042 < - // Sort center part recursively < - sort(a, less, great, false); --- > - /* > - * Sort left and right parts recursively. > - * All elements from center part are equal > - * and, therefore, already sorted. > - */ > - sort(a, left, less - 1, leftmost); > - sort(a, great + 1, right, false); 21973,21982c22044 < + * Sorts the specified range of the array using mixed insertion sort. < + * < + * Mixed insertion sort is combination of simple insertion sort, < + * pin insertion sort and pair insertion sort. < + * < + * In the context of Dual-Pivot Quicksort, the pivot element < + * from the left part plays the role of sentinel, because it < + * is less than any elements from the given part. Therefore, < + * expensive check of the left range can be skipped on each < + * iteration unless it is the leftmost call. --- > + * Sorts the specified range of the array using insertion sort. 21986d22047 < + * @param end the index of the last element for simple insertion sort 21989,22000c22050,22052 < + private static void mixedInsertionSort(char[] a, int low, int end, int high) { < + if (end == high) { < < - } else { // Partitioning with one pivot < /* < - * Use the third of the five sorted elements as pivot. < - * This value is inexpensive approximation of the median. < + * Invoke simple insertion sort on tiny array. < */ < - short pivot = a[e3]; < + for (int i; ++low < end; ) { < + char ai = a[i = low]; --- > + private static void insertionSort(char[] a, int low, int high) { > + for (int i, k = low; ++k < high; ) { > + char ai = a[i = k]; 22002c22054,22055 < + while (ai < a[--i]) { --- > + if (ai < a[i - 1]) { > + while (--i >= low && ai < a[i]) { 22007,22146d22059 < + } else { < < /* < - * Partitioning degenerates to the traditional 3-way < - * (or "Dutch National Flag") schema: < + * Start with pin insertion sort on small part. < * < - * left part center part right part < - * +-------------------------------------------------+ < - * | < pivot | == pivot | ? | > pivot | < - * +-------------------------------------------------+ < - * ^ ^ ^ < - * | | | < - * less k great < - * < - * Invariants: < - * < - * all in (left, less) < pivot < - * all in [less, k) == pivot < - * all in (great, right) > pivot < - * < - * Pointer k is the first index of ?-part. < + * Pin insertion sort is extended simple insertion sort. < + * The main idea of this sort is to put elements larger < + * than an element called pin to the end of array (the < + * proper area for such elements). It avoids expensive < + * movements of these elements through the whole array. < */ < - for (int k = less; k <= great; ++k) { < - if (a[k] == pivot) { < - continue; < - } < - short ak = a[k]; < - if (ak < pivot) { // Move a[k] to left part < - a[k] = a[less]; < - a[less] = ak; < - ++less; < - } else { // a[k] > pivot - Move a[k] to right part < - while (a[great] > pivot) { < - --great; < - } < - if (a[great] < pivot) { // a[great] <= pivot < - a[k] = a[less]; < - a[less] = a[great]; < - ++less; < - } else { // a[great] == pivot < - /* < - * Even though a[great] equals to pivot, the < - * assignment a[k] = pivot may be incorrect, < - * if a[great] and pivot are floating-point < - * zeros of different signs. Therefore in float < - * and double sorting methods we have to use < - * more accurate assignment a[k] = a[great]. < - */ < - a[k] = pivot; < + char pin = a[end]; < + < + for (int i, p = high; ++low < end; ) { < + char ai = a[i = low]; < + < + if (ai < a[i - 1]) { // Small element < + < + /* < + * Insert small element into sorted part. < + */ < + a[i] = a[--i]; < + < + while (ai < a[--i]) { < + a[i + 1] = a[i]; < } < - a[great] = ak; < - --great; < + a[i + 1] = ai; < + < + } else if (p > i && ai > pin) { // Large element < + < + /* < + * Find element smaller than pin. < + */ < + while (a[--p] > pin); < + < + /* < + * Swap it with large element. < + */ < + if (p > i) { < + ai = a[p]; < + a[p] = a[i]; < + } < + < + /* < + * Insert small element into sorted part. < + */ < + while (ai < a[--i]) { < + a[i + 1] = a[i]; < + } < + a[i + 1] = ai; < } < } < < /* < - * Sort left and right parts recursively. < - * All elements from center part are equal < - * and, therefore, already sorted. < + * Continue with pair insertion sort on remain part. < */ < - sort(a, left, less - 1, leftmost); < - sort(a, great + 1, right, false); < + for (int i; low < high; ++low) { < + char a1 = a[i = low], a2 = a[++low]; < + < + /* < + * Insert two elements per iteration: at first, insert the < + * larger element and then insert the smaller element, but < + * from the position where the larger element was inserted. < + */ < + if (a1 > a2) { < + < + while (a1 < a[--i]) { < + a[i + 2] = a[i]; < + } < + a[++i + 1] = a1; < + < + while (a2 < a[--i]) { < + a[i + 1] = a[i]; < + } < + a[i + 1] = a2; < + < + } else if (a1 < a[i - 1]) { < + < + while (a2 < a[--i]) { < + a[i + 2] = a[i]; < + } < + a[++i + 1] = a2; < + < + while (a1 < a[--i]) { < + a[i + 1] = a[i]; < + } < + a[i + 1] = a1; < + } < + } 22153c22066,22071 < + * Sorts the specified range of the array using insertion sort. --- > + * The number of distinct char values. > + */ > + private static final int NUM_CHAR_VALUES = 1 << 16; > + > + /** > + * Sorts the specified range of the array using counting sort. 22169c22087,22089 < - --- > + private static void countingSort(char[] a, int low, int high) { > + int[] count = new int[NUM_CHAR_VALUES]; > 22174c22094,22110 < - while (count[--i] == 0); --- > + /* > + * Compute a histogram with the number of each values. > + */ > + for (int i = high; i > low; ++count[a[--i]]); > + > + /* > + * Place values on their final positions. > + */ > + if (high - low > NUM_CHAR_VALUES) { > + for (int i = NUM_CHAR_VALUES; i > 0; ) { > + for (low = high - count[--i]; high > low; > + a[--high] = (char) i > + ); > + } > + } else { > + for (int i = NUM_CHAR_VALUES; high > low; ) { > while (count[--i] == 0); 22177,22178c22113,22115 < - < - do { --- > + int c = count[i]; > > do { 22181,22189c22118,22119 < + private static void insertionSort(char[] a, int low, int high) { < + for (int i, k = low; ++k < high; ) { < + char ai = a[i = k]; < + < + if (ai < a[i - 1]) { < + while (--i >= low && ai < a[i]) { < + a[i + 1] = a[i]; < + } < + a[i + 1] = ai; --- > + a[--high] = (char) i; > + } while (--c > 0); 22197,22200c22127,22128 < + /** < + * The number of distinct char values. < + */ < private static final int NUM_CHAR_VALUES = 1 << 16; --- > - private static final int NUM_CHAR_VALUES = 1 << 16; > +// [short] 22204c22132,22133 < + * Sorts the specified range of the array using counting sort. --- > + * Sorts the specified range of the array using > + * counting sort or Dual-Pivot Quicksort. 22219d22147 < - } 22223,22224c22151,22157 < + private static void countingSort(char[] a, int low, int high) { < + int[] count = new int[NUM_CHAR_VALUES]; --- > + static void sort(short[] a, int low, int high) { > + if (high - low > MIN_SHORT_OR_CHAR_COUNTING_SORT_SIZE) { > + countingSort(a, low, high); > + } else { > + sort(a, 0, low, high); > } > + } 22226c22159 < /* --- > - /* 22229,22230c22162 < + * Compute a histogram with the number of each values. < */ --- > - */ 22233,22234c22165 < + for (int i = high; i > low; ++count[a[--i]]); < --- > - 22249,22274c22180 < + /* < + * Place values on their final positions. < + */ < + for (int k = high, i = NUM_CHAR_VALUES; --i > -1; ) { < + for (low = k - count[i]; k > low; a[--k] = (char) i); < + } < + } < + < +// [short] < + < + /** < + * Sorts the specified range of the array using < + * counting sort or Dual-Pivot Quicksort. < + * < + * @param a the array to be sorted < + * @param low the index of the first element, inclusive, to be sorted < + * @param high the index of the last element, exclusive, to be sorted < + */ < + static void sort(short[] a, int low, int high) { < + if (high - low > MIN_SHORT_OR_CHAR_COUNTING_SORT_SIZE) { < + countingSort(a, low, high); < + } else { < + sort(a, 0, low, high); < + } < + } < + --- > - } 22288,22295d22193 < + < + /* < + * Run mixed insertion sort on small non-leftmost parts. < + */ < + if (size < MAX_MIXED_INSERTION_SORT_SIZE && (bits & 1) > 0) { < + mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high); < + return; < } 22401c22299 < + * 5 ------o-----------o----------- --- > + * 5 ------o-----------o------------ 22403c22301 < + * 4 ------|-----o-----o-----o----- --- > + * 4 ------|-----o-----o-----o------ 22405c22303 < + * 2 ------o-----|-----o-----o----- --- > + * 2 ------o-----|-----o-----o------ 22407c22305 < + * 1 ------------o-----o----------- --- > + * 1 ------------o-----o------------ 22428c22326 < } --- > - } 22434c22332,22347 < + --- > } > - char[] t = a; a = b; b = t; > - int o = ao; ao = bo; bo = o; > - } > - } > > - /** > - * Sorts the specified range of the array by Dual-Pivot Quicksort. > - * > - * @param a the array to be sorted > - * @param left the index of the first element, inclusive, to be sorted > - * @param right the index of the last element, inclusive, to be sorted > - * @param leftmost indicates if this part is the leftmost in the range > - */ > - private static void sort(char[] a, int left, int right, boolean leftmost) { > - int length = right - left + 1; 22467,22468c22380,22387 < + < + /* --- > > - // Use insertion sort on tiny arrays > - if (length < INSERTION_SORT_THRESHOLD) { > - if (leftmost) { > /* > - * Traditional (without sentinel) insertion sort, > - * optimized for server VM, is used in case of > - * the leftmost part. 22486c22405,22411 < + */ --- > */ > - for (int i = left, j = i; i < right; j = ++i) { > - char ai = a[i + 1]; > - while (ai < a[j]) { > - a[j + 1] = a[j]; > - if (j-- == left) { > - break; 22502c22427 < + } --- > } 22506,22507c22431,22434 < + } < + } --- > } > - a[j + 1] = ai; > } > - } else { 22509c22436,22437 < + /* --- > /* > - * Skip the longest ascending sequence. 22511c22439,22444 < + */ --- > */ > - do { > - if (left >= right) { > - return; > - } > - } while (a[++left] >= a[left - 1]); 22514,22515c22447,22454 < + < + /* --- > > /* > - * Every element from adjoining part plays the role > - * of sentinel, therefore this allows us to avoid the > - * left range check on each iteration. Moreover, we use > - * the more optimized algorithm, so called pair insertion > - * sort, which is faster (in the context of Quicksort) > - * than traditional implementation of insertion sort. 22518c22457,22459 < + */ --- > */ > - for (int k = left; ++left <= right; k = ++left) { > - char a1 = a[k], a2 = a[left]; 22521c22462,22469 < + --- > > - if (a1 < a2) { > - a2 = a1; a1 = a[left]; > - } > - while (a1 < a[--k]) { > - a[k + 2] = a[k]; > - } > - a[++k + 1] = a1; 22538c22486,22488 < + --- > > - while (a2 < a[--k]) { > - a[k + 1] = a[k]; 22574,22576c22524,22530 < + } < + } < + --- > } > - a[k + 1] = a2; > } > - char last = a[right]; > > - while (last < a[--right]) { > - a[right + 1] = a[right]; 22588,22761d22541 < } < - char[] t = a; a = b; b = t; < - int o = ao; ao = bo; bo = o; < + high = lower; // Iterate along the left part < } < } < < /** < - * Sorts the specified range of the array by Dual-Pivot Quicksort. < + * Sorts the specified range of the array using mixed insertion sort. < + * < + * Mixed insertion sort is combination of simple insertion sort, < + * pin insertion sort and pair insertion sort. < + * < + * In the context of Dual-Pivot Quicksort, the pivot element < + * from the left part plays the role of sentinel, because it < + * is less than any elements from the given part. Therefore, < + * expensive check of the left range can be skipped on each < + * iteration unless it is the leftmost call. < * < * @param a the array to be sorted < - * @param left the index of the first element, inclusive, to be sorted < - * @param right the index of the last element, inclusive, to be sorted < - * @param leftmost indicates if this part is the leftmost in the range < + * @param low the index of the first element, inclusive, to be sorted < + * @param end the index of the last element for simple insertion sort < + * @param high the index of the last element, exclusive, to be sorted < */ < - private static void sort(char[] a, int left, int right, boolean leftmost) { < - int length = right - left + 1; < + private static void mixedInsertionSort(short[] a, int low, int end, int high) { < + if (end == high) { < < - // Use insertion sort on tiny arrays < - if (length < INSERTION_SORT_THRESHOLD) { < - if (leftmost) { < - /* < - * Traditional (without sentinel) insertion sort, < - * optimized for server VM, is used in case of < - * the leftmost part. < - */ < - for (int i = left, j = i; i < right; j = ++i) { < - char ai = a[i + 1]; < - while (ai < a[j]) { < - a[j + 1] = a[j]; < - if (j-- == left) { < - break; < - } < - } < - a[j + 1] = ai; < + /* < + * Invoke simple insertion sort on tiny array. < + */ < + for (int i; ++low < end; ) { < + short ai = a[i = low]; < + < + while (ai < a[--i]) { < + a[i + 1] = a[i]; < } < - } else { < - /* < - * Skip the longest ascending sequence. < - */ < - do { < - if (left >= right) { < - return; < + a[i + 1] = ai; < + } < + } else { < + < + /* < + * Start with pin insertion sort on small part. < + * < + * Pin insertion sort is extended simple insertion sort. < + * The main idea of this sort is to put elements larger < + * than an element called pin to the end of array (the < + * proper area for such elements). It avoids expensive < + * movements of these elements through the whole array. < + */ < + short pin = a[end]; < + < + for (int i, p = high; ++low < end; ) { < + short ai = a[i = low]; < + < + if (ai < a[i - 1]) { // Small element < + < + /* < + * Insert small element into sorted part. < + */ < + a[i] = a[--i]; < + < + while (ai < a[--i]) { < + a[i + 1] = a[i]; < + } < + a[i + 1] = ai; < + < + } else if (p > i && ai > pin) { // Large element < + < + /* < + * Find element smaller than pin. < + */ < + while (a[--p] > pin); < + < + /* < + * Swap it with large element. < + */ < + if (p > i) { < + ai = a[p]; < + a[p] = a[i]; < } < - } while (a[++left] >= a[left - 1]); < + < + /* < + * Insert small element into sorted part. < + */ < + while (ai < a[--i]) { < + a[i + 1] = a[i]; < + } < + a[i + 1] = ai; < + } < + } < + < + /* < + * Continue with pair insertion sort on remain part. < + */ < + for (int i; low < high; ++low) { < + short a1 = a[i = low], a2 = a[++low]; < < /* < - * Every element from adjoining part plays the role < - * of sentinel, therefore this allows us to avoid the < - * left range check on each iteration. Moreover, we use < - * the more optimized algorithm, so called pair insertion < - * sort, which is faster (in the context of Quicksort) < - * than traditional implementation of insertion sort. < + * Insert two elements per iteration: at first, insert the < + * larger element and then insert the smaller element, but < + * from the position where the larger element was inserted. < */ < - for (int k = left; ++left <= right; k = ++left) { < - char a1 = a[k], a2 = a[left]; < + if (a1 > a2) { < + < + while (a1 < a[--i]) { < + a[i + 2] = a[i]; < + } < + a[++i + 1] = a1; < < - if (a1 < a2) { < - a2 = a1; a1 = a[left]; < + while (a2 < a[--i]) { < + a[i + 1] = a[i]; < } < - while (a1 < a[--k]) { < - a[k + 2] = a[k]; < + a[i + 1] = a2; < + < + } else if (a1 < a[i - 1]) { < + < + while (a2 < a[--i]) { < + a[i + 2] = a[i]; < } < - a[++k + 1] = a1; < + a[++i + 1] = a2; < < - while (a2 < a[--k]) { < - a[k + 1] = a[k]; < + while (a1 < a[--i]) { < + a[i + 1] = a[i]; < } < - a[k + 1] = a2; < + a[i + 1] = a1; < } < - char last = a[right]; 22762a22543 > + high = lower; // Iterate along the left part 22765,22767c22546 < < - while (last < a[--right]) { < - a[right + 1] = a[right]; --- > + 22794c22573,22575 < + --- > > - // Inexpensive approximation of length / 7 > - int seventh = (length >> 3) + (length >> 6) + 1; 22809,22810c22590,22596 < + < + /* --- > > /* > - * Sort five evenly spaced elements around (and including) the > - * center element in the range. These elements will be used for > - * pivot selection as described below. The choice for spacing > - * these elements was empirically determined to work well on > - * a wide variety of inputs. 22812c22598,22603 < + */ --- > */ > - int e3 = (left + right) >>> 1; // The midpoint > - int e2 = e3 - seventh; > - int e1 = e2 - seventh; > - int e4 = e3 + seventh; > - int e5 = e4 + seventh; 22818,22822c22609,22619 < + for (int k = high, i = MAX_SHORT_INDEX; --i > Short.MAX_VALUE; ) { < + int value = i & 0xFFFF; < + for (low = k - count[value]; k > low; a[--k] = (short) value); < + } < + } --- > + if (high - low > NUM_SHORT_VALUES) { > + for (int i = MAX_SHORT_INDEX; --i > Short.MAX_VALUE; ) { > + int value = i & 0xFFFF; > + > + for (low = high - count[value]; high > low; > + a[--high] = (short) value > + ); > + } > + } else { > + for (int i = MAX_SHORT_INDEX; high > low; ) { > + while (count[--i & 0xFFFF] == 0); 22824,22826c22621,22624 < - // Inexpensive approximation of length / 7 < - int seventh = (length >> 3) + (length >> 6) + 1; < +// [float] --- > - // Sort these elements using insertion sort > - if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; } > + int value = i & 0xFFFF; > + int c = count[value]; 22827a22626,22639 > - if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t; > - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } > + do { > + a[--high] = (short) value; > + } while (--c > 0); > + } > } > - if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t; > - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; > - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } > + } > + > +// [float] > + 22844,22849c22656 < /* < - * Sort five evenly spaced elements around (and including) the < - * center element in the range. These elements will be used for < - * pivot selection as described below. The choice for spacing < - * these elements was empirically determined to work well on < - * a wide variety of inputs. --- > + /* 22853,22858c22660 < */ < - int e3 = (left + right) >>> 1; // The midpoint < - int e2 = e3 - seventh; < - int e1 = e2 - seventh; < - int e4 = e3 + seventh; < - int e5 = e4 + seventh; --- > + */ 22860,22862c22662 < < - // Sort these elements using insertion sort < - if (a[e2] < a[e1]) { char t = a[e2]; a[e2] = a[e1]; a[e1] = t; } --- > + 22865,22871c22665 < < - if (a[e3] < a[e2]) { char t = a[e3]; a[e3] = a[e2]; a[e2] = t; < - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } < - } < - if (a[e4] < a[e3]) { char t = a[e4]; a[e4] = a[e3]; a[e3] = t; < - if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t; < - if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; } --- > + 22892c22686 < + if (parallelism > 0 && size > MIN_PARALLEL_SORT_SIZE) { --- > + if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) { 23036c22830 < + * 5 ------o-----------o----------- --- > + * 5 ------o-----------o------------ 23038c22832 < + * 4 ------|-----o-----o-----o----- --- > + * 4 ------|-----o-----o-----o------ 23040c22834 < + * 2 ------o-----|-----o-----o----- --- > + * 2 ------o-----|-----o-----o------ 23042c22836 < + * 1 ------------o-----o----------- --- > + * 1 ------------o-----o------------ 23826,23828c23620 < + int mi = lo, rmi = (run[lo] + run[hi]) >>> 1; < + while (run[++mi + 1] <= rmi); < --- > - 23844c23636,23638 < - --- > + int mi = lo, rmi = (run[lo] + run[hi]) >>> 1; > + while (run[++mi + 1] <= rmi); > 24073,24078c23867,23869 < } < - return; < } < < - // Inexpensive approximation of length / 7 < - int seventh = (length >> 3) + (length >> 6) + 1; --- > + } > + } > + 24093,24094c23884,23886 < + } < + } --- > } > - return; > } 24096c23888,23890 < + --- > > - // Inexpensive approximation of length / 7 > - int seventh = (length >> 3) + (length >> 6) + 1; 24163c23957 < + if (parallelism > 0 && size > MIN_PARALLEL_SORT_SIZE) { --- > + if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) { 24307c24101 < + * 5 ------o-----------o----------- --- > + * 5 ------o-----------o------------ 24309c24103 < + * 4 ------|-----o-----o-----o----- --- > + * 4 ------|-----o-----o-----o------ 24311c24105 < + * 2 ------o-----|-----o-----o----- --- > + * 2 ------o-----|-----o-----o------ 24313c24107 < + * 1 ------------o-----o----------- --- > + * 1 ------------o-----o------------ 24392,24393c24186 < /* < - * Skip elements, which are equal to pivot values. --- > + /* 24399,24401c24192 < */ < - while (a[less] == pivot1) { < - ++less; --- > + */ 24405c24196,24197 < + /* --- > /* > - * Skip elements, which are equal to pivot values. 24407c24199,24201 < + */ --- > */ > - while (a[less] == pivot1) { > - ++less; 24480,24481c24274 < /* < - * Partitioning: --- > + /* 24490c24283,24284 < + /* --- > /* > - * Partitioning: 24678,24692c24472 < } < - if (a[great] < pivot) { // a[great] <= pivot < - a[k] = a[less]; < - a[less] = a[great]; < - ++less; < - } else { // a[great] == pivot < - /* < - * Even though a[great] equals to pivot, the < - * assignment a[k] = pivot may be incorrect, < - * if a[great] and pivot are floating-point < - * zeros of different signs. Therefore in float < - * and double sorting methods we have to use < - * more accurate assignment a[k] = a[great]. < - */ < - a[k] = a[great]; --- > + } 24709,24710c24489,24502 < - a[great] = ak; < - --great; --- > - if (a[great] < pivot) { // a[great] <= pivot > - a[k] = a[less]; > - a[less] = a[great]; > - ++less; > - } else { // a[great] == pivot > - /* > - * Even though a[great] equals to pivot, the > - * assignment a[k] = pivot may be incorrect, > - * if a[great] and pivot are floating-point > - * zeros of different signs. Therefore in float > - * and double sorting methods we have to use > - * more accurate assignment a[k] = a[great]. > - */ > - a[k] = a[great]; 24717c24509,24511 < + } --- > } > - a[great] = ak; > - --great; 24797c24591,24597 < + } --- > } > - for (int k = right; --k >= left; ) { > - double ak = a[k]; > - if (ak != ak) { // a[k] is NaN > - a[k] = a[right]; > - a[right] = ak; > - --right; 24815,24821c24615 < } < - for (int k = right; --k >= left; ) { < - double ak = a[k]; < - if (ak != ak) { // a[k] is NaN < - a[k] = a[right]; < - a[right] = ak; < - --right; --- > + } 25064,25066c24858 < + int mi = lo, rmi = (run[lo] + run[hi]) >>> 1; < + while (run[++mi + 1] <= rmi); < --- > - 25082c24874,24876 < - --- > + int mi = lo, rmi = (run[lo] + run[hi]) >>> 1; > + while (run[++mi + 1] <= rmi); > 25719c25513 < } --- > + } 25722c25516 < + } --- > } 25745,25746c25539,25540 < --- old/test/jdk/java/util/Arrays/Sorting.java 2019-07-17 17:04:37.820314297 +0200 < +++ new/test/jdk/java/util/Arrays/Sorting.java 2019-07-17 17:04:37.512314302 +0200 --- > --- old/test/jdk/java/util/Arrays/Sorting.java 2019-07-26 10:05:34.128098830 +0200 > +++ new/test/jdk/java/util/Arrays/Sorting.java 2019-07-26 10:05:33.988098832 +0200 28244,28245c28038,28039 < --- old/test/jdk/java/util/Arrays/ParallelSorting.java 2019-07-17 17:04:38.412314289 +0200 < +++ /dev/null 2019-07-17 10:17:39.064651967 +0200 --- > --- old/test/jdk/java/util/Arrays/ParallelSorting.java 2019-07-26 10:05:34.872098820 +0200 > +++ /dev/null 2019-07-26 09:07:09.036147299 +0200 30314,30315c30108,30109 < --- /dev/null 2019-07-17 10:17:39.064651967 +0200 < +++ new/test/jdk/java/util/Arrays/java.base/java/util/SortingHelper.java 2019-07-17 17:04:38.524314288 +0200 --- > --- /dev/null 2019-07-26 09:07:09.036147299 +0200 > +++ new/test/jdk/java/util/Arrays/java.base/java/util/SortingHelper.java 2019-07-26 10:05:35.096098817 +0200