April 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

review request: 4244896: (process) Provide System.getPid(), System.killProcess(String pid)
by Rob McKenna 26 Jun '12

26 Jun '12

Hi folks, I'm hoping for some feedback on the above. Webrev: http://cr.openjdk.java.net/~robm/4244896/webrev.00/ This bug adds two abstract methods to Process.java with the intention of: 1) providing a facility to implement a destroyForcibly method. In practical terms this means provide a method that will send a SIGKILL to the subprocess in *nix environments as opposed to the SIGTERM that is currently being sent. (Windows' destroy() method effectively behaves like this already) 2) providing a facility to check whether the subprocess is still alive. As per the bug report the toString/pid work has been left to be completed separately. Notes: a) It has been pointed out to me that the addition of abstract methods to java.lang.Process should be discussed, particularly as to whether default methods should be provided. b) In src/windows/native/java/lang/ProcessImpl_md.c I chose to use WaitForSingleObject on the off chance that a process may choose to return STILL_ACTIVE as an error code. Thanks! -Rob

8 35

<core-libs-dev> sun.management.Agent: the properties.putAll API may fail with ConcurrentModifcationException on multi-thread scenario
by Deven You 17 May '12

17 May '12

Hi core-libs-devs, I am not sure if sun.management.Agent belongs to jmx-dev mailing list, if so please anyone tell me. This issue is that the sun.management.Agent.loadManagementProperties() will invoke properties.putAll which will throw ConcurrentModifcationException if there are other threads which modify the properties concurrently. I have made a patch[1] which synchronize the sysProps so that putAll can work on multi-thread scenario. The test case is also available in [1]. Thanks a lot! [1] http://cr.openjdk.java.net/~littlee/OJDK-256/webrev.00 <http://cr.openjdk.java.net/%7Elittlee/OJDK-256/webrev.00> -- Best Regards, Deven

4 17

RFR: 5015163 "(str) String merge/join that is the inverse of String.split()" into JDK 8
by Jim Gish 03 May '12

03 May '12

