November 2012 - 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

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

javax.sql.rowset.serial.SerialBlob doesn't support free and getBinaryStream
by Deven You 10 Jan '13

10 Jan '13

Hi All, First of all, if the jdbc problem has a better mailing list to post please tell me. I find that javax.sql.rowset.serial.SerialBlob is not fully implemented in OpenJDK 8. Methods public InputStream getBinaryStream(long pos,long length) throws SQLException public void free() throws SQLException only throw UnsupportedOperationException. I have made a patch[1] to implement these 2 methods. Could anyone take a look to review it. BTW: I think the spec for SerialBlob is not very clear like it doesn't mention if all method rather than free() need throw any exception after free() is invoked. However that behavior seems reasonable. [1] http://cr.openjdk.java.net/~littlee/OJDK-576/webrev Thanks a lot. -- Best Regards, Deven

3 14

8003562: Provide a command-line tool to find static dependencies
by Mandy Chung 19 Dec '12

19 Dec '12

As part of prepare for modules [1], this RFE is to provide a command-line tool in JDK8 so that developers can understand the static dependencies of their applications and libraries.As part of Project Jigsaw, a useful class analyzer [2] was developed that makes it very easy to identify the dependencies based on the classfile library thathas also been enhanced to support dependency analysis [3]. Inspired by the sample tool that Jon Gibbons developed, we propose this new command-line name as "jdeps". $ ./bin/jdeps -h Usage: jdeps <options> <files....> where possible options include: -version Version information -classpath <path> Specify where to find class files -v --verbose Print class-level dependencies -r --reverse Invert the dependencies in the output -p Restrict analysis to classes in this package (may be given multiple times) -e --regex Restrict analysis to packages matching pattern (-p and -e are exclusive) -P --profile Show profile or the file containing a package -d --depth Specify the depth of the transitive dependency analysis Default depth is 1. Set depth to 0 to traverse all dependencies. -all Show all classes and members with no breakdown The jdeps tool shows package-level dependencies of the input files that can be .class files, a directory, or a JAR file. Specify the depth for the transitive dependency analysis; otherwise, it only analyzes the input files. jdeps -P option will show where the class/package comes from. For Java SE API, it will show the Profile name (I implement a workaround for now until the profile work is in jdk8). For JDK internal APIs, they will not be exported in modular world. jdeps will indicate any usage of the JDK internal APIs in the output to help developers prepare for transitioning to modules. See below for a few sample output. Webrev at: http://cr.openjdk.java.net/~mchung/jdk8/webrevs/8003562/ The implementation classes for jdeps are in the langtools repo along with the com.sun.tools.classfile library. I'm working on adding more unit tests. I'd like to get this webrev out to begin the discussion and get review feedback. Thanks Mandy [1] http://openjdk.java.net/jeps/162 [2] http://hg.openjdk.java.net/jigsaw/jigsaw/jdk/raw-file/543b0d24a920/make/too… [3] http://bugs.sun.com/view_bug.do?bug_id=6907575 Sample Output $./bin/jdeps demo/jfc/Notepad/Notepad.jar <unnamed> (demo/jfc/Notepad/Notepad.jar) -> java.awt -> java.awt.event -> java.beans -> java.io -> java.lang -> java.net -> java.util -> java.util.logging -> javax.swing -> javax.swing.border -> javax.swing.event -> javax.swing.text -> javax.swing.tree -> javax.swing.undo $ ./bin/jdeps -P demo/jfc/Notepad/Notepad.jar <unnamed> (demo/jfc/Notepad/Notepad.jar) -> java.awt compact4 -> java.awt.event compact4 -> java.beans compact4 -> java.io compact1 -> java.lang compact1 -> java.net compact1 -> java.util compact1 -> java.util.logging compact1 -> javax.swing compact4 -> javax.swing.border compact4 -> javax.swing.event compact4 -> javax.swing.text compact4 -> javax.swing.tree compact4 -> javax.swing.undo compact4 $ ./bin/jdeps -d 10 demo/jfc/Notepad/Notepad.jar <unnamed> (demo/jfc/Notepad/Notepad.jar) -> java.awt -> java.awt.event -> java.beans -> java.io -> java.lang -> java.net -> java.util -> java.util.logging -> javax.swing -> javax.swing.border -> javax.swing.event -> javax.swing.text -> javax.swing.tree -> javax.swing.undo java.security (/export/mchung/ws/jdeps-repo/build/macosx-x86_64/j2sdk-image/jre/lib/rt.jar) -> javax.crypto javax.crypto (/export/mchung/ws/jdeps-repo/build/macosx-x86_64/j2sdk-image/jre/lib/jce.jar) -> java.io -> java.lang -> java.lang.reflect -> java.net -> java.nio -> java.security -> java.security.cert -> java.security.spec -> java.util -> java.util.concurrent -> java.util.jar -> java.util.regex -> java.util.zip -> sun.security.jca JDK internal API -> sun.security.util JDK internal API javax.crypto.spec (/export/mchung/ws/jdeps-repo/build/macosx-x86_64/j2sdk-image/jre/lib/jce.jar) -> java.lang -> java.security.spec -> java.util

