April 2011 - 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

A method with return type size_t returns negative value
by Jing LV 29 Nov '11

29 Nov '11

Hello, I found a problem in windows/native/java/io/io_util_md.c, method handleRead(). The return type of the method is size_t, which is defined as unsigned int. However we see the method would return negative values while it meets some error. This may be a problem as the API comsumer and later developer may have misunderstand it. I suggest modify it to ssize_t (or SSIZE_T as it is on windows). Any comments? -- Best Regards, Jimmy, Jing LV

5 21

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

Review request for 7020513 : Add com.sun.xml.internal to the "package.access" property in java.security
by Rama Pulavarthi 29 Aug '11

29 Aug '11

Hi, Need reviewer for CR 7020513: Add com.sun.xml.internal to the "package.access" property in $JAVA_HOME/lib/security/java.security Webrev is available at http://cr.openjdk.java.net/~ohair/openjdk7/jdk7-tl-jaxws-7020513/webrev/ thanks, Rama Pulavarthi

6 12

BufferedOutputStream does not throw exception after it's closed
by Jing LV 25 Jul '11

25 Jul '11

Hello, Find a similar problem with the one in the last mail(BufferedWriter), this time is BufferedOutputStream, and it has a delegated output stream and behave the same with BufferedWriter, I believe the two problems are just the same - it needs to check the open status before store the contents even if it does not need to flush. A similar testcase can be: private int bufferSize = 1024; public void test() throws Exception { OutputStream out = new BufferedOutputStream(new ClosableByteArrayOutputStream(), bufferSize); out.close(); try { out.write(new byte[] { 7, 3, 4, 5 }); fail("expected already closed exception"); } catch (IOException expected) { } } private static class ClosableByteArrayOutputStream extends OutputStream { private final ByteArrayOutputStream bytesOut = new ByteArrayOutputStream(); private boolean closed = false; @Override public void close() throws IOException { closed = true; } @Override public void write(int oneByte) throws IOException { if (closed) { throw new IOException(); } bytesOut.write(oneByte); } } Any comments? I'd like to raise this problem on the bug-tracker system.

4 6

Unreachable catch classes
by Joe Darcy 26 May '11

26 May '11

Hello. FYI, javac in JDK 7 does a more precise analysis than before on what catch blocks can actually be reached and warnings are issued for unreachable catch blocks. I've extracted those warnings from a recent full JDK build in case anyone wants to update the code in question. -Joe ../../../../../../src/share/classes/com/sun/corba/se/impl/protocol/BootstrapServerRequestDispatcher.java:124: warning: unreachable catch clause } catch (java.lang.Exception ex) { ^ thrown type RuntimeException has already been caught ../../../../../../src/share/classes/com/sun/corba/se/impl/protocol/BootstrapServerRequestDispatcher.java:124: warning: unreachable catch clause } catch (java.lang.Exception ex) { ^ thrown type RuntimeException has already been caught ../../../src/share/classes/java/util/concurrent/ThreadPoolExecutor.java:1115: warning: unreachable catch clause } catch (Throwable x) { ^ thrown types RuntimeException,Error have already been caught ../../../src/share/classes/java/net/DatagramSocket.java:183: warning: unreachable catch clause } catch(IOException e) { ^ thrown type SocketException has already been caught Note: Some input files use or override a deprecated API. Note: Recompile with -Xlint:deprecation for details. Note: Some input files use unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. 2 warnings ../../../src/share/classes/java/security/cert/X509CertSelector.java:2217: warning: unreachable catch clause } catch (CertificateException e3) { ^ thrown types CertificateNotYetValidException,CertificateExpiredException have already been caught ../../../src/share/classes/javax/management/modelmbean/RequiredModelMBean.java:1220: warning: unreachable catch clause } catch (Exception e) { ^ thrown types InvocationTargetException,IllegalAccessException,RuntimeException have already been caught 1 warning ../../../../src/share/classes/sun/security/rsa/RSASignature.java:205: warning: unreachable catch clause } catch (GeneralSecurityException e) { ^ thrown type BadPaddingException has already been caught

6 15

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

proposal to optimise the performance of the Jar utility
by mike.skells＠talk21.com 12 May '11

12 May '11