This enhancement proposal has a long history. The most recent attempt to get some String.join() methods was by Joe Darcy back in 2009 ( http://mail.openjdk.java.net/pipermail/core-libs-dev/2009-October/002967.ht…) He started with the changes that Remi Forax had done 8 months prior to that, which Remi had attempted a year before that! I've taken the work that Remi and Joe did and am trying again. There was a lot of discussion that was generated and that is why this has died on the vine a number of times. I realize that the current proposal may also generate discussion, but I think this had merit 4 years ago and still does. We won't satisfy everyone. It may not be perfect (what is?!), but if we can look at it from the perspective that something is better than nothing, then we ought to attempt a quick review and get this in. Having said that, I ask that you please take a look at the http://cr.openjdk.java.net/~jgish/5015163/webrev/ <http://cr.openjdk.java.net/%7Ejgish/5015163/webrev/> Just a few words, based on the previous discussion, to set some context. * join() is (roughlty) intended to be the inverse of split() * example: "Hi there".join("-", "Bill", "Joe", "Zoe") will yield "Hi there-Bill-Joe-Zoe" * in the original proposal the delimiter character was what you started with, i.e. o "-".join( "Hi there", "Bill", "Joe", "Zoe") yielded the same result as above o it seemed awkward to have the delimiter be the String instance that the join was performed on. I agree and so have made the first parameter of the join be the delimiter. * there was a lot of discussion about the pros and cons of making join() a static method vs an instance method. The point was made then, and I concur, that given that split() is an instance method, it only makes sense that join() be one too. Certainly there are other perspectives on this and one could argue the merit of each and every one of them, but in the interests of progress, I think the the split()/join() similarity argument is the most compelling and natural. Thanks, Jim Gish

4 13

Re: Proposed refactoring: introduce JLS7 language features to core libs
by Stefan Reich 02 May '12

02 May '12

Hello, is there any interest to accept change sets based on OpenJDK 7 that update the java classes in jdk/src/share/classes to use * multi-catch * string switch statements as opposed to nested if statements when comparing strings with string literals * type inference by removing duplicative type information in the constructor when using generics * indexOf(int) when indexOf(String) is used with a String literal that contains only one character, and similar small-scale improvements? The proposed change sets would pass all jtreg tests. If there is interest, what would be next steps? Regards, Stefan Reich

3 5

Review Request: 7164376 Replace use of sun.security.action.LoadLibraryAction
by Mandy Chung 02 May '12

02 May '12

7164376 Replace use of sun.security.action.LoadLibraryAction with direct call of System.loadLibrary Webrev: http://cr.openjdk.java.net/~mchung/jdk8/webrevs/7164376/webrev.00/ This change is required for jdk modularization. High level summary: it replaces the use of LoadLibraryAction: FROM: java.security.AccessController.doPrivileged(new LoadLibraryAction("net")); TO: AccessController.doPrivileged( new java.security.PrivilegedAction<Void>() { public Void run() { System.loadLibrary("net"); return null; } }); It touches files in awt, security and serviceability area (cc'ed). For this type of simple change, I think 1-2 reviewers can review all files (simpler to review jdk.patch) and no need for all teams to do the reviews. System.loadLibrary and Runtime.loadLibrary loads a system library of the given library name that requires RuntimePermission("loadLibrary."+lib) permission. Many places in the JDK code loading a system native library is using the sun.security.action.LoadLibraryAction convenient class that will load the system library as a privileged action: java.security.AccessController.doPrivileged(new LoadLibraryAction("net")); The search path of native libraries are coupled with an associated class loader. For example, the application class loader uses the path specified in the "java.library.path" system property for native library lookup. The loadLibrary implementation uses the caller's class loader for finding the native library being requested. For system libraries, the class loader is null and the system library lookup is handled as a special case. When the sun.security.action.LoadLibraryAction class is used that is the caller of System.loadLibrary, the caller's class loader in this case is "null" loader and thus it always finds the native library from the system library path. In a modular world, JDK modules may be loaded by multiple different module class loader. The following code would not work if it is expected to load a native library from a module which is not the module where the sun.security.action.LoadLibraryAction lives. For example, the management module is trying to load libmanagement.so. Calling the following will fail to find libmanagement.so because the caller of System.loadLibrary is the LoadLibraryAction which is in the base module and search the library from the base module only. To prepare for jdk modularization, the use of LoadLibraryAction should be replaced with a direct call of System.loadLibrary. This patch also removes sun.security.action.LoadLibraryAction class to avoid regression. Thanks Mandy

5 7

Codereview request for 7014640: To add a metachar \R for line ending and character classes for vertical/horizontal ws \v \V \h \H
by Xueming Shen 02 May '12

02 May '12

Hi Here are the webrev and blenderrev for the proposed change to add 5 new regex constructs \R \v \V \h \V. \R: recommended by Unicode Regex TR#18 for matching all line ending characters and sequences, is equivalent to ( \u000D\u000A | [\u000A\u000B\u000C\u000D\u0085\u2028\u2029] ) \h, \v, \H and \V: matches any character considered to (not) be horizontal/vertical whitespace. Webrev: http://cr.openjdk.java.net/~sherman/7014640/blenderrev.html Blenderrev: http://cr.openjdk.java.net/~sherman/7014640/blenderrev.html new Pattern api http://cr.openjdk.java.net/~sherman/7014640/Pattern.html Here are couple notes regarding the spec/implementation. (1) \v was implemented as \u000B ('\013'), but not documented (did not appear in our API doc as one supported construct, such as \t \r \n...). To define \v as a "general" construct for all vertical whitespace characters might trigger some compatibility concerns (more characters are now matched by \v). But given this is a never documented implementation detail and the \u000B is still being matched by \v, I would consider this as an acceptable behavior change. (2) a predefined character class can appear inside another character class, for example you can have [...\v...], however, since it represents a "class" of character, so it can't be a start or end code point of a range inside a class, so you can have [a-b], but you can't have [\h-...] or [...-\h] (exception will be thrown). But for \v, since it was implemented as \u000B (VT), you were able to put it as a start or end value of a range, I feel it'd be better still keep it the way it worked before, so [\v-\v] works and will match the VT in this implementation. (3) The newly added \h\v\H\V constructs are all "Unicode version" of character classes, the rest of the "predefined character class" family (\d\D\s\S\w\W) are ASCII only, you will have to turn on flag UNICODE_CHARACTER_CLASS to get the Unicode version of these constructs. This is kinda of inconsistent. Perl's corresponding constructs work in a similar way, all Perl's \d\D\s\S \w\W\v\V\h\H work in Unicode version, and to have a \a modifier to turn the \d\D\s\S\w\W back to ASCII mode but not for \h\v\H\V. We had the discussion back into JDK7 regarding the ASCII vs Unicode for these constructs, the decision then was to keep these predefined character classes (and POSIX character classes) ASCII by default, to have a flag UNICODE_CHARACTER_CLASS to turn them into Unicode version. Given there is NOT an ASCII version in Perl and we didn't have ASCII version in Java regex to trigger compatibility concern, I feel it might be better to just have a simple Unicode version of \h\v\H\V. (4)\R is not a character class, since it matched \r\n. This one will need to go through ccc process. Thanks, -Sherman

2 2

Remove the assert in Integer.valueOf()
by Rémi Forax 01 May '12

01 May '12

Hi guys, I've found a case where assert is harmful because it doesn't play well with Hotspot inlining heuristic. I'm currently playing with a lambda modified implementation of java.util and as you see below Integer.valueOf is considered as too big by Hotspot to be inlined. 79 2 b lambda.perf.Iterables::filterMapReduce (72 bytes) @ 4 java.util.AbstractList::iterator (10 bytes) inline (hot) @ 6 java.util.AbstractList$Itr::<init> (6 bytes) unloaded signature classes @ 61 java.util.AbstractList$Itr::hasNext (20 bytes) inline (hot) @ 8 java.util.Arrays$ArrayList::size (6 bytes) inline (hot) ! @ 16 java.util.AbstractList$Itr::next (45 bytes) inline (hot) @ 1 java.util.AbstractList$Itr::checkForComodification (23 bytes) inline (hot) @ 14 java.util.Arrays$ArrayList::get (7 bytes) inline (hot) @ 29 lambda.perf.Test$1::accept (9 bytes) inline (hot) @ 5 lambda.perf.Test$1::accept (13 bytes) inline (hot) @ 1 java.lang.Integer::intValue (5 bytes) inline (hot) @ 45 lambda.perf.Test$2::map (9 bytes) inline (hot) @ 5 lambda.perf.Test$2::map (2 bytes) inline (hot) @ 52 lambda.perf.Test$3::apply (13 bytes) inline (hot) @ 9 lambda.perf.Test$3::apply (13 bytes) inline (hot) @ 1 java.lang.Integer::intValue (5 bytes) inline (hot) @ 5 java.lang.Integer::intValue (5 bytes) inline (hot) @ 9 java.lang.Integer::valueOf (54 bytes) too big @ 61 java.util.AbstractList$Itr::hasNext (20 bytes) inline (hot) @ 8 java.util.Arrays$ArrayList::size (6 bytes) inline (hot) but the code of Integer.valueOf doesn't seem too big: public static Integer valueOf(int i) { assert IntegerCache.high >= 127; if (i >= IntegerCache.low && i <= IntegerCache.high) return IntegerCache.cache[i + (-IntegerCache.low)]; return new Integer(i); } The issue is that Hotspot also count the bytecodes related to assert in its inlining heuristic. If the assert is commented, the inlining tree is good. 88 2 b lambda.perf.Iterables::filterMapReduce (72 bytes) @ 4 java.util.AbstractList::iterator (10 bytes) inline (hot) @ 6 java.util.AbstractList$Itr::<init> (6 bytes) unloaded signature classes @ 61 java.util.AbstractList$Itr::hasNext (20 bytes) inline (hot) @ 8 java.util.Arrays$ArrayList::size (6 bytes) inline (hot) ! @ 16 java.util.AbstractList$Itr::next (45 bytes) inline (hot) @ 1 java.util.AbstractList$Itr::checkForComodification (23 bytes) inline (hot) @ 14 java.util.Arrays$ArrayList::get (7 bytes) inline (hot) @ 29 lambda.perf.Test$1::accept (9 bytes) inline (hot) @ 5 lambda.perf.Test$1::accept (13 bytes) inline (hot) @ 1 java.lang.Integer::intValue (5 bytes) inline (hot) @ 45 lambda.perf.Test$2::map (9 bytes) inline (hot) @ 5 lambda.perf.Test$2::map (2 bytes) inline (hot) @ 52 lambda.perf.Test$3::apply (13 bytes) inline (hot) @ 9 lambda.perf.Test$3::apply (13 bytes) inline (hot) @ 1 java.lang.Integer::intValue (5 bytes) inline (hot) @ 5 java.lang.Integer::intValue (5 bytes) inline (hot) @ 9 java.lang.Integer::valueOf (32 bytes) inline (hot) @ 28 java.lang.Integer::<init> (10 bytes) call site not reached @ 61 java.util.AbstractList$Itr::hasNext (20 bytes) inline (hot) @ 8 java.util.Arrays$ArrayList::size (6 bytes) inline (hot) Given that Integer.valueOf() is a method used very often and that if the inlining fails, the escape analysis will not remove the allocation, I think it's a good idea to comment this assert. cheers, Rémi

7 17

RFR: 7103570 AtomicIntegerFieldUpdater does not work when SecurityManager is installed
by David Holmes 30 Apr '12

30 Apr '12

http://cr.openjdk.java.net/~dholmes/7103570/webrev/ Basic fix is to call getDeclaredField() inside a doPrivileged block. In addition the call to checkPackageAccess is now conditional - it allows for, for example, a class in sun.misc to create a field updater for another class in sun.misc. Finally the @throws spec for newUpdater has been expanded to say: @throws RuntimeException with a nested reflection-based exception if the class does not hold field or is the wrong type, + or the field is inaccessible to the caller according to Java language + access control This last part requires CCC approval which I will initiate. I have a glitch with running the test under jtreg but hopefully that will get sorted soon (jtreg fails if a security manager is installed). Thanks, David Holmes ------------

4 7

hg: jdk8/tl/jdk: 6996372: synchronizing handshaking hash
by xuelei.fan＠oracle.com 27 Apr '12

27 Apr '12

Changeset: f0842ed897c3 Author: xuelei Date: 2012-04-27 04:25 -0700 URL: http://hg.openjdk.java.net/jdk8/tl/jdk/rev/f0842ed897c3 6996372: synchronizing handshaking hash Summary: remove the unnecessary synchronization. Also reviewed by David Schlosnagle (schlosna(a)gmail.com) Reviewed-by: weijun ! src/share/classes/sun/security/util/DisabledAlgorithmConstraints.java

1 0