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.c...@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'le...@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.c...@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.
>
