New portion of improvements for Dual-Pivot Quicksort

[Vladimir Iaroslavski]

Josh,

Thank you very much for review.
I'll prepare updated version and send it with my comments soon.

Vladimir

Joshua Bloch wrote:
> Vladimir,
> 
> Hi. I'm thrilled that you were able to eke so much more perforance out 
> of this already optimized code. I read your changes on my flight to 
> Pittsburgh. Here's the code review:
> 
> I think the comment on lines 102-105 was too useful to delete:
> 
>  102        ...  This
>  103      * method differs from the public {@code sort} method in that the
>  104      * {@code right} index is inclusive, and it does no range checking
>  105      * on {@code left} or {@code right}.
> 
> The sentinel technique that you use in lines 118 - 136 is questionable: 
> you are modifying a portion of the array outside the specified range of 
> the call, which arguably violates the contract of the call, and could be 
> observed in a multithreaded program. It's not beyond the realm of reason 
> that it could break existing clients. I will discuss it with Doug Lea 
> and let you know what he says.
> 
> If we leave this optimization in, we should change the comments 
> slightly. Appearing to comment-out code (other than entire assertions in 
> inner loops) is never a good thing, hence the change to line 130 and the 
> addition of the line that follows. Also I reworded the commennt in lines 
> 122-125 for clarity. Changed lines are starred, added line has a "+":
> 
>  118         // Use insertion sort on tiny arrays
>  119         if (length < INSERTION_SORT_THRESHOLD) {
>  120             if (left > 0) {
>  121                 /*
> *122                  * Temporarily set the value immediately preceding 
> the range
> *123                  * to the minimum int value to serve as a sentinel. 
> This
> *124                  * allows us to avoid the j >= left check on each 
> iteration.
>  125                  */
>  126                 int before = a[left - 1]; a[left - 1] = 
> Integer.MIN_VALUE;
>  127 
>  128                 for (int j, i = left + 1; i <= right; i++) {
>  129                     int ai = a[i];
> *130                     for (j = i - 1; ai < a[j]; j--) {
> +NEW                         // assert j >= left;
>  131                         a[j + 1] = a[j];
>  132                     }
>  133                     a[j + 1] = ai;
>  134                 }
>  135                 a[left - 1] = before;
>  136             } else {
> 
> The comment in line 155 is misleading, and should be replace by this:
> 
> I'd reword the comment in lines 137-140 for clarity:
> 
>  137                 /*
>  138                  * For case, when left == 0, traditional (without a 
> sentinel)
>  139                  * insertion sort, optimized for server VM, is used.
>  140                  */
> 
> 
> 155         // Inexpensive approximation of length / 7
> 
> The comment strategy for choosing sample points is subtle enough that it 
> deserves bit more commentary. I propose replacing line 158 with this:
> 
>     /*
>      * Sort five evenly spaced elements around (and including) the center
>      * element in the range. These elements will be used for pivot selection
>      * as described below. The choice for spacing these elements was 
> empirically
>      * determined to work well on a wide variety of inputs.
>      */
> 
> Lines 183 and 184 are unnecessary array accesses. Probably better is:
> 
>  183         int pivot1 = ae2;
>  184         int pivot2 = ae4;
> 
> This is essentially just a renaming of these two local variables, and 
> presumably the compiler will act accordingly.
> 
> I prefer the original wording:
> 
>  197              * Pointer k is the first index of ?-part
> 
> to the revised wording:
> 
>  217              * Pointer k is the first index of not inspected ?-part.
> 
> I'd revert this change.
> 
> I'd change 190 from:
> 
>  190         if (pivot1 < pivot2) {
> 
> to
> 
>  190         if (pivot1 != pivot2) {
> 
> It's clearer (this is the "pivots differ" case), and at least as fast.
> 
> The spacing lines 249 and 250 is a bit quirky:
> 
>  249             dualPivotQuicksort(a, left,   less - 2);
>  250             dualPivotQuicksort(a, great + 2, right);
> 
> I'd replace it with the more standard:
> 
>  249             dualPivotQuicksort(a, left, less - 2);
>  250             dualPivotQuicksort(a, great + 2, right);
> 
> Alternatively, you could make corresponding arguments line up:
> 
>  249             dualPivotQuicksort(a, left,      less - 2);
>  250             dualPivotQuicksort(a, great + 2, right   );
> 
> The policy change in line 256 is non-trivial:
> 
> Old: 
> 
>  298         if (less < e1 && great > e5) {
> 
> New:
> 
>  256             if (great - less > 5 * seventh) {
> 
> I previously experimented with the "new-style" policy (length-based, 
> rather than endpoint-based), but didn't get good results. Perhaps the 
> symmetric style combines well with the change in interval size (5/7 vs. 
> 2/3). At any rate, it's simpler than the old-style and conforms to the 
> comment, so if you're satisfied with the performance, I'm happy with it.
> 
> In lines 362 and 363, you have the same "quirky spacing" as in linkes 
> 249 and 250:
> 
>  361             // Sort left and right parts recursively
>  362             dualPivotQuicksort(a, left,   less - 1);
>  363             dualPivotQuicksort(a, great + 1, right);
> 
>     Regards,
> 
>     Josh