August 2015 - core-libs-dev

JDK-8067661: transferTo proposal for Appendable
by Patrick Reinhart 15 Nov '17

15 Nov '17

Hi Chris & Pavel, Based on the transferTo Method on the InputStream I would propose to introduce a default method on the Readable interface. In that way the method can be used for all existing implementations of Readable and still be implemented in a special way by a individual implementer. /** * Reads all characters from this readable and writes the characters to * the given appendable in the order that they are read. On return, this * readable will be at end its data. * * This method may block indefinitely reading from the readable, or * writing to the appendable. The behavior for the case where the readable * and/or appendable is asynchronously closed, or the thread * interrupted during the transfer, is highly readable and appendable * specific, and therefore not specified. * * If an I/O error occurs reading from the readable or writing to the * appendable, then it may do so after some characters have been read or * written. Consequently the readable may not be at end of its data and * one, or both participants may be in an inconsistent state. It is strongly * recommended that both readable and appendable be promptly closed * if needed and an I/O error occurs. * * @param out the appendable, non-null * @return the number of characters transferred * @throws IOException if an I/O error occurs when reading or writing * @throws NullPointerException if {@code out} is {@code null} * * @since 1.9 */ default long transferTo(Appendable out) throws IOException { .... } -Patrick

5 26

ISO-8859-16 charset/decoder/encoder
by Charles Oliver Nutter 25 Aug '17

25 Aug '17

Again, apologies if this is not the right list. OpenJDK does not currently contain support for encoding/decoding ISO-8859-16. A JRuby user recently reported that they needed this encoding. So, I implemented it. Here's a link to the charset/decoder/encoder in JRuby's repository: https://github.com/jruby/jruby/blob/master/core/src/main/java/org/jruby/uti… I tried to follow the general form of the other ISO-8859 charsets, but there's probably more reuse possible (I believe they use sun.nio.cs classes I can't access). Happy to contribute this. Unsure of the process. - Charlie

4 5

[8u40] RFR 6642881: Improve performance of Class.getClassLoader()
by Coleen Phillimore 30 Jul '16

30 Jul '16

Summary: Add classLoader to java/lang/Class instance for fast access This is a backport request for 8u40. This change has been in the jdk9 code for 3 months without any problems. The JDK changes hg imported cleanly. The Hotspot change needed a hand merge for create_mirror call in klass.cpp. http://cr.openjdk.java.net/~coleenp/6642881_8u40_jdk/ http://cr.openjdk.java.net/~coleenp/6642881_8u40_hotspot/ bug link https://bugs.openjdk.java.net/browse/JDK-6642881 Ran jdk_core jtreg tests in jdk with both jdk/hotspot changes. Also ran jck java_lang tests with only the hotspot change. The hotspot change can be tested separately from the jdk change (but not the other way around). Thanks, Coleen

4 8

RFR: JDK-8044629: (reflect) Constructor.getAnnotatedReceiverType() returns wrong value
by Joel Borggrén-Franck 26 Jul '16

26 Jul '16

Hi, Can I get a review for this fix and javadoc clarification for https://bugs.openjdk.java.net/browse/JDK-8044629 The problem is with potentially annotated receiver parameters, they only exist for inner class constructors, so this fix makes sure that a ctor is for an inner class or returns null (as for a static method) otherwise. CCC has been approved. Webrev: http://cr.openjdk.java.net/~jfranck/8044629/webrev.00/ cheers /Joel

5 11

Re: Analysis on JDK-8022321 java/lang/ref/OOMEInReferenceHandler.java fails intermittently
by David Holmes 24 Jun '16

24 Jun '16

Hi Kalyan, This is not a hotspot issue so I'm moving this to core-libs, please drop hotspot from any replies. On 20/12/2013 6:26 AM, srikalyan wrote: > Hi all, I have been working on the bug JDK-8022321 > <https://bugs.openjdk.java.net/browse/JDK-8022321> , this is a sporadic > failure and the webrev is available here > http://cr.openjdk.java.net/~srikchan/Regression/JDK-8022321_OOMEInReference… I'm really not sure what to make of this. We have a test that triggers an out-of-memory condition but the OOME can actually turn up in the ReferenceHandler thread causing it to terminate and the test to fail. We previously accounted for the non-obvious occurrences of OOME due to the Object.wait and the possible need to load the InterruptedException class - but still the OOME can appear where we don't want it. So finally you have just placed the whole for(;;) loop in a try/catch(OOME) that ignores the OOME. I'm certain that makes the test happy, but I'm not sure it is really what we want for the ReferenceHandler thread. If the OOME occurs while cleaning, or enqueuing then we will fail to clean and/or enqueue but there would be no indication that has occurred and I think that is a bigger problem than this test failing. There may be no way to make this test 100% reliable. In fact I'd suggest that no memory exhaustion test can be 100% reliable. David > * > **"Root Cause:Still not known"* > 2 places where there is a possibility for OOME > 1) Cleaner.clean() > 2) ReferenceQueue.enqueue() > > 1) The cleanup code in turn has 2 places where there is potential for > throwing OOME, > a) thunk Thread which is run from clean() method. This Runnable is > passed to Cleaner and appears in the following classes > java/nio/DirectByteBuffer.java > sun/misc/Perf.java > sun/nio/fs/NativeBuffer.java > sun/nio/ch/IOVecWrapper.java > sun/misc/Cleaner/ExitOnThrow.java > However none of the above overridden implementations ever create an > object in the clean() code. > b) new PrivilegedAction created in try catch Exception block of > clean() method but for this object to be created and to be held > responsible for OOME an Exception(other than OOME) has to be thrown. > > 2) No new heap objects are created in the enqueue method nor anywhere in > the deep call stack (VM.addFinalRefCount() etc) so this cannot be a > potential cause. > > *Experimental change to java.lang.Reference.java* : > - Put one more guard (try catch with OOME block) in the Reference > Handler Thread which may give the Reference Handler a chance to cleanup. > This is fixing the test failure (several 1000 runs with 0 failures) > - Without the above change the test fails atleast 3-5 times for every > 1000 run. > > *PS*: The code change is to a very critical part of JDK and i am fully > not aware of the consequences of the change, hence seeking expert help > here. Appreciate your time and inputs towards this. >

