Josh,
Quick note on changing
int pivot1 = a[e2[;
int pivot2 = a[e4];
by
int pivot1 = ae2;
int pivot2 = ae4;
It is extremely surprised, but version with local variables eats
5% (!) of time for client and 2% for server mode (in compare
with one-pivot implementation from JDK 6), see:
client server
with a[e2], a[e4]: 60.75% 48.20%
with ae2, ae4: 65.80% 50.42%
I don't have idea why this simple change is so expensive.
Does anybody can explain it?
Vladimir
Tue, 4 May 2010 21:57:42 -0700 письмо от Joshua Bloch <j...@google.com>:
>
> 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
