December 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

Re: RFR: 8001647: In-place methods on Collection/List
by Akhil Arora 21 Apr '13

21 Apr '13

Updated with yours and Alan's comments - http://cr.openjdk.java.net/~akhil/8001647.2/webrev/ - removed null check for removeSet - cache this.size in removeAll, replaceAll (for ArrayList, Vector and CopyOnWriteArrayList) - calculate removeCount instead of BitCount.cardinality() - removed unnecessary @library from test support classes Catching IndexOOB and throwing CME in forEach/removeAll/replaceAll seems unecessary... did you have a use-case in mind where an IndexOOB can occur with these methods? Thanks On 12/08/2012 05:11 AM, Arne Siegel wrote: > ArrayList.java, line 1171: > final boolean anyToRemove = (removeSet != null) && !removeSet.isEmpty(); > As removeSet will never be null, this line can be simplified. This is a left-over from the > preceding implementation (see b67). > > ArrayList.java, method forEach optimizes the loop by reducing the number of heap accesses: > final int size = this.size; > for (int i=0; modCount == expectedModCount && i < size; i++) { > ... > This trick might also be introduced to methods removeAll and replaceAll. > > In the ListIterator implementation of ArrayList, there are various appearances of the idiom: > try { > ... > } catch (IndexOutOfBoundsException ex) { > throw new ConcurrentModificationException(); > } > This technique might also be used in forEach, removeAll, and replaceAll (though not likely to > be of any importance). > > Regards > Arne Siegel >

5 16

JDK 8 code review request for 8005042 Add Method.isDefault to core reflection
by Joe Darcy 13 Apr '13

13 Apr '13

Hello, Please review these changes to add core reflection support to recognize default methods: 8005042 Add Method.isDefault to core reflection http://cr.openjdk.java.net/~darcy/8005042.0/ Thanks, -Joe

9 21

Re: [PATCH] Sunbug 7131192: Optimize BigInteger.doubleValue(), floatValue()
by Louis Wasserman 14 Feb '13

14 Feb '13

