<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
Vladimir,<br><br>> If we consider case when the whole array is sorted,<br>> we can omit setting sentinel and restoring original value:<br><br>Let me define my point more precisely. We can omit setting sentinel not only in a particular case when the whole array is sorted.<br><br>During partitioning the whole array is split into small chunks. Elements within a chunks remains unsorted,<br>but every element in a certain chunk is greater than every element in preceding (lefter) chunks<br>and less than every element in following (righter) chunks.<br><br>E.g.<br><br>   [...A...B...]C[...D...E...]F[...G...H...]<br><br>Elements C and F are pivots.<br>Elements D and E are greater that pivot C and hence greater than A and B, and less than pivot F and hence G and H.<br><br>Therefore during sorting any non-leftmost chunk we can rely on preceding chunk.<br><br>Did I miss something? Is this what you mean?<br><br>Thank you,<br>Dmytro Sheyko<br><br>> Date: Wed, 5 May 2010 21:23:37 +0400<br>> From: iaroslavski@mail.ru<br>> Subject: Re: New portion of improvements for Dual-Pivot Quicksort<br>> To: dmytro_sheyko@hotmail.com<br>> CC: core-libs-dev@openjdk.java.net<br>> <br>> Hi Dmytro,<br>> <br>> Thank you very much for suggestions! I checked it and here<br>> is my results:<br>> <br>> If we consider case when the whole array is sorted,<br>> we can omit setting sentinel and restoring original value:<br>> <br>> //  int before = a[left - 1]; a[left - 1] = Integer.MIN_VALUE;<br>> <br>>      for (int j, i = left + 1; i <= right; i++) {<br>>          int ai = a[i];<br>>          for (j = i - 1; /* j >= left && */ ai < a[j]; j--) {<br>>              a[j + 1] = a[j];<br>>          }<br>>          a[j + 1] = ai;<br>>      }<br>> //  a[left - 1] = before;<br>> <br>> I checked this version and found that it works little bit faster<br>> (only 0.4-0.3%) with client VM, but loses more than 2.5% under<br>> server mode in compare with one-pivot version from JDK 6:<br>> <br>>                       client   server<br>>             original: 60.75%   48.20%<br>> no setting sentinel: 60.40%   50.88%<br>> <br>> If we add additional check which case is sorted, I think, we<br>> don't win at all.<br>> <br>> And if pivot candidates are not put back to array, it shows<br>> very poor results:<br>> <br>>                      client   server<br>>            original: 60.75%   48.20%<br>> no back candidates: 66.80%   53.95%<br>> <br>> I run one pivot version taken from JDK 6: I replace in Dual-Pivot<br>> implementation with all optimizations dual-pivot partitioning by one-pivot:<br>> but it remain still slower than DPQ. So, the main point of DPQ is not only<br>> in optimizations, but in dividing array into 3 parts instead of two.<br>> <br>> Thank you,<br>> Vladimir<br>> <br>> Dmytro Sheyko wrote:<br>> > Hi Vladimir,<br>> > <br>> > The trick with sentinel is quite cute. Going farther, I think it is not <br>> > always necessary to replace left outer element with the least possible value<br>> > (and restore it later after sorting) because after partitioning every <br>> > element in adjoining array part can play the role of sentinel.<br>> > The only exception is when the user requested to sort array partially <br>> > (not from the beginning). Thereby we should care about setting sentinel <br>> > explicitly in this exceptional case only and only once before sorting whole array.<br>> > <br>> > Also it seems to me that it is not necessary to put pivot candidates (5 <br>> > elements that are used to choose pivots) back to array<br>> > because anyway they are to be sorted later and likely change their <br>> > positions.<br>> > <br>> > I am also interesting in theoretical rationale why dual pivot quicksort <br>> > is better than single pivot one. The last document that I have seen <br>> > (Last updated: September 22, 2009)<br>> > compared classic quicksort (where pivot is chosen arbitrarily) with <br>> > "classic" dual pivot quicksort (where pivots are also chosen arbitrarily).<br>> > As conclusion they both perform about 2*n*ln(n) key comparisons. However <br>> > jdk had improved quicksort: median-of-three and pseudomedian-of-nine<br>> > approaches were used. And median-of-three approach lead to 12/7*n*ln(n) <br>> > key comparisons. On the other hand, dual pivot quicksort is also improved:<br>> > pivots are chosen from 5 candidates, and hence it must perform less than <br>> > 2*n*ln(n) key comparisons.<br>> > <br>> > Regards,<br>> > Dmytro Sheyko<br>> > <br>> >  > Date: Tue, 27 Apr 2010 01:50:08 +0400<br>> >  > Subject: New portion of improvements for Dual-Pivot Quicksort<br>> >  > From: vladimir.iaroslavski@googlemail.com<br>> >  > To: core-libs-dev@openjdk.java.net<br>> >  ><br>> >  > Hello, everyone!<br>> >  ><br>> >  > I've investigated the implementation of the Dual-Pivot Quicksort<br>> >  > which is used for sorting primitives and here is my result:<br>> >  ><br>> >  > http://cr.openjdk.java.net/~alanb/6947216/webrev.00<br>> >  ><br>> >  > New implementation of Dual-Pivot Quicksort is faster<br>> >  > than previous one of 12% for client VM and few percents for<br>> >  > server VM. Tests on Bentley's test suite (Win XP, JDK 7,<br>> >  > build 1.7.0-ea-b84, n = 1000000) show geometry mean 0.88<br>> >  > for client VM and 0.98-1.00 for server VM.<br>> >  ><br>> >  > In compare with sorting from JDK 6 by Jon L. Bentley and<br>> >  > M. Douglas McIlroy's (with one pivot) the ratio is 0.61 / 0.50<br>> >  > (client / server).<br>> >  ><br>> >  > See the execution time for sorting array of 2`000`000 int elements<br>> >  > 50 times, client / server VM, in milliseconds:<br>> >  ><br>> >  > random<br>> >  > new: 16723 18776<br>> >  > jdk7: 17571 18975<br>> >  > jdk6: 22241 26524<br>> >  ><br>> >  > ascendant<br>> >  > new: 3541 4702<br>> >  > jdk7: 4486 4669<br>> >  > jdk6: 8667 7978<br>> >  ><br>> >  > descendant<br>> >  > new: 3854 4907<br>> >  > jdk7: 4942 5034<br>> >  > jdk6: 8787 8243<br>> >  ><br>> >  > equal<br>> >  > new: 234 281<br>> >  > jdk7: 291 230<br>> >  > jdk6: 602 1018<br>> >  ><br>> >  > organ pipes<br>> >  > new: 7673 8613<br>> >  > jdk7: 8167 8993<br>> >  > jdk6: 11902 14044<br>> >  ><br>> >  > stagger 1<br>> >  > new: 7648 8591<br>> >  > jdk7: 8161 8979<br>> >  > jdk6: 11908 13810<br>> >  ><br>> >  > stagger 2<br>> >  > new: 8349 9299<br>> >  > jdk7: 10968 11916<br>> >  > jdk6: 12194 14734<br>> >  ><br>> >  > stagger 4<br>> >  > new: 8475 9622<br>> >  > jdk7: 9221 9682<br>> >  > jdk6: 10523 12006<br>> >  ><br>> >  > stagger 8<br>> >  > new: 9321 10689<br>> >  > jdk7: 11125 12387<br>> >  > jdk6: 13829 16214<br>> >  ><br>> >  > period 1..2<br>> >  > new: 758 751<br>> >  > jdk7: 870 754<br>> >  > jdk6: 1038 1227<br>> >  ><br>> >  > period 1..4<br>> >  > new: 1004 963<br>> >  > jdk7: 1365 1209<br>> >  > jdk6: 1511 1847<br>> >  ><br>> >  > period 1..8<br>> >  > new: 1588 1573<br>> >  > jdk7: 1599 1790<br>> >  > jdk6: 2602 3045<br>> >  ><br>> >  > random 1..2<br>> >  > new: 1327 1125<br>> >  > jdk7: 1362 1496<br>> >  > jdk6: 1531 2182<br>> >  ><br>> >  > random 1..4<br>> >  > new: 1830 2118<br>> >  > jdk7: 1851 2236<br>> >  > jdk6: 2292 3025<br>> >  ><br>> >  > where stagger(m) is array like a[i] = i * (m + 1) % length.<br>> >  ><br>> >  > The summary of changes is:<br>> >  ><br>> >  > 1. For sorting small arrays is used insertion sort with sentinel<br>> >  > instead of traditional, which has the structure:<br>> >  ><br>> >  > for (int i = left + 1; i <= right; i++) {<br>> >  > for (j = i; j > left && a[j-1] > a[j]; j--) {<br>> >  > swap(a[i], a[j-1]);<br>> >  > }<br>> >  > }<br>> >  ><br>> >  > Note that range check j > left is performed on each iteration,<br>> >  > but really helps very rare. To avoid this expensive range check,<br>> >  > it was suggested to set minimum value (negative infinity) on the<br>> >  > first position. This type of suggestion is used in new version:<br>> >  ><br>> >  > if left bound > 0, we can put sentinel on a[left - 1], do insertion<br>> >  > sort without expensive check range, and then restore a[left - 1]<br>> >  > value. If left == 0, traditional insertion sort is used. Please,<br>> >  > look at the webrev for details.<br>> >  ><br>> >  > 2. In previous implementation 5 evenly spaced elements<br>> >  ><br>> >  > sixth = length / 6;<br>> >  > a[sixth], a[2 * sixth], a[3 * sixth], a[4 * sixth], a[5 * sixth]<br>> >  ><br>> >  > were used as candidates of pivots elements. This case is very<br>> >  > sensitive for period inputs, especially by 6. The new suggestion<br>> >  > is to take 5 center evenly spaced elements like this:<br>> >  ><br>> >  > int seventh = length / 7;<br>> >  > int midpoint = (left + right) >>> 1;<br>> >  ><br>> >  > a[midpoint - 2 * seventh], a[midpoint - seventh], a[midpoint],<br>> >  > a[midpoint + seventh], a[midpoint + 2 * seventh]<br>> >  ><br>> >  > and moreover, the seventh is calculated inexpensively:<br>> >  > seventh = (length >>> 3) + (length >>> 6) + 1;<br>> >  ><br>> >  > This schema works the same on random, ascendant, descendant, equal<br>> >  > inputs, but much better for period / stagger.<br>> >  ><br>> >  > 3. The whole structure<br>> >  ><br>> >  > <choose pivots><br>> >  ><br>> >  > if (pivotsDiffer) {<br>> >  > <do partitioning for two pivots><br>> >  > }<br>> >  > else {<br>> >  > <do partitioning for one pivot><br>> >  > }<br>> >  ><br>> >  > <sort left and right parts><br>> >  ><br>> >  > if (!pivotsDiffer) {<br>> >  > return;<br>> >  > }<br>> >  > <swap internal pivot values to ends><br>> >  ><br>> >  > <sort center part><br>> >  ><br>> >  > was modified to:<br>> >  > ----------------<br>> >  ><br>> >  > <choose pivots><br>> >  ><br>> >  > if (pivot1 < pivot2) {<br>> >  > <do partitioning for two pivots><br>> >  > <swap pivots into their final positions><br>> >  > <sort left and right parts><br>> >  > <swap internal pivot values to ends><br>> >  > <sort center part><br>> >  > }<br>> >  > else {<br>> >  > <do partitioning for one pivot><br>> >  > <sort left and right parts><br>> >  > }<br>> >  ><br>> >  > 4. Partitioning for both cases have not been changed at all.<br>> >  ><br>> >  > 5. Minor javadoc and format changes.<br>> >  ><br>> >  > Please, review new implementation,<br>> >  > any comments / suggestions are welcome!<br>> >  ><br>> >  > Thank you,<br>> >  > Vladimir<br>                                    <br /><hr />Hotmail: Powerful Free email with security by Microsoft. <a href='https://signup.live.com/signup.aspx?id=60969' target='_new'>Get it now.</a></body>
</html>