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
>
