RFR: 8226297: Dual-pivot quicksort improvements
Brent Christian
brent.christian at oracle.com
Mon Aug 12 23:46:48 UTC 2019
Hi,
I received an update from Vladimir:
-----------------------------------
"I investigated approach with adaptive threshold for mixed insertion sort
and have the following results.
New version shows the same gain for large arrays
and has few percents of speed up for small arrays:
total gain:
size = 150, char, was: 0.10 -> new: 0.17
size = 150, int, was: 0.15 -> new: 0.18
size = 150, short, was: 0.14 -> new: 0.16
See new version in attachment. The changes are simple and safety:
initial threshold for insertion sort was increased from 41 to 44,
initial threshold for mixed insertion sort was decreased from 114 to 65,
but the size is compared with adaptive threshold
if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && ....
(was: if (size < MAX_MIXED_INSERTION_SORT_SIZE && ....)
Variable bits is increased by 6 instead of 2."
-----------------------------------
I've incorporated this change in an updated webrev, here:
http://cr.openjdk.java.net/~bchristi/8226297/webrev05-adaptive/webrev/
For convenience, I made .diffs from the previous version (webrev04) for
DualPivotQuickSort.java[1] and Arrays.java[2 - change to trailing
white-space, only].
-Brent
1.
http://cr.openjdk.java.net/~bchristi/8226297/webrev05-adaptive/DualPivotQuicksort.java.diff
2.
http://cr.openjdk.java.net/~bchristi/8226297/webrev05-adaptive/Arrays.java.diff
More information about the core-libs-dev
mailing list