We are proposing a patch to improve the performance for the DualPivotQuickSort
use by Array.sort to sort primitives array. We have identified two area for
optimization:
Firstly, we have changed the algorithm to determine what a "run" is. A "run" is
how long you go through the array with it being in order. For example, an array
of 1, 2, 3, 5, 4, 3 would have a run count equal to 2 (two parts that are in
order).
The JDK implementation stops looking for runs if it comes across two equal
numbers at the beginning of a run, eg.
1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 5
And then sorts the whole array, as seen in this part of the algorithm:
} else { // equal
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}
Instead, we detect and equal beginning of a run at the top of the for loop, as
shown here:
while (k < right && a[k] == a[++k]); //equal
so the array mentioned above would instead have one run, be determined already
sorted, and sort would not be called as it would in the original JDK
implementation.
Second optimization is in the case of an array that is descending, and then
ascending.
Since the algorithm does swapping in the case of descending numbers, by the end
of all swapping the array is sorted. We detect this through this if statement:
if (run[count] > left && a[run[count]] >= a[run[count] - 1]) {
count--;
}
And will stop sorting, unlike the JDK.
I have attached a webrev.zip containing the patch and unit test that verifies
the sort is correct. We also have a couple of JMH based performance tests which
is not included. If the JMH is available we can also make those performance
test available as well.
The patch is author by Kristen O'Leary (Kristen.o'[email protected]) and myself.
Please attribute both of us when committing. You can find my OCA entry under
Goldman Sachs and as we are not authors yet we can't raise a bug report in the
database.
Please let us know if you need further clarification or modification to the
patch.
Sunny Chan, Executive Director, Technology
Goldman Sachs (Asia) L.L.C. | 68th Floor | Cheung Kong Center | 2 Queens Road
Central | Hong Kong
email: [email protected] | Tel: +852 2978 6481 | Fax: +852 2978 0633
This message may contain information that is confidential or privileged. If
you are not the intended recipient, please advise the sender immediately and
delete this message. See http://www.gs.com/disclaimer/email for further
information on confidentiality and the risks inherent in electronic
communication.
