<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
Hello Vladimir,<br><br>Could you remind me where can I find sources for the test suite?<br><br>Thanks,<br>Dmytro<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: Trusted email with Microsoft’s powerful SPAM protection. <a href='https://signup.live.com/signup.aspx?id=60969' target='_new'>Sign up now.</a></body>
</html>