# Patch to improve primitives Array.sort()

Paul Sandoz paul.sandoz at oracle.com
Fri Apr 24 07:30:45 UTC 2015

```HI Chan,

Attachments might be getting removed by the OpenJDK email server.

If you send me the webrev privately i can upload to cr. If so could you do that please send the JMH tests as i think people might also be interested in those.

Paul.

On Apr 24, 2015, at 9:17 AM, "Chan, Sunny" <Sunny.Chan at gs.com> wrote:

> 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'leary at gs.com) 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:  sunny.chan at gs.com | 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.
>

```