RFR: 8226297: Dual-pivot quicksort improvements

Brent Christian brent.christian at oracle.com
Mon Aug 12 23:46:48 UTC 2019


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:

For convenience, I made .diffs from the previous version (webrev04) for 
DualPivotQuickSort.java[1] and Arrays.java[2 - change to trailing 
white-space, only].



More information about the core-libs-dev mailing list