Hello, everyone! I've investigated the implementation of the Dual-Pivot Quicksort which is used for sorting primitives and here is my result:
http://cr.openjdk.java.net/~alanb/6947216/webrev.00 New implementation of Dual-Pivot Quicksort is faster than previous one of 12% for client VM and few percents for server VM. Tests on Bentley's test suite (Win XP, JDK 7, build 1.7.0-ea-b84, n = 1000000) show geometry mean 0.88 for client VM and 0.98-1.00 for server VM. In compare with sorting from JDK 6 by Jon L. Bentley and M. Douglas McIlroy's (with one pivot) the ratio is 0.61 / 0.50 (client / server). See the execution time for sorting array of 2`000`000 int elements 50 times, client / server VM, in milliseconds: random new: 16723 18776 jdk7: 17571 18975 jdk6: 22241 26524 ascendant new: 3541 4702 jdk7: 4486 4669 jdk6: 8667 7978 descendant new: 3854 4907 jdk7: 4942 5034 jdk6: 8787 8243 equal new: 234 281 jdk7: 291 230 jdk6: 602 1018 organ pipes new: 7673 8613 jdk7: 8167 8993 jdk6: 11902 14044 stagger 1 new: 7648 8591 jdk7: 8161 8979 jdk6: 11908 13810 stagger 2 new: 8349 9299 jdk7: 10968 11916 jdk6: 12194 14734 stagger 4 new: 8475 9622 jdk7: 9221 9682 jdk6: 10523 12006 stagger 8 new: 9321 10689 jdk7: 11125 12387 jdk6: 13829 16214 period 1..2 new: 758 751 jdk7: 870 754 jdk6: 1038 1227 period 1..4 new: 1004 963 jdk7: 1365 1209 jdk6: 1511 1847 period 1..8 new: 1588 1573 jdk7: 1599 1790 jdk6: 2602 3045 random 1..2 new: 1327 1125 jdk7: 1362 1496 jdk6: 1531 2182 random 1..4 new: 1830 2118 jdk7: 1851 2236 jdk6: 2292 3025 where stagger(m) is array like a[i] = i * (m + 1) % length. The summary of changes is: 1. For sorting small arrays is used insertion sort with sentinel instead of traditional, which has the structure: for (int i = left + 1; i <= right; i++) { for (j = i; j > left && a[j-1] > a[j]; j--) { swap(a[i], a[j-1]); } } Note that range check j > left is performed on each iteration, but really helps very rare. To avoid this expensive range check, it was suggested to set minimum value (negative infinity) on the first position. This type of suggestion is used in new version: if left bound > 0, we can put sentinel on a[left - 1], do insertion sort without expensive check range, and then restore a[left - 1] value. If left == 0, traditional insertion sort is used. Please, look at the webrev for details. 2. In previous implementation 5 evenly spaced elements sixth = length / 6; a[sixth], a[2 * sixth], a[3 * sixth], a[4 * sixth], a[5 * sixth] were used as candidates of pivots elements. This case is very sensitive for period inputs, especially by 6. The new suggestion is to take 5 center evenly spaced elements like this: int seventh = length / 7; int midpoint = (left + right) >>> 1; a[midpoint - 2 * seventh], a[midpoint - seventh], a[midpoint], a[midpoint + seventh], a[midpoint + 2 * seventh] and moreover, the seventh is calculated inexpensively: seventh = (length >>> 3) + (length >>> 6) + 1; This schema works the same on random, ascendant, descendant, equal inputs, but much better for period / stagger. 3. The whole structure <choose pivots> if (pivotsDiffer) { <do partitioning for two pivots> } else { <do partitioning for one pivot> } <sort left and right parts> if (!pivotsDiffer) { return; } <swap internal pivot values to ends> <sort center part> was modified to: ---------------- <choose pivots> if (pivot1 < pivot2) { <do partitioning for two pivots> <swap pivots into their final positions> <sort left and right parts> <swap internal pivot values to ends> <sort center part> } else { <do partitioning for one pivot> <sort left and right parts> } 4. Partitioning for both cases have not been changed at all. 5. Minor javadoc and format changes. Please, review new implementation, any comments / suggestions are welcome! Thank you, Vladimir
