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

[Vladimir Iaroslavski]

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 MAX_RUN_COUNT, MAX_RUN_LENGTH 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
> >  ...