December 2010 - 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

Are the faster versions of HashMap and BigInteger going into jdk7?
by Paulo Levi 03 Sep '11

03 Sep '11

Just a question.

8 12

Request for approval: Bug 100057 - Potential stack corruption in GetJavaProperties
by Andrew Haley 18 May '11

18 May '11

https://bugs.openjdk.java.net/show_bug.cgi?id=100057 GetJavaProperties has a stack-allocated fixed size buffer for holding a copy of a string returned by setlocale(3). However, there is no guarantee that the string will fit into this buffer. This one is probably due to Solaris code being reused for Linux. The patch has been in IcedTea for a long while. OK to push, OpenJDK 7 and 6? Andrew. --- oldopenjdk6/jdk/src/solaris/native/java/lang/java_props_md.c 2008-08-28 04:15:51.000000000 -0400 +++ openjdk/jdk/src/solaris/native/java/lang/java_props_md.c 2008-09-15 10:37:26.000000000 -0400 @@ -211,7 +211,9 @@ * <language name>_<country name>.<encoding name>@<variant name> * <country name>, <encoding name>, and <variant name> are optional. */ - char temp[64]; + char * temp; + temp = (char*) malloc(strlen(lc)+1); + char *language = NULL, *country = NULL, *variant = NULL, *encoding = NULL; char *std_language = NULL, *std_country = NULL, *std_variant = NULL, @@ -323,6 +325,9 @@ /* return same result nl_langinfo would return for en_UK, * in order to use optimizations. */ std_encoding = (*p != '\0') ? p : "ISO8859-1"; + + /* Free temp */ + free(temp); #ifdef __linux__

6 17

Sunbug 6934356: Vector.writeObject() synchronization risks serialization deadlock
by Neil Richards 14 Feb '11

14 Feb '11

Hello. I have a fix and testcase for problem 6934356 in the Java bug database - "Vector.writeObject() synchronization risks serialization deadlock". I've included the 'hg diff -g' output below. I'm new to OpenJDK - though not to Java SE implementation development - so hope that this is correct mailing list to ask for the code to be reviewed. (Please point me towards a better list if this is not so). Also, given that this is a reported bug in the Java bug database, I'm a little confused as to whether I need to additionally raise it in https://bugs.openjdk.java.net/ And, indeed, whether it is better for me to include the 'hg diff -g' output inline, as I have done below, or as an attachment, or in some other fashion. Basically, any guidance will be gratefully received :-) Thanks, Neil -- Unless stated above: IBM United Kingdom Limited - Registered in England and Wales with number 741598. Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU -- diff --git a/src/share/classes/java/util/Vector.java b/src/share/classes/java/util/Vector.java --- a/src/share/classes/java/util/Vector.java +++ b/src/share/classes/java/util/Vector.java @@ -1053,10 +1053,20 @@ * is, serialize it). This method is present merely for synchronization. * It just calls the default writeObject method. */ - private synchronized void writeObject(java.io.ObjectOutputStream s) + private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { - s.defaultWriteObject(); + final java.io.ObjectOutputStream.PutField fields = s.putFields(); + Object[] data = null; + synchronized (this) { + fields.put("capacityIncrement", capacityIncrement); + fields.put("elementCount", elementCount); + final int dataLength = elementData.length; + data = new Object[dataLength]; + System.arraycopy(elementData, 0, data, 0, dataLength); + } + fields.put("elementData", data); + s.writeFields(); } /** diff --git a/test/java/util/Vector/SerializationDeadlock.java b/test/java/util/Vector/SerializationDeadlock.java new file mode 100644 --- /dev/null +++ b/test/java/util/Vector/SerializationDeadlock.java @@ -0,0 +1,111 @@ +/* + * @test + * @bug 6934356 + * @summary Serializing Vector objects which refer to each other should not be able to deadlock. + * @author Neil Richards <neil.richards(a)ngmr.net> + */ + +import java.io.ByteArrayOutputStream; +import java.io.IOException; +import java.io.ObjectOutputStream; +import java.io.Serializable; +import java.util.ArrayList; +import java.util.Vector; +import java.util.concurrent.CyclicBarrier; +import java.util.concurrent.TimeoutException; +import java.util.concurrent.TimeUnit; + +public class SerializationDeadlock { + public static void main(final String[] args) { + // Test for Vector serialization deadlock + final Vector<Object> v1 = new Vector<Object>(); + final Vector<Object> v2 = new Vector<Object>(); + final TestBarrier testStart = new TestBarrier(3); + + v1.add(testStart); + v1.add(v2); + v2.add(testStart); + v2.add(v1); + + final CyclicBarrier testEnd = new CyclicBarrier(3); + final TestThread t1 = new TestThread(v1, testEnd); + final TestThread t2 = new TestThread(v2, testEnd); + + t1.start(); + t2.start(); + + try { + testStart.await(); + testEnd.await(1, TimeUnit.SECONDS); + } catch (TimeoutException te) { + throw new RuntimeException("Test FAILED: Probable serialization deadlock detected"); + } catch (Exception e) { + throw new RuntimeException("Test ERROR: Unexpected exception caught", e); + } + + TestThread.handleExceptions(); + } + + static final class TestBarrier extends CyclicBarrier + implements Serializable { + public TestBarrier(final int count) { + super(count); + } + + private void writeObject(final ObjectOutputStream oos) + throws IOException { + oos.defaultWriteObject(); + // Wait until all TestThreads have started serializing data + try { + await(); + } catch (final Exception e) { + throw new IOException("Test ERROR: Unexpected exception caught", e); + } + } + } + + static final class TestThread extends Thread { + private static final ArrayList<Exception> exceptions = new ArrayList<Exception>(); + + private final Vector vector; + private final CyclicBarrier testEnd; + + public TestThread(final Vector vector, final CyclicBarrier testEnd) { + this.vector = vector; + this.testEnd = testEnd; + setDaemon(true); + } + + public void run() { + try { + final ByteArrayOutputStream baos = new ByteArrayOutputStream(); + final ObjectOutputStream oos = new ObjectOutputStream(baos); + + oos.writeObject(vector); + oos.close(); + } catch (final IOException ioe) { + addException(ioe); + } finally { + try { + testEnd.await(); + } catch (Exception e) { + addException(e); + } + } + } + + private static synchronized void addException(final Exception exception) { + exceptions.add(exception); + } + + public static synchronized void handleExceptions() { + if (false == exceptions.isEmpty()) { + for (Exception exception : exceptions) { + exception.printStackTrace(); + } + throw new RuntimeException("Test ERROR: Unexpected exceptions thrown on test threads - see stderr for details"); + } + } + } +} +