Hi, I'm working at Google now, but I'd like to revive this patch as a contribution from Google. At the moment, what's mainly needed is review for http://bugs.sun.com/view_bug.do?bug_id=7192954, the fix to Float.parseFloat's rounding behavior, before we can go anywhere with the patch to optimize BigInteger.floatValue() and doubleValue(). > Would anyone be able to review that patch so these can start moving forward? Thanks, > Louis Wasserman Java Core Libraries Team @ Google guava-libraries.googlecode.com ---------- Forwarded message ---------- > From: Louis Wasserman <wasserman.louis(a)gmail.com> > Date: Sat, Jul 14, 2012 at 5:32 AM > Subject: Re: [PATCH] Sunbug 7131192: Optimize BigInteger.doubleValue(), > floatValue() > To: Joseph Darcy <joe.darcy(a)oracle.com> > Cc: Andrew Haley <aph(a)redhat.com>, core-libs-dev(a)openjdk.java.net > > > Understood. FYI, testing for this change revealed a bug in > Float.parseFloat, a patch for which has been separately sent to this > mailing list under the subject line "[PATCH] Sunbug 6358355: Rounding error > in Float.parseFloat". (As a result, the BigInteger patch may fail some of > the provided tests at the moment, but that is truly because the reference > implementation it's being tested against is faulty.) > > Louis Wasserman > wasserman.louis(a)gmail.com > http://profiles.google.com/wasserman.louis > > > On Sat, Jul 14, 2012 at 2:20 AM, Joseph Darcy <joe.darcy(a)oracle.com>wrote: > >> Hello, >> >> Thanks for the patch Louis. >> >> >> On 7/12/2012 3:21 AM, Andrew Haley wrote: >> >>> On 07/12/2012 10:32 AM, Louis Wasserman wrote: >>> >>>> It was attached to the previous message? I don't know if this list >>>> works >>>> with attachments. Alternately, the patch was attached here: >>>> https://bugs.openjdk.java.net/**show_bug.cgi?id=100222<https://bugs.openjdk.java.net/show_bug.cgi?id=100222> >>>> >>>> I'm not sure what you mean by double-rounding bugs, though. It's >>>> not difficult to actually implement the HALF_EVEN rounding behavior >>>> with bit twiddling. >>>> >>> Sure, as long as you've thought about it and done it carefully. The >>> bit twiddling is easy to do, and easy to get wrong. >>> >>> > From the supplied patch it looks like you've done a good job, but >>> there was no way to tell without it. I presume the listserv dropped >>> it on the floor. >>> >>> Andrew. >>> >> >> I've taken a quick look at the patch. The concept for the change is >> good; the current path of converting to float/double through a string is a >> simple but very roundabout way to accomplish this task. >> >> Unfortunately, I'm saturated with the JDK bug migration [1] and will >> continue to be saturated for at least several more weeks so I won't be able >> to take a more detailed look at the patch for a while. I suspect some more >> directly test cases will be needed to test tricky rounding situations. >> >> Thanks, >> >> -Joe >> >> [1] https://blogs.oracle.com/**darcy/entry/moving_monarchs_**dragons<https://blogs.oracle.com/darcy/entry/moving_monarchs_dragons> >> > > > -- Louis Wasserman

1 1

IdentityHashMap.[keySet|values|entrySet].toArray speed-up
by Peter Levart 14 Feb '13

14 Feb '13

Hi all, I propose a patch to java.util.IdentityHashMap to speed-up toArray methods of it's keySet, values and entrySet views: http://dl.dropbox.com/u/101777488/jdk8-tl/IdentityHashMap/webrev.01/index.h… I toyed with the possibility to replace HashMap-s, that are used in java.lang.Class and java.lang.reflect.[Field|Method|Constructor] to hold cached annotations, with IdentityHashMap-s. They are a perfect replacement, since keys in these maps are java.lang.Class objects. They are more compact then HashMap-s. This is the comparison of allocated heap bytes between HashMap and IdentityHashMap for various sizes and corresponding capacities which takes into account the size of the Map object, the size of allocated array and the size of Map.Entry-s in case of HM (IHM doesn't have them) and the size of associated values Collection view (allocated when dumping annotations to array). HM-s for annotations are currently allocated with default initial capacity (16). I propose to allocate IHM-s with initial capacity 8 that fits to hold 5 entries which is enough for typical annotation use cases on one hand and still makes improvement for any case on the other: 32 bit JVM: | HashMap | IdentityHashMap | size|capacity bytes|capacity bytes|IHM.bytes-HM.bytes --------+-----------------+-----------------+------------------ 0| 16 144| 8 136| -8 1| 16 168| 8 136| -32 2| 16 192| 8 136| -56 3| 16 216| 8 136| -80 4| 16 240| 8 136| -104 5| 16 264| 8 136| -128 6| 16 288| 16 200| -88 7| 16 312| 16 200| -112 8| 16 336| 16 200| -136 9| 16 360| 16 200| -160 10| 16 384| 16 200| -184 11| 16 408| 16 200| -208 12| 16 432| 32 328| -104 13| 32 520| 32 328| -192 14| 32 544| 32 328| -216 15| 32 568| 32 328| -240 16| 32 592| 32 328| -264 17| 32 616| 32 328| -288 18| 32 640| 32 328| -312 19| 32 664| 32 328| -336 20| 32 688| 32 328| -360 40| 64 1296| 64 584| -712 60| 128 2032| 128 1096| -936 80| 128 2512| 128 1096| -1416 100| 256 3504| 256 2120| -1384 120| 256 3984| 256 2120| -1864 140| 256 4464| 256 2120| -2344 160| 256 4944| 256 2120| -2824 180| 256 5424| 512 4168| -1256 64 bit JVM: | HashMap | IdentityHashMap | size|capacity bytes|capacity bytes|IHM.bytes-HM.bytes --------+-----------------+-----------------+------------------ 0| 16 248| 8 240| -8 1| 16 296| 8 240| -56 2| 16 344| 8 240| -104 3| 16 392| 8 240| -152 4| 16 440| 8 240| -200 5| 16 488| 8 240| -248 6| 16 536| 16 368| -168 7| 16 584| 16 368| -216 8| 16 632| 16 368| -264 9| 16 680| 16 368| -312 10| 16 728| 16 368| -360 11| 16 776| 16 368| -408 12| 16 824| 32 624| -200 13| 32 1000| 32 624| -376 14| 32 1048| 32 624| -424 15| 32 1096| 32 624| -472 16| 32 1144| 32 624| -520 17| 32 1192| 32 624| -568 18| 32 1240| 32 624| -616 19| 32 1288| 32 624| -664 20| 32 1336| 32 624| -712 40| 64 2552| 64 1136| -1416 60| 128 4024| 128 2160| -1864 80| 128 4984| 128 2160| -2824 100| 256 6968| 256 4208| -2760 120| 256 7928| 256 4208| -3720 140| 256 8888| 256 4208| -4680 160| 256 9848| 256 4208| -5640 180| 256 10808| 512 8304| -2504 I hope I've got that tables right. This is the program to compute them: https://raw.github.com/plevart/jdk8-tl/JEP-149.2/test/src/test/IHMvsHMsizes… IHM is also more performant when retrieving the values by keys. The only area in which it lags behind HashMap and is important for accessing annotations in bulk is the toArray method of the values view. In particular for small sizes. The above patch speeds-up those methods by using index iteration instead of Iterator. Here are some speed-up comparisons: https://raw.github.com/plevart/jdk8-tl/JEP-149.2/test/IHM_benchmark_results… They are obtained by running the following micro benchmark: https://raw.github.com/plevart/jdk8-tl/JEP-149.2/test/src/test/IdentityHash… Even if IHM doesn't replace HM for holding annotations, a speed-up improvement is an improvement. Regards, Peter

