Re[2]: Dual-Pivot Quicksort improvements for highly structured (nearly sorted) arrays and data with small periods (original) (raw)

Vladimir Iaroslavski iaroslavski at mail.ru
Fri Feb 4 21:58:25 UTC 2011

Hi Mike,

Thank you for review!

The value of the @version tag is date plus numbers which are not from any version control system. It is just abbreviation for changes and versions from my file tree. For example, "5\7" means improvement of pivot candidates, "p" - pair insertion sort, "m" - using of merge sort. Sometimes I receive feedback or find review of Dual-Pivot Quicksort source in the internet and the version value helps me a lot to recognize which version is used. The @value tag is not shown in javadoc (as well as whole DPQ class), therefore I'd like to keep it.

All tuning parameters were empirically determined. The best way to find optimal value is to run series of tests and compare sorting with different values. This series was done by me recently and INSERTION_SORT_THRESHOLD was increased. I think it makes sense to run check in each release.

No templates: I take int method and adjust it for other types, but double/float methods are little bit different from int/long/short/char/byte, see comment in new version, lines 440-448 and 507-514. Note that Quicksort is not used in byte method at all, counting and insertion sort are used only. Methods for short/char use counting sort also. When I prepare final version of the class, I double check all methods.

Thank you, Vladimir

Fri, 4 Feb 2011 10:48:10 -0800 письмо от Mike Duigou <mike.duigou at oracle.com>:

This looks like really good work. I have a few comments and questions about this webrev. None of these comments block commit.

- The @version tag contains what appears to be a value from a version control system. I thought all of these had been or were being eliminated. - I am curious how the MAXRUNCOUNT, MAXRUNLENGTH and THRESHOLD values are derived. We should provide some back link to how these values were chosen at so that future maintainers can decided when it is appropriate (or not) to change the values. - Are the seven implementations generated from a template or are they hand-coded? I didn't check that there are no unexplained differences between the implementation but am curious if it would be possible that differences could arise or exist. Mike On Jan 20 2011, at 10:09 , Vladimir Iaroslavski wrote: > Here is improvement for sorting primitives: > http://cr.openjdk.java.net/~alanb/7013585/webrev > ...

More information about the core-libs-dev mailing list