Vladimir, Fascinating. I don't know why this should be so.
Joch On Wed, May 5, 2010 at 3:03 PM, Vladimir Iaroslavski <iaroslav...@mail.ru>wrote: > 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 >