3 4

Proposal: Fully Concurrent ClassLoading
by David Holmes 04 Feb '13

04 Feb '13

Java 7 introduced support for parallel classloading by adding to each class loader a ConcurrentHashMap, referenced through a new field, parallelLockMap. This contains a mapping from class names to Objects to use as a classloading lock for that class name. This scheme has a number of inefficiencies. To address this we propose for Java 8 the notion of a fully concurrent classloader ... This is a fairly simple proposal that I've written up as a blog entry: https://blogs.oracle.com/dholmes/entry/parallel_classloading_revisited_full… Please discuss this proposal here. Thanks, David Holmes

7 42

Improving performance and reducing object allocations of java.util.UUID to/from string
by Steven Schlansker 29 Jan '13

29 Jan '13

Hello core-libs-dev, My company uses UUIDs throughout our software. We recently identified that the java.util.UUID implementations of fromString and toString are horridly inefficient. An incomplete list of the inefficiencies: * fromString uses a regular expression that is not even precompiled * fromString uses a regular expression to parse out the "-" markers, requiring the allocation of many String and String[] objects, when a simple linear scan works just fine * fromString unnecessarily allocates multiple Long objects * toString creates a char[64], a String object which copies that, and a sub-String object for *each* of the 5 hex digit segments * toString produces a fixed-length result but involves multiple StringBuilder concatenations Everyone that I have shown the relevant code to has been horrified by the complete lack of care towards object allocations. While I am a big fan of the "object allocation is free until otherwise proven" philosophy, we traced multiple production problems down to these hotspots. But instead of just whining about it, I wish to contribute a patch which I believe fixes the problem. This is my first attempt to submit anything to the JDK, so please be nice :-) My initial attempt has yielded micro benchmarks with very favorable outcomes. By taking the appropriate code from java.lang.Long, modifying it to work on a single pre-allocated array+offset rather than returning a String, and scanning for dashes instead of regex splitting I reduced times 3-6x and object allocations to the low single digits. My Google Caliper benchmark is available here, to ensure that I have not committed any benchmark sins: https://gist.github.com/4356621 benchmark instances Bytes ns linear runtime JdkUuidFromString 51.00 1544.0 608.2 ============================== NewUuidFromString 2.00 72.0 179.1 ======== JdkUuidToString 31.00 1720.0 321.4 =============== NewUuidToString 3.00 200.0 51.5 == In particular, the reduction of object allocations from ~1.5KB to 72/200 bytes dramatically reduces GC pressure when you sit in a tight loop deserializing millions of UUIDs from strings. I believe the same patch can (and should?) apply to jdk7u and jdk8, as the code does not seem to have changed. I would appreciate any feedback on the code style, efficiency, or correctness that you can offer. I have run the "java/util/UUID" jtreg suite against this and it passes. We stole the more thorough Apache Harmony tests for this and they pass as well: https://github.com/stevenschlansker/components-ness-core/blob/master/src/te… I have not yet secured a CLA, but my company is in the process of signing one. The rest of the message is a "hg export" of my change set, which is current to the tip of jdk7. Happy holidays, and thank you for your time! Steven Schlansker # HG changeset patch # User Steven Schlansker <steven(a)nesscomputing.com> # Date 1356737383 0 # Node ID a812c963b96f08112f6805cbc380b12af196f788 # Parent 9b8c96f96a0f9a5801b55530a387fefbe50482a3 java.util.UUID: improve performance of UUID#toString and UUID#fromString by avoiding many unnecessary object allocations. benchmark instances Bytes ns linear runtime JdkUuidFromString 51.00 1544.0 608.2 ============================== NewUuidFromString 2.00 72.0 179.1 ======== JdkUuidToString 31.00 1720.0 321.4 =============== NewUuidToString 3.00 200.0 51.5 == diff -r 9b8c96f96a0f -r a812c963b96f src/share/classes/java/util/UUID.java --- a/src/share/classes/java/util/UUID.java Mon Jun 27 13:21:34 2011 -0700 +++ b/src/share/classes/java/util/UUID.java Fri Dec 28 23:29:43 2012 +0000 @@ -189,26 +189,79 @@ * described in {@link #toString} * */ - public static UUID fromString(String name) { - String[] components = name.split("-"); - if (components.length != 5) - throw new IllegalArgumentException("Invalid UUID string: "+name); - for (int i=0; i<5; i++) - components[i] = "0x"+components[i]; + public static UUID fromString(String str) { + int dashCount = 4; + int [] dashPos = new int [6]; + dashPos[0] = -1; + dashPos[5] = str.length(); - long mostSigBits = Long.decode(components[0]).longValue(); + for (int i = str.length()-1; i >= 0; i--) { + if (str.charAt(i) == '-') { + if (dashCount == 0) { + throw new IllegalArgumentException("Invalid UUID string: " + str); + } + dashPos[dashCount--] = i; + } + } + + if (dashCount > 0) { + throw new IllegalArgumentException("Invalid UUID string: " + str); + } + + long mostSigBits = decode(str, dashPos, 0) & 0xffffffffL; mostSigBits <<= 16; - mostSigBits |= Long.decode(components[1]).longValue(); + mostSigBits |= decode(str, dashPos, 1) & 0xffffL; mostSigBits <<= 16; - mostSigBits |= Long.decode(components[2]).longValue(); + mostSigBits |= decode(str, dashPos, 2) & 0xffff); - long leastSigBits = Long.decode(components[3]).longValue(); + long leastSigBits = decode(str, dashPos, 3) & 0xffffL; leastSigBits <<= 48; - leastSigBits |= Long.decode(components[4]).longValue(); + leastSigBits |= decode(str, dashPos, 4) & 0xffffffffffffL; return new UUID(mostSigBits, leastSigBits); } + private static long decode(final String str, final int [] dashPos, final int field) { + int start = dashPos[field]+1; + int end = dashPos[field+1]; + if (start >= end) { + throw new IllegalArgumentException("Invalid UUID string: " + str); + } + long curr = 0; + for (int i = start; i < end; i++) { + int x = getNibbleFromChar(str.charAt(i)); + curr <<= 4; + if (curr < 0) { + throw new NumberFormatException("long overflow"); + } + curr |= x; + } + return curr; + } + + private static final int NUM_ALPHA_DIFF = 'A' - '9' - 1; + private static final int LOWER_UPPER_DIFF = 'a' - 'A'; + + private static int getNibbleFromChar(final char c) + { + int x = c - '0'; + if (x > 9) { + x -= NUM_ALPHA_DIFF; // difference between '9' and 'A' + if (x > 15) { + x -= LOWER_UPPER_DIFF; // difference between 'a' and 'A' + } + if (x < 10) { + throw new IllegalArgumentException(c + " is not a valid character for an UUID string"); + } + } + + if (x < 0 || x > 15) { + throw new IllegalArgumentException(c + " is not a valid character for an UUID string"); + } + + return x; + } + // Field Accessor Methods /** @@ -372,19 +425,46 @@ * @return A string representation of this {@code UUID} */ public String toString() { - return (digits(mostSigBits >> 32, 8) + "-" + - digits(mostSigBits >> 16, 4) + "-" + - digits(mostSigBits, 4) + "-" + - digits(leastSigBits >> 48, 4) + "-" + - digits(leastSigBits, 12)); + return toString(getMostSignificantBits(), getLeastSignificantBits()); } - /** Returns val represented by the specified number of hex digits. */ - private static String digits(long val, int digits) { - long hi = 1L << (digits * 4); - return Long.toHexString(hi | (val & (hi - 1))).substring(1); + public static String toString(long msb, long lsb) { + char[] uuidChars = new char[36]; + + hexDigits(uuidChars, 0, 8, msb >> 32); + uuidChars[8] = '-'; + hexDigits(uuidChars, 9, 4, msb >> 16); + uuidChars[13] = '-'; + hexDigits(uuidChars, 14, 4, msb); + uuidChars[18] = '-'; + hexDigits(uuidChars, 19, 4, lsb >> 48); + uuidChars[23] = '-'; + hexDigits(uuidChars, 24, 12, lsb); + + return new String(uuidChars); } + private static void hexDigits(char[] dest, int offset, int digits, long val) { + long hi = 1L << (digits * 4); + toUnsignedString(dest, offset, digits, hi | (val & (hi - 1)), 4); + } + + private final static char[] HEX_DIGITS = { + '0' , '1' , '2' , '3' , '4' , '5' , + '6' , '7' , '8' , '9' , 'a' , 'b' , + 'c' , 'd' , 'e' , 'f' + }; + + private static void toUnsignedString(char[] dest, int offset, int len, long i, int shift) { + int charPos = len; + int radix = 1 << shift; + long mask = radix - 1; + do { + dest[offset + --charPos] = HEX_DIGITS[(int)(i & mask)]; + i >>>= shift; + } while (i != 0 && charPos > 0); + } + /** * Returns a hash code for this {@code UUID}. *

