Hello Dmytro, Please, see file test/java/util/Arrays/Sorting.java in the JDK repository, It contains unit tests.
Thank you, Vladimir 2010/4/30 Dmytro Sheyko <dmytro_she...@hotmail.com>: > Hello Vladimir, > > Could you remind me where can I find sources for the test suite? > > Thanks, > Dmytro > >> Date: Tue, 27 Apr 2010 01:50:08 +0400 >> Subject: New portion of improvements for Dual-Pivot Quicksort >> From: vladimir.iaroslav...@googlemail.com >> To: core-libs-dev@openjdk.java.net >> >> 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