Hi, Not sure if this is too late for Java 7 but I have made some optimisations for a client to improve the performance of the jar utility in their environment, and would like to promite then into the main code base The optimisations that I have performed are 1. Allowing the Jar utility to have other compression levels (currently it allows default (5) only) 2. Multi-threading, and pipelining the the file information and access 3. multi-threading the compression and file writing A little background A part of the development process of where I work they regularly Jar the content of the working projects as part of the distribution to remote systems. This is a large and complex code base of 6 million LOC and growing. The Jar file ends up compressed to approx 100Mb, Uncompressed the jar size is approx 245mb, about 4-5 times the size of rt.jar. I was looking at ways to improve the performance as this activity occurs several times a day for dozens of developers In essence when compressing a new jar file the jar utility is single threaded and staged. Forgive me if this is an oversimplification first it works out all of the files that are specified, buffering the file names, (IO bound) then it iterates through the files, and for each file, it load the file information, and then the file content sending it to a JarOutputStream, (CPU bound or IO bound depending on the IO speed) The JarOutputStream has a compression of 0 (just store) or 5 (the default), and the jar writing is single threaded by the design of the JarOutputStream The process of creation of a Jar took about 20 seconds in windows with the help of an SSD, and considerable longer without one, and was CPU bound to one CPU core ---- The changes that I made were 1. Allow deferent compression levels (for us a compression level of 1 increases the file size of the Jar to 110 Mb but reduces the CPU load in compression to approx 30% of what it was (rough estimate) 2. pipelining the file access 2.1 one thread is started for each file root (-C on the Jar command line), which scans for files and places the file information into a blocking queue(Q1), which I set to abretrary size of 200 items 2.2 one thread pool of 10 threads reads the file information from the queue (Q1) and buffers the file content to a specified size (again I specified an arbetrary size limit of 25K for a file, and places the buffered content into a queue(q2) (again arbetrary size of 10 items 2.3 one thread takes the filecontent from Q2 and compresses it or checksums it and adds it the the JarOutputStream. This process is single threaded due to the design of the JarOutputStream some other minor performance gain occurred by increasing the buffer on the output stream to reduce the IO load The end result is that the process takes about approx 5 seconds in the same configuration The above is in use in production configuration for a few months now As a home project I have completed some enhancements to the JarOutputStream, and produced a JarWriter that allows multiple threads to work concurrently deflating or calculating checksums, which seems to test OK for the test cases that Ihave generated,and successfully loads my quad core home dev machine on all cores. Each thread allocates a buffer, and the thread compresses a files into the buffer, only blocking other threads whenthe buffer is written to the output (which is after the compression is complete, unless the file is too large to compress This JarWriter is not API compatable with the JarOutputStream, it is not a stream. It allows the programmer to write a record based of the file information and an input stream, and is threadsafe. It is not a drop in replacement for JarOutputStream I am not an expert in the ZIp file format, but much of the code from ZipOutputStream is unchanged, just restructured --- I did think that there is some scope for improvement, that I have not looked at a. thresholding of file size for compression (very small files dont compress well b. some file types dont compress well (e.g. png, jpeg) as they have been compressed already) c. using NIO to parallelise the loading of the file information or content d. some pre-charging of the deflator dictionary (e.g. a class file contains the strings of the class name and packages), but this would make the format incompatable with zip, and require changes to the JVM to be useful, and is a long way from my comform zone, or skill set. This would reduce the file size -- What is the view of the readers. Is this something, or at least some parts of this that could be incorperated into Java 7 or is this too late on the dev cycle regards Mike

4 14

Codereview request: CR 7040220 java/char_encodin Optimize UTF-8 charset for String.getBytes()/toCharArray()
by Xueming Shen 02 May '11

02 May '11

Hi This is motivated by Neil's request to optimize common-case UTF8 path for native ZipFile.getEntry calls [1]. As I said in my replying email [2] I believe a better approach might be to "patch" UTF8 charset directly to implement sun.nio.cs.ArrayDecoder/Encoder interface to speed up the coding operation for array based encoding/decoding under certain circumstance, as we did for all single byte charsets in #6636323 [3]. I have a old blog [4] that has some data for this optimization. The original plan was to do the same thing for our new UTF8 [5] as well in JDK7, but then (excuse, excuse) I was just too busy to come back to this topic till 2 days ago. After two days of small tweaking here and there and testing those possible corner cases I can think of, I'm happy with the result and think it might be worth sending it out for a codereview for JDK7, knowing we only have couple days left. The webrev is at http://cr.openjdk.java.net/~sherman/7040220/webrev Those tests are supposed to make sure the coding result from the new paths for String.getBytes()/ toCharArray() matches the result from the existing implementation. The performance results of running StrCodingBenchmarkUTF8 (included in webrev) on my linux box in -client and -server mode respectively are included at http://cr.openjdk.java.net/~sherman/7040220/client http://cr.openjdk.java.net/~sherman/7040220/server The microbenchmark measures 1-byte, 2-byte, 3-byte and 4 bytes utf8 bits separately with different length of data (from 12 bytes to thousands) Thanks! -Sherman [1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-April/006710.html [2] http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-April/006726.html [3] http://cr.openjdk.java.net/~sherman/6636323_6636319/webrev [4] http://blogs.sun.com/xuemingshen/entry/faster_new_string_bytes_cs [5] http://blogs.sun.com/xuemingshen/entry/the_big_overhaul_of_java

4 13

hg: jdk7/tl/langtools: 7039931: Project Coin: diamond inference fail with generic constructor explicit type-arguments
by maurizio.cimadamore＠oracle.com 30 Apr '11

30 Apr '11

Changeset: 4caf17560ae0 Author: mcimadamore Date: 2011-04-30 11:57 +0100 URL: http://hg.openjdk.java.net/jdk7/tl/langtools/rev/4caf17560ae0 7039931: Project Coin: diamond inference fail with generic constructor explicit type-arguments Summary: diamond should be disallowed in cases where explicit generic constructor parameters are specified Reviewed-by: jjg ! src/share/classes/com/sun/tools/javac/comp/Check.java ! src/share/classes/com/sun/tools/javac/resources/compiler.properties + test/tools/javac/diags/examples/DiamondAndExplicitParams.java ! test/tools/javac/generics/diamond/7030150/GenericConstructorAndDiamondTest.java - test/tools/javac/generics/diamond/7030150/Neg01.java - test/tools/javac/generics/diamond/7030150/Neg01.out - test/tools/javac/generics/diamond/7030150/Neg02.java - test/tools/javac/generics/diamond/7030150/Neg02.out - test/tools/javac/generics/diamond/7030150/Neg03.java - test/tools/javac/generics/diamond/7030150/Neg03.out - test/tools/javac/generics/diamond/7030150/Pos01.java - test/tools/javac/generics/diamond/7030150/Pos02.java

1 0