March 2013 - core-libs-dev

Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort
by Vladimir Yaroslavskiy 27 Feb '16

27 Feb '16

Hello All, I'd like to share with you new Dual-Pivot Quicksort which is faster than the known implementations (theoretically and experimental). I'd like to propose to replace the JDK's Quicksort implementation by new one. Description ----------- The classical Quicksort algorithm uses the following scheme: 1. Pick an element P, called a pivot, from the array. 2. Reorder the array so that all elements, which are less than the pivot, come before the pivot and all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot element is in its final position. 3. Recursively sort the sub-array of lesser elements and the sub-array of greater elements. The invariant of classical Quicksort is: [ <= p | >= p ] There are several modifications of the schema: [ < p | = p | > p ] or [ = p | < p | > p | = p ] But all of them use *one* pivot. The new Dual-Pivot Quicksort uses *two* pivots elements in this manner: 1. Pick an elements P1, P2, called pivots from the array. 2. Assume that P1 <= P2, otherwise swap it. 3. Reorder the array into three parts: those less than the smaller pivot, those larger than the larger pivot, and in between are those elements between (or equal to) the two pivots. 4. Recursively sort the sub-arrays. The invariant of the Dual-Pivot Quicksort is: [ < P1 | P1 <= & <= P2 } > P2 ] The new Quicksort is faster than current implementation of Quicksort in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort. The full description of the Dual-Pivot Quicksort you can find on my page: http://iaroslavski.narod.ru/quicksort Performance tests ----------------- Here is result of running on different types of input data: Client VM all 85% organ 0..1 0..4 random ascend descend equal equal pipes random 010101 random Dual-Pivot: 16.83 5.31 5.47 0.35 0.68 10.59 1.06 1.02 2.18 Bentley's: 19.77 9.08 10.13 0.63 1.12 13.22 1.63 1.08 2.49 Server VM all 85% organ 0..1 0..4 random ascend descend equal equal pipes random 010101 random Dual-Pivot: 23.94 6.68 6.63 0.43 0.62 17.14 1.42 1.96 3.41 Bentley's: 25.20 10.18 10.32 2.07 1.33 16.72 2.95 1.82 3.39 The a lot of other tests have been run under client and server mode. The most interesting is BentleyBasher test framework. It runs battery of tests for all cases: { 100, 1000, 10000, 1000000 } x { sawtooth, rand, stagger, plateau, shuffle } x { ident, reverse, reverse_front, reverse_back, sort, dither} where 100, ... , 1000000 - array length sawtooth: x[i] =i%m rand: x[i] = rand() % m stagger: x[i] = (i*m + i) % n plateau: x[i] = min(i, m) shuffle: x[i] = rand()%m? (j+=2): (k+=2) ident(x) - a copy of x reverse(x, 0, n) - reversed copy reverse_front(x, 0, n/2) - front half reversed reverse_back(x, n/2, n) - back half reversed sort(x) - an ordered copy dither(x) - add i%5 to x[i] Here is the result of execution: Server VM: http://spreadsheets.google.com/pub?key=t_EAWUkQ4mD3BIbOv8Fa-AQ&output=html Client VM: http://spreadsheets.google.com/pub?key=tdiMo8xleTxd23nKUObcz0Q&single=true&… Mathematical investigations --------------------------- It is proved that for the Dual-Pivot Quicksort the average number of comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n), whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n) respectively. Full mathematical proof see in attached proof.txt and proof_add.txt files. Theoretical results are also confirmed by experimental counting of the operations. Diff between current and new implementation of Quicksort -------------------------------------------------------- Here is the link to the diff for java.util.Arrays class: http://cr.openjdk.java.net/~alanb/6880672/webrev.00 If you like to look and play with new algorithm, please, take attached class DualPivotQuicksort.java Feedback -------- Also I'd like to share a feedback from Joshua Bloch and Jon Bentley who spent a lot of time investigating this algorithm, who gave me many advices and tips how to make new Quicksort better. -------- Original Message -------- Subject: Re: Integration of new Dual-Pivot Quicksort into JDK 7 Date: Thu, 10 Sep 2009 07:20:11 -0700 From: Joshua Bloch <jjb(a)google.com> Jon also says that Vladimir should make every reasonable improvement to the basic method before checking in the code. In his words, "It would be horrible to put the new code into the library, and then have someone else come along and speed it up by another 20% by using standard techniques." I believe it's not unlikely that this code may end up getting ported to many languages and widely deployed in much the manner of Bentley and McIlroy's fine sort (which is nearing 20 successful years in the field). Jon will help Vladimir do this. -------- Original Message -------- Subject: Dual-Pivot Quicksort: Next Steps Date: Wed, 09 Sep 2009 15:02:25 -0400 From: Jon Bentley <jbentley(a)avaya.com> Vladimir, Josh, I *finally* feel like I understand what is going on. Now that I (think that) I see it, it seems straightforward and obvious. Tony Hoare developed Quicksort in the early 1960s. I was very proud to make minor contributions to a particularly clean (binary) quicksort in the mid 1980s, to a relatively straightforward, industrial strength Quicksort with McIlroy in the early 1990s, and then to algorithms and data structures for strings with Sedgewick in the mid 1990s. I think that Vladimir's contributions to Quicksort go way beyond anything that I've ever done, and rank up there with Hoare's original design and Sedgewick's analysis. I feel so privileged to play a very, very minor role in helping Vladimir with the most excellent work! ----------------------------------------------- Let me know, if you have any questions/comments. Thank you, Vladimir Here is the details between steps (1) and (2) in the case of Dual-Pivot Quicksort: ----------------------------------------------------------------------------- >From the algorithm above, the average number of comparisons C_n as a function of the number of elements may be represented by the equation: (1) C_n = 1 + 2/(n*(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + 1*i + C_{j-i-1} + 2*(j-i- 1) + C_{n-j-1} + 2*(n-j-1)} Equation (1) means that total number is the sum of the comparison numbers of all cases of partitions into 3 parts plus number of comparisons for elements from left part (one comparison), center and right parts (2 comparisons). !!! It can be rewritten in other way: !!! (2) C_n = 1 + R*(n-2) + 2/(n(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + C_{j-i-1} + C_{n-j-1}} where R is the average number of comparisons during one iteration. This constant R can be found as average value (1 + 2 + 2) / 3 = 5/3 ~ 1.6666. ----------------------------------------------------------------------------- How it can be rewritten: We should show that 2/(n*(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {i + 2*(j-i- 1) + 2*(n-j-1)} equals to 5/3 * (n-2). Let's consider the double sum: sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {i + 2*(j-i- 1) + 2*(n-j-1)} = = sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {2*n - 4} - sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {i} = = 2*(n-2)*sum_{i=0}^{n-2} {n-1-i} - sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {i} = = 2*(n-2)*((n-1)^2 - (n-1)*(n-2)/2) - (n-1)*sum_{i=0}^{n-2} {i} + sum_{i=0}^{n-2} {i*i} = ------------------------------------------------------------------ here we use the property: sum_{k=1}{n} {k^2} = n^3/3 + n^2/2 + n/6 ------------------------------------------------------------------ = 2*(n-2)*((n-1)^2 - (n-1)*(n-2)/2) - (n-1)*(n-1)*(n-2)/2 + (n-2)^3/3 + (n-2)^2/2 + (n-2)/6 = = 1/6 * (12*(n-1)^2*(n-2) - 6*(n-1)*(n-2)^2 - 3*(n-1)^2*(n-2) + 2*(n-2)^3 + 3*(n-2)^2 + (n-2)) = = 1/6 * (3*(n-1)*(n-2)*(3*(n-1) - 2*(n-2)) + (n-2)*(2*(n-2)^2 + 3*(n-2) + 1))) = = 1/6 * (3*(n-1)*(n-2)*(n+1) + (n-2)*(2*n^2 - 5*n + 3)) = = 1/6 * (n-2)*(5*n^2 - 5*n) = 5/6 * n*(n-1)*(n-2) Substitute the result into equation (1): (1.1) C_n = 1 + 2/(n*(n-1)) * 5/6 * n*(n-1)*(n-2) + 2/(n*(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + C_{j-i-1} + C_{n-j-1}} or (1.2) C_n = 1 + 5/3*(n-2) + 2/(n*(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + C_{j-i-1} + C_{n-j-1}} We see that (1.2) is same as (2). /** * @author Vladimir Yaroslavskiy * @version 2009.09.10 m765 */ public class DualPivotQuicksort { public static void sort(int[] a) { sort(a, 0, a.length); } public static void sort(int[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); dualPivotQuicksort(a, fromIndex, toIndex - 1, 3); } private static void rangeCheck(int length, int fromIndex, int toIndex) { if (fromIndex > toIndex) { throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); } if (fromIndex < 0) { throw new ArrayIndexOutOfBoundsException(fromIndex); } if (toIndex > length) { throw new ArrayIndexOutOfBoundsException(toIndex); } } private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } private static void dualPivotQuicksort(int[] a, int left, int right, int div) { int len = right - left; if (len < 27) { // insertion sort for tiny array for (int i = left + 1; i <= right; i++) { for (int j = i; j > left && a[j] < a[j - 1]; j--) { swap(a, j, j - 1); } } return; } int third = len / div; // "medians" int m1 = left + third; int m2 = right - third; if (m1 <= left) { m1 = left + 1; } if (m2 >= right) { m2 = right - 1; } if (a[m1] < a[m2]) { swap(a, m1, left); swap(a, m2, right); } else { swap(a, m1, right); swap(a, m2, left); } // pivots int pivot1 = a[left]; int pivot2 = a[right]; // pointers int less = left + 1; int great = right - 1; // sorting for (int k = less; k <= great; k++) { if (a[k] < pivot1) { swap(a, k, less++); } else if (a[k] > pivot2) { while (k < great && a[great] > pivot2) { great--; } swap(a, k, great--); if (a[k] < pivot1) { swap(a, k, less++); } } } // swaps int dist = great - less; if (dist < 13) { div++; } swap(a, less - 1, left); swap(a, great + 1, right); // subarrays dualPivotQuicksort(a, left, less - 2, div); dualPivotQuicksort(a, great + 2, right, div); // equal elements if (dist > len - 13 && pivot1 != pivot2) { for (int k = less; k <= great; k++) { if (a[k] == pivot1) { swap(a, k, less++); } else if (a[k] == pivot2) { swap(a, k, great--); if (a[k] == pivot1) { swap(a, k, less++); } } } } // subarray if (pivot1 < pivot2) { dualPivotQuicksort(a, less, great, div); } } } At first consider the classic Quicksort scheme and find the average number of comparisons and swaps for it. We assume that input data is random permutation of n numbers from the range [1..n]. Classic Quicksort ================= 1. Choose a pivot element (take random), 2. Compare each (n-1) elements with the pivot 3. and swap it, if necessary, to have the partitions: [ <= pivot | >= pivot ] 4. Sort recursively left and right parts. >From the algorithm above, the average number of comparisons C_n as a function of the number of elements may be represented by the equation: (1) C_n = (n-1) + 1/n * sum_{k=0}^{n-1} {C_k + C_{n-k-1}} and last sum can be rewritten: (2) C_n = (n-1) + 2/n * sum_{k=0}^{n-1} C_k Write formula (2) for n+1: (3) C_{n+1} = n + 2/(n+1) * sum_{k=0}^{n} C_k Multiply (2) by n and (3) by (n+1) and subtract one from other, we have: (4) (n+1)*C_{n+1} - n*C_n = 2*n + 2*C_n Sorting an array of n elements may be considered as selecting one permutation of the n elements among all possible permutations. The number of possible permutations of n elements is n!, so the task for any sorting algorithm is to determine the one permutation out of n! possibilities. The minimum number of operations (swap and comparisons) for sorting n elements is const*ln(n!). >From the Stirling's formula the approximation of the number of operations is A*n*ln(n) + B*n + C, where A, B and C are constant coefficients. The coefficients B and C are not important for large n. Therefore, the function C_n may be approximated by the equation: (5) C_n = A*n*ln(n) The function C_n is substituted from equation (5) into equation (4), which yields the following equation: (6) (n+1)*A*(n+1)*ln(n+1) - n*A*n*ln(n) = 2*n + 2*A*n*ln(n) Using the properties of logarithms, equation (6) can then be reduced to: (7) n*ln(1+1/n) + 2*ln(1+1/n) + (1/n) * ln(n+1) = 2/A Using a property of logarithm: ln(1 + x) -> x, if x -> 0, and other property: ln(n) / n -> 0, when n -> +oo, equation (7) will be approximated by: (8) 1 + 0 + 0 = 2/A So, the coefficient A is equal to 2 and the average number of comparisons in sorting of n size arrays is (9) C_n = 2*n*ln(n). To find the approximation of the average number of swaps, we use the similar approach as in the case of comparisons. The average number of swaps S_n as a function of the number of elements may be represented by the equation: (10) S_n = 1/2*(n-1) + 2/n * sum_{k=0}^{n-1} S_k We assume that average number of swaps during one iteration is 1/2*(n-1). It means that in average one half of elements is swapped only. Using the same approach, we find that the coefficient A equals to 1. Therefore, the function S_n may be approximated by the equation: (11) S_n = n*ln(n) ------------------------------------------------------------------------------- Now consider the Dual-Pivot Quicksort scheme and find the average number of comparisons and swaps for it. We assume that input data is random permutation of n numbers from the range [1..n]. Dual-Pivot Quicksort ==================== 1. Choose 2 pivot elements pivot1 and pivot2 (take random), 2. pivot1 must be less or equal than pivot2, otherwise they are swapped 3. Compare each (n-2) elements with the pivots 4. and swap it, if necessary, to have the partitions: [ <= p1 | p1 <= & <= p2 | >= p2 ] 5. Sort recursively left, center and right parts. >From the algorithm above, the average number of comparisons C_n as a function of the number of elements may be represented by the equation: (1) C_n = 1 + 2/(n*(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + 1*i + C_{j-i-1} + 2*(j-i-1) + C_{n-j-1} + 2*(n-j-1)} Equation (1) means that total number is the sum of the comparison numbers of all cases of partitions into 3 parts plus number of comparisons for elements from left part (one comparison), center and right parts (2 comparisons). It can be rewritten in other way: (2) C_n = 1 + R*(n-2) + 2/(n(n-1)) * sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} {C_i + C_{j-i-1} + C_{n-j-1}} where R is the average number of comparisons during one iteration. This constant R can be found as average value (1 + 2 + 2) / 3 = 5/3, which means that elements from left part are required only one comparison, and elements form center and right parts - two comparisons. The double sum in equation (2) can be reduced: (3) C_n = 1 + 5/3*(n-2) + 2/(n*(n-1)) * sum_{k=0}^{n-2} {3 * (n-k-1) * C_k} Denote 1 + 5/3*(n-2) by f_n and multiply to n*(n-1): (4) n*(n-1)*C_n = n*(n-1)*f_n + 6 * sum_{k=0}^{n-2} {(n-k-1) * C_k} Write formula (4) for n+1: (5) n*(n+1)*C_{n+1} = n*(n+1)*f_n + 6 * sum_{k=0}^{n-1} {(n-k) * C_k} Subtract (4) from (5), we have: (6) n*(n+1)*C_{n+1} - n*(n-1)*C_n = n*(n+1)*f_n - n*(n-1)*f_n + 6 * sum_{k=0}^{n-2} C_k + 6*C_{n-1} Denote n*(n+1)*C_{n+1} - n*(n-1)*C_n by X_n and n*(n+1)*f_n - n*(n-1)*f_n by F_n: (7) X_n = F_n + 6 * sum_{k=0}^{n-2} C_k + 6*C_{n-1} Write formula (7) for n+1: (8) X_{n+1} = F_{n+1} + 6 * sum_{k=0}^{n-1} C_k + 6*C_n Subtract (7) from (8), we have: (9) X_{n+1} - X_n = F_{n+1} - F_n + 6*C_n Resolving of F_{n+1} - F_n gives: (10) X_{n+1} - X_n = 2 + 10*n + 6*C_n The function X_n is substituted into equation (10), which yields the following equation: (11) (n+1)*(n+2)C_{n+2} -2*n(n+1)*C_{n+1} + (n*(n-1) - 6)*C_n = 2 + 10*n We will find the function C_n approximated by the equation: (12) C_n = A*n*ln(n) The function C_n is substituted from equation (12) into equation (11), which yields the following equation: (13) (n^3+5*n^2+8*n+4)*ln(n+2) - (2*n^3+4*n^2+2*n)*ln(n+1) + (n^3-n^2-6*n)*ln(n) = (10*n+2) / A Using the properties of logarithms, equation (13) can then be reduced to: (14) n^3*(ln(n+2)-2*ln(n+1)+ln(n)) + n^2*(5*ln(n+2)-4*ln(n+1)-ln(n)) + n*(8*ln(n+2)-2*ln(n+1)-6*ln(n)) + 4*ln(n+2) = (10*n+2) / A Using a property of logarithm: ln(1 + x) -> x, if x -> 0, and other property: ln(n) / n -> 0, when n -> +oo, equation (15) will be approximated by: (15) -1 + 4 + 2 + 0 + 0 = 10 / A So, the coefficient A is equal to 2 and the average number of comparisons in sorting of n size arrays is (9) C_n = 2*n*ln(n). To find the approximation of the average number of swaps, we use the similar approach as in the case of comparisons. The average number of swaps S_n as a function of the number of elements may be represented by the equation: (10) S_n = 4 + 2/3*(n-2) + 2/(n*(n-1)) * sum_{k=0}^{n-2} {(n-k-1)*S_k} We assume that average number of swaps during one iteration is 2/3*(n-2). It means that in average one third of elements is swapped only. Using the same approach, we find that the coefficient A equals to 0.8. Therefore, the function S_n may be approximated by the equation: (11) S_n = 0.8*n*ln(n) ------------------------------------------------------------------------- And as summary: The value of the coefficient A: dual-pivot classic comparison: 2.0 2.0 swap: 0.8 1.0

14 20

8008662: Add @jdk.Supported to JDK-specific/supported API
by Alan Bateman 11 Sep '13

11 Sep '13

Joe Darcy recently added @jdk.Supported [1] to make it possible to identify JDK-specific APIs. I'd like to add this to a number of APIs in the com.sun namespace to make it obvious these are "supported". Specifically I'm proposing to add it to: - Java Debug Interface (com.sun.jdi) - Attach API (com.sun.tools.attach) - SCTP API (com.sun.nio.sctp) - HTTP server API (com.sun.net.httpserver) - Management extensions (com.sun.management) - JDK-specific API to JAAS (com.sun.security.auth) - JDK-specific JGSS API (com.sun.security.jgss) The javadoc for all of these is generated as part of the regular JDK "docs" build and so shouldn't be controversial. There are a number of other candidates in com.sun with murkier status that I've stayed clear of for now. The webrev with the changes is here: http://cr.openjdk.java.net/~alanb/8008662/webrev/ In a couple of cases the package description is legacy package.html so I've had to move/convert them to package-info.java. In all but one case I've added the annotation to the package-info, the one exception is com.sun.management where there is at least one type that is documented as "not supported". Joe Darcy might have suggestions on that. Otherwise this is mostly mechanical and the patch file is easier to review that the webrev. -Alan [1] http://hg.openjdk.java.net/jdk8/tl/langtools/rev/55cca2f38ee6

13 39

Request for Review: 5049299: (process) Use posix_spawn, not fork, on S10 to avoid swap exhaustion
by Rob McKenna 12 Aug '13

12 Aug '13

Hi folks, Looking for a review for the webrev below, which also resolves: 7175692: (process) Process.exec should use posix_spawn [macosx] For additional context and a brief description it would be well worth looking at the following thread started by Michael McMahon, who did the brunt of the work for this fix: http://mail.openjdk.java.net/pipermail/core-libs-dev/2009-May/thread.html#1… Basically the fix aims to swap fork for posix_spawn as the default process launch mechanism on Solaris and Mac OSX in order to avoid swap exhaustion issues encountered with fork()/exec(). It also offers a flag (java.lang.useFork) to allow a user to revert to the old behaviour. I'm having trouble seeing the wood for the trees at this point so I'm anticipating plenty of feedback. In particular I'd appreciate some discussion on: - The binary launcher name & property name may need some work. A more general property ("java.lang.launchMechanism") to allow a user to specify a particular call was mooted too. It may be more future proof and I'm completely open to that. (e.g. launchMechanism=spawn|fork|vfork|clone - we would obviously ignore inapplicable values on a per-platform basis) - I'd like a more robust way of checking that someone isn't trying to use jprochelper outside of the context for which it is meant. - The decision around which call to use getting moved to the java level and away from the native preprocessor. The webrev is at: http://cr.openjdk.java.net/~robm/5049299/webrev.01/ <http://cr.openjdk.java.net/%7Erobm/5049299/webrev.01/> Thanks a lot, -Rob

5 22

Re: RFR JDK-8003245
by John Zavgren 30 May '13

30 May '13

Florian: Yes, the uninitialized memory will be accessed in some cases, for example: @@ -1733,10 +1747,12 @@ CK_X9_42_DH1_DERIVE_PARAMS ckParam; jfieldID fieldID; jlong jKdf; jobject jOtherInfo, jPublicData; + memset(&ckParam, 0, sizeof(CK_X9_42_DH1_DERIVE_PARAMS));<--- added initialization + /* get kdf */ jX942Dh1DeriveParamsClass = (*env)->FindClass(env, CLASS_X9_42_DH1_DERIVE_PARAMS); if (jX942Dh1DeriveParamsClass == NULL) { return ckParam; } fieldID = (*env)->GetFieldID(env, jX942Dh1DeriveParamsClass, "kdf", "J"); if (fieldID == NULL) { return ckParam; } ----- Original Message ----- From: fweimer(a)redhat.com To: john.zavgren(a)oracle.com Cc: core-libs-dev(a)openjdk.java.net Sent: Wednesday, March 27, 2013 11:48:57 AM GMT -05:00 US/Canada Eastern Subject: Re: RFR JDK-8003245 On 03/20/2013 04:27 PM, John Zavgren wrote: > Please consider the following changes that eliminate the use of uninitialized memory. > http://cr.openjdk.java.net/~jzavgren/8003245/webrev.01/ Is the uninitialized memory accessed on the error paths? -- Florian Weimer / Red Hat Product Security Team

3 2

[PATCH] Review Request for 8009258: TEST_BUG: java/io/pathNames/GeneralWin32.java fails intermittently
by Eric Wang 29 May '13

29 May '13

Hi, Please help to review fix below for bug 8009258 <https://jbs.oracle.com/bugs/browse/JDK-8009258>, TEST_BUG:java/io/pathNames/GeneralWin32.java fails intermittently. http://cr.openjdk.java.net/~ewang/8009258/webrev.00/ The File.canRead() method should not be used to check read permission of a directory. Thanks, Eric

3 9

Re: Review Request: BigInteger patch for efficient multiplication and division (#4837946)
by Tim Buktu 13 May '13

13 May '13

Hi, I have updated the patch. It now contains Alan Eliasen's fast square() and pow() implementations. Special characters have been replaced with ASCII ones. Also included is a patched MutableBigInteger which uses the fast division algorithm in BigInteger, and a patched BigDecimal which uses the fast BigInteger.pow() method. Both changes speed up BigDecimal division. BigDecimal division is still much slower than BigInteger division (except BigDecimal.divideAndRound) because it calls doRound(), setScale(), and bigMultiplyPowerTen() which are pretty slow. Maybe these methods can be made more efficient. To view the four patched files (#4 is BigIntegerTest.java) on one page, go to https://gist.github.com/tbuktu/1576025 , or get them individually at https://gist.github.com/tbuktu/1576025/raw/96e9dfd9261862223aa9ff81618f1d85… https://gist.github.com/tbuktu/1576025/raw/447db955ef74b065b03b0b45abd443ce… https://gist.github.com/tbuktu/1576025/raw/6863a38032835b48b73cbce5aa833680… https://gist.github.com/tbuktu/1576025/raw/11977be7d001e093baa915b4370f326e… Semi-related: I think there is a bug in jdk/test/java/math/BigInteger/CompareToTests.java and jdk/test/java/math/BigDecimal/CompareToTests.java. It prints failures (with or without my patches) but the overall test doesn't fail. Tim

5 29

Review Request for JDK-8003992: File and other classes in java.io do not handle embedded nulls properly
by Dan Xu 06 May '13

06 May '13

Hi All, Please help review the fix for JDK-8003992: File and other classes in java.io do not handle embedded nulls properly. Java IO, not like NIO, does not check NUL character in the given file path name, which brings confusion to Java users. This fix is going to address this issue by removing any NUL character from the given file path. And it also cleans and optimizes the path-name normalization logic. Thanks! Bug: https://jbs.oracle.com/bugs/browse/JDK-8003992 webrev: http://cr.openjdk.java.net/~dxu/8003992/webrev.00/ -Dan

8 17

RFR (S) CR 8006627: Improving performance and reducing object allocations of java.util.UUID to/from string
by Steven Schlansker 30 Apr '13

30 Apr '13

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=8006627 I have created a patch that dramatically improves UUID to/from string performance. Please find below a webrev with my proposed changes. Thanks in advance for any feedback on the contents. I do not believe I have a committer lined up yet. My company has a signed OCA on file, "Ness Computing". http://dl.dropbox.com/u/1422321/uuid_webrev/index.html http://dl.dropbox.com/u/1422321/uuid_webrev.zip

4 18

Proxy.isProxyClass scalability
by Peter Levart 29 Apr '13

29 Apr '13

Hello, Recently I stumbled upon the scalability problem of j.l.r.Proxy.isProxyClass(Class) method when trying to find-out why the equals() method of annotations is not scalable. The reason is that j.l.r.Proxy uses a single synchronized wrapper around WeakHashMap to keep track of proxy classes in order to implement isProxyClass method: 244 /** set of all generated proxy classes, for isProxyClass implementation */ 245 private static Map<Class<?>, Void> proxyClasses = 246 Collections.synchronizedMap(new WeakHashMap<Class<?>, Void>()); 631 public static boolean isProxyClass(Class<?> cl) { 632 if (cl == null) { 633 throw new NullPointerException(); 634 } 635 636 return proxyClasses.containsKey(cl); 637 } In the discussion on the cuncurrency-interest list: * http://cs.oswego.edu/pipermail/concurrency-interest/2013-January/010642.html ...it was indicated that other places in JDK besides the annotation's equals() method suffer from this scalability bottleneck, mainly in the field of serialization, RMI and JMX. With the help from this discussion, I prepared a possible fix which I'm proposing here: http://dl.dropbox.com/u/101777488/jdk8-tl/isProxyClass/webrev.01/index.html The fix drops usage of synchronized wrapper and WeakHashMap and replaces them with a ClassValue and a little ThreadLocal trick to initialize it. The ThreadLocal trick could be replaced with a simple static variable guarded by a synchronized block if desired. I have some results from a micro-benchmark that exercises the annotation's equals method. The results were obtained on two different systems: * https://raw.github.com/plevart/jdk8-tl/proxy/test/benchmark_results.txt The benchmark sources: * https://github.com/plevart/jdk8-tl/blob/proxy/test/src/test/AnnotationEqual… * https://github.com/plevart/micro-bench/blob/master/src/si/pele/microbench/T… Thanks to Aleksey Shipilev for showing me the obvious pitfalls when designing a micro-benchmark. I hope this time it does the job correctly... What do you thik? Should I file a RFE first? Regards, Peter

7 63

Math.round(...) and bug 6430675
by Jeff Hain 23 Apr '13

23 Apr '13

Hi. Since 6430675 fix, Math.round(float) and Math.round(double) specs no longer specify rounding by adding 0.5 and then using floor, and let the user believe that they "now round up properly". However playing with fresh JDK 7 and 8 versions I saw that these methods still exhibit some suprising results coming from adding 0.5 and then using floor. For example, for odd values in [8388609.0f,16777215.0f] or [-16777215.0f,-8388609.0f], which are mathematical integers, Math.round(float) returns value+1. Shouldn't the references to floor(value+0.5(f/d)) be restored in the specs, or the implementations having a work-around for these cases? -Jeff

2 4