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. >