Vladimir,<div><br></div><div>Fascinating. šI don't know why this should be so.</div><div><br></div><div>šš šJoch<br><br><div class="gmail_quote">On Wed, May 5, 2010 at 3:03 PM, Vladimir Iaroslavski <span dir="ltr"><<a href="mailto:iaroslavski@mail.ru">iaroslavski@mail.ru</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Josh,<br>
<br>
Quick note on changing<br>
<br>
int pivot1 = a[e2[;<br>
int pivot2 = a[e4];<br>
<br>
by<br>
<br>
int pivot1 = ae2;<br>
int pivot2 = ae4;<br>
<br>
It is extremely surprised, but version with local variables eats<br>
5% (!) of time for client and 2% for server mode (in compare<br>
with one-pivot implementation from JDK 6), see:<br>
<br>
 š š š š š š š š š š client š server<br>
with a[e2], a[e4]: š 60.75% š 48.20%<br>
 š šwith ae2, ae4: š 65.80% š 50.42%<br>
<br>
I don't have idea why this simple change is so expensive.<br>
Does anybody can explain it?<br>
<br>
Vladimir<br>
<br>
Tue, 4 May 2010 21:57:42 -0700 ΠΙΣΨΝΟ ΟΤ Joshua Bloch <<a href="mailto:jjb@google.com">jjb@google.com</a>>:<br>
<div><div></div><div class="h5">><br>
> Vladimir,<br>
><br>
> 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:<br>
><br>
> I think the comment on lines 102-105 was too useful to delete:<br>
><br>
> 102 š š... This<br>
> 103 š * method differs from the public {@code sort} method in that the<br>
> 104 š * {@code right} index is inclusive, and it does no range checking<br>
> 105 š * on {@code left} or {@code right}.<br>
><br>
> 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.<br>

><br>
> 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 "+":<br>

><br>
> 118 š š // Use insertion sort on tiny arrays<br>
> 119 š š if (length < INSERTION_SORT_THRESHOLD) {<br>
> 120 š š š if (left > 0) {<br>
> 121 š š š š /*<br>
> *122 š š š š * Temporarily set the value immediately preceding the range<br>
> *123 š š š š * to the minimum int value to serve as a sentinel. This<br>
> *124 š š š š * allows us to avoid the j >= left check on each iteration.<br>
> 125 š š š š */<br>
> 126 š š š š int before = a[left - 1]; a[left - 1] = Integer.MIN_VALUE;<br>
> 127<br>
> 128 š š š š for (int j, i = left + 1; i <= right; i++) {<br>
> 129 š š š š š int ai = a[i];<br>
> *130 š š š š š for (j = i - 1; ai < a[j]; j--) {<br>
> +NEW š š š š š š // assert j >= left;<br>
> 131 š š š š š š a[j + 1] = a[j];<br>
> 132 š š š š š }<br>
> 133 š š š š š a[j + 1] = ai;<br>
> 134 š š š š }<br>
> 135 š š š š a[left - 1] = before;<br>
> 136 š š š } else {<br>
><br>
> The comment in line 155 is misleading, and should be replace by this:<br>
><br>
> I'd reword the comment in lines 137-140 for clarity:<br>
><br>
> 137 š š š š /*<br>
> 138 š š š š * For case, when left == 0, traditional (without a sentinel)<br>
> 139 š š š š * insertion sort, optimized for server VM, is used.<br>
> 140 š š š š */<br>
><br>
> 155 š š // Inexpensive approximation of length / 7<br>
><br>
> The comment strategy for choosing sample points is subtle enough that it deserves bit more commentary. I propose replacing line 158 with this:<br>
><br>
> š /*<br>
> š * Sort five evenly spaced elements around (and including) the center<br>
> š * element in the range. These elements will be used for pivot selection<br>
> š * as described below. The choice for spacing these elements was empirically<br>
> š * determined to work well on a wide variety of inputs.<br>
> š */<br>
><br>
> Lines 183 and 184 are unnecessary array accesses. Probably better is:<br>
><br>
> 183 š š int pivot1 = ae2;<br>
> 184 š š int pivot2 = ae4;<br>
><br>
> This is essentially just a renaming of these two local variables, and presumably the compiler will act accordingly.<br>
><br>
> I prefer the original wording:<br>
><br>
> 197 š š š * Pointer k is the first index of -part<br>
><br>
> to the revised wording:<br>
><br>
> 217 š š š * Pointer k is the first index of not inspected -part.<br>
><br>
> I'd revert this change.<br>
><br>
> I'd change 190 from:<br>
><br>
> 190 š š if (pivot1 < pivot2) {<br>
> to<br>
> 190 š š if (pivot1 != pivot2) {<br>
><br>
> It's clearer (this is the "pivots differ" case), and at least as fast.<br>
><br>
> The spacing lines 249 and 250 is a bit quirky:<br>
><br>
> 249 š š š dualPivotQuicksort(a, left, šless - 2);<br>
> 250 š š š dualPivotQuicksort(a, great + 2, right);<br>
><br>
> I'd replace it with the more standard:<br>
><br>
> 249 š š š dualPivotQuicksort(a, left, less - 2);<br>
> 250 š š š dualPivotQuicksort(a, great + 2, right);<br>
><br>
> Alternatively, you could make corresponding arguments line up:<br>
><br>
> 249 š š š dualPivotQuicksort(a, left, š less - 2);<br>
> 250 š š š dualPivotQuicksort(a, great + 2, right š);<br>
><br>
> The policy change in line 256 is non-trivial:<br>
><br>
> Old:<br>
><br>
> 298 š š if (less < e1 && great > e5) {<br>
><br>
> New:<br>
><br>
> 256 š š š if (great - less > 5 * seventh) {<br>
><br>
> 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.<br>

><br>
> In lines 362 and 363, you have the same "quirky spacing" as in linkes 249 and 250:<br>
><br>
> 361 š š š // Sort left and right parts recursively<br>
> 362 š š š dualPivotQuicksort(a, left, šless - 1);<br>
> 363 š š š dualPivotQuicksort(a, great + 1, right);<br>
><br>
> šRegards,<br>
> šJosh<br>
</div></div></blockquote></div><br></div>