10 95

RFR 8029891 : Deadlock detected in java/lang/ClassLoader/deadlock/GetResource.java
by Brent Christian 18 May '16

18 May '16

Hi, Please review this fix, courtesy of Peter Levart (thanks!), that I would like to get in. https://bugs.openjdk.java.net/browse/JDK-8029891 http://cr.openjdk.java.net/~bchristi/8029891/webrev.0/ There is some discussion of it in the bug report, starting at 2014-12-31. The problem, as stated by Mandy: "System Properties is a hashtable that synchronizes on itself for any access. Currently System.getProperties returns the Properties instance accessed by the system in which any application code might synchronize on it (that's what the test is doing). The problem reported JDK-6977738 is about Properties.store method that was fixed not to synchronize on this instance. System property is a common way for changing the default setting and so it's impractical to expect the class loading code path not to call System.getProperty." This fix changes java.util.Properties to store its values in an internal ConcurrentHashMap, ignoring its Hashtable heritage. In this way, Properties can be "de-sychronized": all methods inherited from Hashtable are overridden, to remove synchronization, and delegate to the internal CHM. The serialized form is unchanged. An alternative approach considered would be for System.getProperties() to return a duplicate snapshot of the current Properties. This presents a compatibility risk to existing code that keeps a reference to the return value of System.getProperties() and expects to either read new properties added afterwards, or set properties on the cached copy. -Brent

7 41

RFR: 8079136: Accessing a nested sublist leads to StackOverflowError
by Ivan Gerasimov 31 Mar '16

31 Mar '16

Hello! When creating a sublist with List.subList(), it keeps a reference to its parent. Then, when accessing (get(), set(), add(), remove(), etc.) the sublist, it recursively calls the corresponding methods of its parent. This recursion, when deep enough, can cause StackOverflowError. The only reason to do things recursively here, is the need to update modCount and size of all the parents. So, the proposal is to update these fields in a loop. A few cleanups were done along the way. Would you please help review the fix? BUGURL: https://bugs.openjdk.java.net/browse/JDK-8079136 WEBREV: http://cr.openjdk.java.net/~igerasim/8079136/0/webrev/ Sincerely yours, Ivan

9 45

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 ] or [ = 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

RFR 8124977 cmdline encoding challenges on Windows
by Kirk Shoop (MS OPEN TECH) 24 Feb '16

24 Feb '16

Hi, Issue: https://bugs.openjdk.java.net/browse/JDK-8124977 Webrev: http://cr.openjdk.java.net/~kshoop/8124977/ This webrev intends to address interaction between Windows console and java apps. Two switches were added that change the behavior of the launcher. The defaults do not change the launcher behavior. -Dwindows.UnicodeConsole=true - switches on Unicode support in the Windows console. This optional switch causes the launcher to call GetCommandLineW() and parse the arguments in unicode. It also modifies how the codepage for console output is selected. -Dfile.encoding.unicode="UTF-8" - identifies Unicode charset to use; If not specified, UTF-8 is used by default. Ignored when windows.UnicodeConsole is not set to true. When the first switch is used, this optional switch allows the codepage for console output to be controlled. I would like to get feedback on the approach here and any additional work that is required solve these particular Unicode issues on Windows. Kirk

10 32

RFR: 8129957 - Deadlock in JNDI LDAP implementation when closing the LDAP context
by Rob McKenna 17 Sep '15

17 Sep '15

Hi folks, We have a hang between LdapClient / Ctx due to the fact that Connection.cleanup() calls LdapClient.processConnectionClosure which locks the unsolicited vector and in turn calls LdapCtx.fireUnsolicited which locks the eventSupport object. Unfortunately when an LdapCtx.close() occurs at the same time, its removeUnsolicited method locks the eventSupport object first and then attempts to call LdapClient.removeUnsolicited which attempts to lock the unsolicited vector. So: thread 1: Connection.cleanup -> LdapClient.processConnectionClosure (LOCK VECTOR) -> LdapCtx.fireUnsolicited (LOCK EVENTSUPPORT) (LdapClient is looping through LdapCtx objects in the unsolicited vector) thread 2: LdapCtx.close (LOCK LDAPCTX) -> LdapCtx.removeUnsolicited (LOCK EVENTSUPPORT) -> LdapClient.removeUnsolicited (LOCK VECTOR) (A single LdapCtx removes itself from its LdapClient unsolicited list) My proposed solution is to have both threads lock the LdapClient before locking either the unsolicited vector or the eventSupport object. Webrev at: http://cr.openjdk.java.net/~robm/8129957/webrev.01/ -Rob

2 2