3 7

RFR: [jdk7u-dev] - 8003898: X11 toolkit can be chosen as the default toolkit
by Rob McKenna 25 Jan '13

25 Jan '13

Hi folks, This review contains: 8003898: X11 toolkit can be chosen as the default toolkit 7162111: TEST_BUG: change tests run in headless mode [macosx] (open) 8004928: TEST_BUG: Reduce dependence of CoreLib tests from the AWT subsystem Unfortunately the last two patches didn't apply cleanly, hence the review request. (the commit comments will be altered appropriately before integration) Webrev at: http://cr.openjdk.java.net/~robm/7162111/webrev.01/ <http://cr.openjdk.java.net/%7Erobm/7162111/webrev.01/> I've just submitted a test job so I'll integrate once I get a review and a clean bill of health from that. -Rob

5 8

Review Request : Java exe doesn't process args ending Back slash
by jayashree viswanathan 17 Jan '13

17 Jan '13

Hi All, Java.exe doesn't seems to process arguments ending with back slashes well , in windows only . I have added test scenario and changeset in the below webrev . http://cr.openjdk.java.net/~jviswana/7188114/webrev.01/ This seems to be introduced after the bug fix for 7188114 has be made into jdk8 . Thanks and Regards, Jayashree Viswanathan

2 5