9 29

Review request for 6927486: Deadlock in legacy Hashtable writeObject()
by Neil Richards 11 Feb '11

11 Feb '11

Please find attached a changeset to address the problem reported in bug 6927486, "Deadlock in legacy Hashtable writeObject()". The problem reported is similar to one found in java.util.Vector, for which a fix is also currently under review (http://mail.openjdk.java.net/pipermail/core-libs-dev/2010-December/005529.h…) This fixes approach is similar to that in Vector - namely to record the objects to be serialized within the synchronization in Hashtable.writeObject(), so that the calls to writeObject() in that method can be moved to beyond the synchronization, thus avoiding the possibility of deadlock. (The calls to writeObject() - for the keys and value of the hashtable's entries - are the last activity within Hashtable.writeObject(), so no additional calls need be delayed). The keys and values to be written out are recorded in a stack of Entry objects, created specially for the task to form a local single-linked list of entries, which is then traversed outside the synchronized block to make the calls to s.writeObject() with each entry's key and value. I believe this is the most efficient means of addressing the problem - any suggestions on how to further improve it gratefully received. As the order of writing out the entries has effectively changed from FIFO to LIFO (as it uses a stack), I have reversed the order the code traverses the table (from low index to high). (I note that the API doc explicitly gives no guarantees as to the order the entries are serialized. Nevertheless, as the initial traversal order was the more uncommon of the two forms, I suspect that there might be some deeper reasoning as to why it was done that way, hence why I've tried to retain its spirit). Any reviews or comment gratefully received, Thanks, Neil PS: The evaluation of this bug suggests that java.util.Random and java.util.PropertyPermission may also be susceptible to serialization deadlock (ie. in addition to Vector and Hashtable). I do not believe this to be case: whilst their writeObject() methods are synchronized, neither class needs to call ObjectOutputStream.writeObject() within them, so the possibility of deadlock there cannot arise. PPS: I notice the API javadoc for PropertyPermission does not give its serialized form (and the "See Also:" section), even though it is Serializable, which strikes me as unusual. I suppose it has no serializable fields of its own (over that which BasicPermission has), but I'm sure I've seen other serializable classes with no fields having "serialized form" entries. -- Unless stated above: IBM email: neil_richards at uk.ibm.com IBM United Kingdom Limited - Registered in England and Wales with number 741598. Registered office: PO Box 41, North Harbour, Portsmouth, Hampshire PO6 3AU

4 10

Code Review 7000511: PrintStream, PrintWriter, Formatter leave files open when exception thrown
by Chris Hegarty 06 Jan '11

06 Jan '11

Failing java.io.PrintStream, java.io.PrintWriter, java.util.Scanner, and java.util.Formatter multi-arg constructors that take a java.io.File or String filename (as well as one or more additional args) opens a FileIn/OutputStream to the given File/filename. If one of the other given args causes the constructor to fail ( null or unsupported charset for example ) the FileIn/OutputStream is never closed, and the application does not have a reference to it. You rely on the finalizer to close the stream. This is most serious on Windows because you cannot remove a file if there is an open handle to it. I also cleaned up an existing regression test that fails in samevm mode (partly) because of this. And removed another excluded test from the list since its bug was fixed some time ago. Webrev: http://cr.openjdk.java.net/~chegar/7000511/webrev.00/webrev/ -Chris.

4 12

Review for CR 6728865 : Improved heuristics for Collections.disjoint() [updated]
by Mike Duigou 04 Jan '11

04 Jan '11

I have updated the webrev for CR 6728865 with Rémi's feedback. The new webrev is at: http://cr.openjdk.java.net/~mduigou/6728865.1/webrev/ The size() comparisons are now done only when both c1 and c2 are not sets and I have removed the isEmpty() micro-optimization. Mike

7 31

hg: jdk7/tl/jdk: 2 new changesets
by valerie.peng＠oracle.com 28 Dec '10

28 Dec '10

Changeset: adff75ebdc00 Author: valeriep Date: 2010-12-22 19:19 -0800 URL: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/adff75ebdc00 6924489: sun.security.pkcs11.wrapper.PKCS11Exception: CKR_OPERATION_NOT_INITIALIZED Summary: Reset cipher state to un-initialized wherever necessary. Reviewed-by: weijun ! src/share/classes/sun/security/pkcs11/P11Cipher.java Changeset: 3254c3ae63fe Author: valeriep Date: 2010-12-27 11:39 -0800 URL: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/3254c3ae63fe Merge - src/share/classes/java/dyn/BootstrapMethod.java - src/share/classes/java/dyn/LinkagePermission.java - src/share/classes/java/dyn/MethodHandleProvider.java - src/share/classes/sun/dyn/JavaMethodHandle.java - src/share/native/sun/font/layout/HebrewLigatureData.cpp - src/share/native/sun/font/layout/HebrewShaping.cpp - src/share/native/sun/font/layout/HebrewShaping.h - test/java/dyn/JavaDocExamples.java

1 0

hg: jdk7/tl/jdk: 7005984: 3/3 Incorrect values of S0C and S0CMX appear with -gcnewcapacity in jstat
by daniel.daugherty＠oracle.com 24 Dec '10

24 Dec '10

Changeset: 3c4afaacd345 Author: dcubed Date: 2010-12-23 23:10 -0800 URL: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/3c4afaacd345 7005984: 3/3 Incorrect values of S0C and S0CMX appear with -gcnewcapacity in jstat Summary: Swap S0C and S0CMX column values. Reviewed-by: ohair, dholmes, poonam ! src/share/classes/sun/tools/jstat/resources/jstat_options ! test/sun/tools/jstat/gcNewCapacityOutput1.awk

1 0

hg: jdk7/tl/jdk: 7002386: (launcher) fix XshowSettings
by kumar.x.srinivasan＠oracle.com 23 Dec '10

23 Dec '10

Changeset: 5beec82bf20d Author: ksrini Date: 2010-12-23 13:51 -0800 URL: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/5beec82bf20d 7002386: (launcher) fix XshowSettings Reviewed-by: darcy, mchung, naoto ! src/share/bin/java.c ! src/share/classes/sun/launcher/LauncherHelper.java ! test/tools/launcher/Settings.java

1 0