5 29

bottleneck by java.lang.Class.getAnnotations()
by Alexander Knöller 17 Dec '12

17 Dec '12

Hello there. (Reposting this request for improvement as suggested in mailing list jdk6-dev) java.lang.Class.getAnnotations() always enters a synchronized-block (initAnnotationsIfNecessary() ), slowing down multi core machines that heavily make use of Annotations. (in our Case we use LoadTimeWeaving in the spring-framework 3.1.2) We are using sun-jdk 6u27 on CentOS which has the same performance-bottleneck. I could not easily find sources for sunjdk (no open source anymore). So I do not know if Versions 7 or 8 contain fixes for this. openjdk7 and 8 show no fix so far, although it looks like it might be possible to build a kind of double-checked locking using local variables? I am not very familiar with concurrency while using SoftReferences, but I guess using a local Variable for concurrency-avoidance for the annotations-field or the target of the SoftReference, then doing a nonsynchronized check for the redefinition and a potential null-value on the local copy of the annotations-variable should suffice to decide that one could leave out the synced call and just returns the annotations-value (referenced by the local variable)? Also you would need to use a local variable while calculating the annotations prior to assigning the result to the annotations-field to avoid concurrency-effects on the double-checked locking. Since Code using getAnnotations() always could get hit by an annotations-result not fitting any more to the class because of a concurrent thread redefining the class we would not need to take care of this (and the current code could cause unexpected behaviour already inside "getAnnotations()" after exiting the lock on initAnnotationsIfNecessary()). Regards Alex Anfang der weitergeleiteten E-Mail: > Von: Alexander Knöller <alexander.knoeller(a)gmail.com> > Betreff: Re: bottleneck by java.lang.Class.getAnnotations() > Datum: 2. November 2012 08:43:06 MEZ > An: Joe Darcy <joe.darcy(a)oracle.com> > Kopie: Alan Bateman <Alan.Bateman(a)oracle.com>, jdk6-dev(a)openjdk.java.net > > I know. But there is a usual solution to those kind of problems: double checked locking. > This would avoid synchronization for all the cases where no redefinitions take place. > (I also put in a bug-report for the sunjdk where I elaborated this a bit more.) > I am not so familiar with concurrency while using SoftReferences, but I guess using a local Variable for concurrency-avoidance for the annotations-field or the target of the SoftReference, then doing a nonsynchronized check for the redefinition and a potentially null-value on the local copy of the annotations-variable should suffice to decide that one could leave out the synced call and just returns the annotations-value (in the local variable)? > > Also you would need to use a local variable while calculating the annotations-Field prior to assigning the result to the field to avoid concurrency-effects on the double-checked locking. > > Since Code using getAnnotations() always could trap in an annotations-result not fitting any more to the class because of concurrent redefinition we would not need to take care of this (and the current code could cause this already inside "getAnnotations()". > > -Alex > > Am 01.11.2012 um 15:56 schrieb Joe Darcy: > >> >> On 11/1/2012 7:11 AM, Alan Bateman wrote: >>> On 01/11/2012 13:17, Alexander Knöller wrote: >>>> Hi there. >>>> >>>> java.lang.Class.getAnnotations() always enters a synchronized-block, slowing down multi core machines that heavily make use of Annotations. >>>> (in our Case we use LoadTimeWeaving in the spring-framework 3.1.2) >>>> We are using sun-jdk 6 which has the same performance-bottleneck. >>>> openjdk7 and 8 show no fix so far, although it looks like it might be possible to build a kind of double-checked locking? >>>> >>>> Has this issue ever been persued? >>>> >>>> Special Regards >>>> Alex Knöller >>>> >>> If you have a proposal then I suggest bringing it to core-libs-dev for discussion. In addition to contention there are other issues that need attention there too, particularly the potential to deadlock and the overhead per Class when annotations aren't used. There's definitely some useful work that could be done there. >>> >>> >> >> Note that the block in question is synchronized so that getAnnotations returns the right result if the class has been redefined at runtime using an API for that purpose. >> >> -Joe >> >

8 48

Review Request: 8004201: add reducers to primitive type wrappers
by Akhil Arora 11 Dec '12

11 Dec '12

Hi Requesting review for some basic functionality related to lambdas - Add min, max, sum methods to the primitive wrapper classes - Byte, Short, Integer, Long, Float, Double and Character so as to be able to use them as reducers in lambda expressions. Add and, or, xor methods to Boolean. http://cr.openjdk.java.net/~akhil/8004201.0/webrev/ http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=8004201 Thanks

7 12

Request for Review : CR#8004015 : Add interface extends and defaults for basic functional interfaces
by Mike Duigou 10 Dec '12

10 Dec '12

Hello all; In the original patch which added the basic lambda functional interfaces, CR#8001634 [1], none of the interfaces extended other interfaces. The reason was primarily that the javac compiler did not, at the time that 8001634 was proposed, support extension methods. The compiler now supports adding of method defaults so this patch improves the functional interfaces by filing in the inheritance hierarchy. Adding the parent interfaces and default methods allows each functional interface to be used in more places. It is especially important for the functional interfaces which support primitive types, IntSupplier, IntFunction, IntUnaryOperator, IntBinaryOperator, etc. We expect that eventually standard implementations of these interfaces will be provided for functions like max, min, sum, etc. By extending the reference oriented functional interfaces such as Function, the primitive implementations can be used with the boxed primitive types along with the primitive types for which they are defined. The patch to add parent interfaces and default methods can be found here: http://cr.openjdk.java.net/~mduigou/8004015/0/webrev/ http://cr.openjdk.java.net/~mduigou/8004015/0/specdiff/java/util/function/p… Mike [1] http://hg.openjdk.java.net/jdk8/tl/jdk/rev/c2e80176a697

10 25

RFR: 8003596 CheckLockLocationTest-Windows-fix
by Jim Gish 04 Dec '12

04 Dec '12

Please review http://cr.openjdk.java.net/~jgish/Bug8003596-CheckLockLocationTest-Windows-… <http://cr.openjdk.java.net/%7Ejgish/Bug8003596-CheckLockLocationTest-Window…> Summary: fixes test when running on Windows so that test that requires setWritable is not run, because Windows does not support setWritable. Thanks, Jim -- Jim Gish | Consulting Member of Technical Staff | +1.781.442.0304 Oracle Java Platform Group | Core Libraries Team 35 Network Drive Burlington, MA 01803 jim.gish(a)oracle.com

2 5

JDBC bug: Incorrect number of conflicts is reported by CachedRowSetWriter.writeData
by Frank Ding 03 Dec '12

03 Dec '12

Hi guys, We discovered a bug in CachedRowSetWriter.writeData method where incorrect number of conflicts is reported. I searched in Oracle bug database and no similar record was found. So I submitted a new one whose internal review ID is 2376620. A test case with code is illustrated in the bug submission that leverages PostgreSQL server but the issue is platform independent and easy to reproduce. I provided a patch review, available @ http://cr.openjdk.java.net/~dingxmin/2376620/webrev.01/ Is there anybody who is interested in patch and can also review bug 2376620? Your reply is appreciated. Best regards, Frank

2 7

Request for review (XXS): JDK-8004066: TEST_BUG: test/java/lang/Math/DivModTests.java assumes ArithmeticException message
by Krystal Mo 03 Dec '12

03 Dec '12

Hi all, Could I get a couple of review for this small change, please? And could someone from the JDK side sponsor this change? Bug: https://jbs.oracle.com/bugs/browse/JDK-8004066 Webrev: http://cr.openjdk.java.net/~kmo/8004066/webrev.00/ The DivModTest introduced in JDK-6282196 [1] checks the contents of the exception message, but that message isn't specified in JavaDoc and thus may vary between VM implementations (or even in the same VM). The issue has affected HotSpot Server VM in nightlies, and the Shark VM. As OpenJDK library code may receive broader adoption in the future, this issue may affect other VM implementations in the future as well. (Details: The HotSpot Server Compiler may recompile hot throw sites to throw a preallocated exception object, with null exception message, leading to a NPE in the test; The bytecode interpreter in Zero/Shark VM throws the ArithmeticException with "/ by long zero" for ldiv, which is different from normal HotSpot behavior (which is expected by the test) where the exception message is "/ by zero".) This change relaxes the test so that it's more lenient and less sensitive to the error message produced by the VM. I don't think there's a good/reliable way of verifying whether an ArithmeticException came from "division by zero", checking the type should be enough for now. Tested with the failing nightly test case and jprt. $ java -Xcomp -showversion -XX:DefaultMaxRAMFraction=8 -XX:-TieredCompilation -XX:CompileThreshold=100 -XX:+UnlockExperimentalVMOptions -XX:+IgnoreUnrecognizedVMOptions -XX:+AggressiveOpts -XX:+IgnoreUnrecognizedVMOptions -XX:-UseCompressedOops DivModTests java version "1.8.0-ea" Java(TM) SE Runtime Environment (build 1.8.0-ea-b65) Java HotSpot(TM) 64-Bit Server VM (build 25.0-b11-internal-fastdebug, compiled mode) Exception in thread "main" java.lang.NullPointerException at DivModTests.resultEquals(DivModTests.java:390) at DivModTests.testIntFloorMod(DivModTests.java:126) at DivModTests.testIntFloorDivMod(DivModTests.java:103) at DivModTests.testIntFloorDivMod(DivModTests.java:68) at DivModTests.main(DivModTests.java:45) Description from the bug report: ~/jdk/test/java/lang/Math$ java -Xint -showversion DivModTests java version "1.8.0-ea" Java(TM) SE Runtime Environment (build 1.8.0-ea-b65) OpenJDK 64-Bit Shark VM (build 25.0-b11-internal, interpreted mode) FAIL: long Math.floorDiv(4, 0) = java.lang.ArithmeticException: / by long zero; expected java.lang.ArithmeticException: / by zero FAIL: long StrictMath.floorDiv(4, 0) = java.lang.ArithmeticException: / by long zero; expected java.lang.ArithmeticException: / by zero FAIL: long Math.floorMod(4, 0) = java.lang.ArithmeticException: / by long zero; expected java.lang.ArithmeticException: / by zero FAIL: long StrictMath.floorMod(4, 0) = java.lang.ArithmeticException: / by long zero; expected java.lang.ArithmeticException: / by zero Exception in thread "main" java.lang.RuntimeException: 4 errors found in DivMod methods. at DivModTests.main(DivModTests.java:49) Regards, Kris [1]: https://jbs.oracle.com/bugs/browse/JDK-6282196

4 8