April 2008 - core-libs-dev

Re: [PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger
by Alan Eliasen 06 Jun '09

06 Jun '09

Anonymous member wrote: > Out of curiousity, how does the Java implementation compare to GMP in > terms of speed? (Note: These numbers apply to the *revised* patch that I'll be posting in a few minutes.) It depends on the size of the numbers. When I run the regression tests that I wrote, my updated Java version runs in about 2 minutes. When I run the same regression test in Kaffe using GMP, it takes about 2 *hours*. (Some of the same tests using Java 1.6 take many, many hours without my optimizations for the pow() function). But those are a lot of small numbers. There is a lot of overhead in converting from Java to C types and back, and in Kaffe's relative slowness. And currently, only multiply() has been improved in my Java patches that I've submitted. Kaffe is about 25 times slower on the average program anyway. When you run Kaffe/GMP for very large numbers, Kaffe/GMP starts being very much faster. OpenJDK still can't compete for numbers that are on the cutting edge of number theory. But we'll be much better than we were before. If I were to write the same code in pure C using GMP, then GMP would be much faster. But I haven't done that. So it's hard to compare GMP to Java exactly. But some numbers. For multiplying the numbers 3^1000000 * 3^1000001, (with my fixes to do the exponentiation hundreds of thousands of times faster factored out; without these, JDK 1.6 would be thousands of times slower,) the times for 20 iterations are: JDK 1.6 OpenJDK1.7 with my patches Kaffe w/GMP 292987 ms 28650 ms 866 ms Thus, for numbers of this size, my algorithms are more than 10 times faster than JDK 1.6, but 33 times slower than Kaffe/GMP. For multiplying the somewhat special form 2^1000000 * 2^1000001, (the arguments of this in binary are a 1 followed by a million zeroes) JDK 1.6 OpenJDK1.7 with my patches Kaffe w/GMP 117298 ms 386 ms 474 ms So, my algorithm is 303 times faster than JDK, and just slightly faster than Kaffe/GMP. For multiplying numbers 3^14000000 * 3^14000001, the time for 1 iteration is: JDK 1.6 OpenJDK1.7 with my patches Kaffe w/GMP 3499115 ms 89505 ms 910 ms Thus, for numbers of this size, my patches make it 38.9 times faster, but still 99 times slower than GMP. Sigh. Well, to be expected. If you work with large numbers, GMP becomes ridiculously faster. Kaffe with GMP becomes only slightly slower than pure GMP as the portion of time in Java gets small. GMP includes 3-way Toom-Cook multiplication, and the much faster FFT multiplication (which is O(n)) for very large numbers, and hand-crafted assembly language that uses 64-bit instructions and limbs on my 64-bit architecture (as opposed to the 32-bit ints used in BigInteger. Hopefully some day in the future, BigInteger will be rewritten to use longs internally instead of ints. Multiplying two 64-bit longs does 4 times as much work as multiplying two 32-bit ints, and will thus likely be significantly faster, especially on 64-bit architectures.) So GMP is still very much faster for very large numbers. It is also *much* faster in turning numbers into strings, and in exponentiation. The algorithms in BigInteger are horrible for pow() and toString(). See the following bugs: 4641897: BigInteger.toString() algorithm slow for large numbers http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897 4646474: BigInteger.pow() algorithm slow in 1.4.0 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474 I have several fixes for both of these. My JVM-based programming language Frink ( http://futureboy.us/frinkdocs/ ) implements many of these improvements, and is much faster for a variety of arguments. I just need to finish improving these for a variety of different arguments, and considering the threading and memory-size-vs-speed tradeoffs in implementing toString efficiently. -- Alan Eliasen | "Furious activity is no substitute eliasen(a)mindspring.com | for understanding." http://futureboy.us/ | --H.H. Williams

4 8

hg: jdk7/tl/jdk: 6690122: Provide a mechanism for specifying Java-level USDT-like dtrace probes
by keith.mcguigan＠sun.com 08 May '08

08 May '08

Changeset: 2bfddc119eea Author: kamg Date: 2008-04-17 22:00 -0400 URL: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/2bfddc119eea 6690122: Provide a mechanism for specifying Java-level USDT-like dtrace probes Summary: Initial checkin of JSDT code Reviewed-by: sspitsyn, sbohne ! make/com/sun/Makefile + make/com/sun/tracing/Makefile + make/com/sun/tracing/dtrace/Makefile ! make/docs/Makefile ! make/docs/NON_CORE_PKGS.gmk ! make/sun/Makefile + make/sun/tracing/Makefile + make/sun/tracing/dtrace/Makefile + make/sun/tracing/dtrace/mapfile-vers + src/share/classes/com/sun/tracing/Probe.java + src/share/classes/com/sun/tracing/ProbeName.java + src/share/classes/com/sun/tracing/Provider.java + src/share/classes/com/sun/tracing/ProviderFactory.java + src/share/classes/com/sun/tracing/ProviderName.java + src/share/classes/com/sun/tracing/dtrace/ArgsAttributes.java + src/share/classes/com/sun/tracing/dtrace/Attributes.java + src/share/classes/com/sun/tracing/dtrace/DependencyClass.java + src/share/classes/com/sun/tracing/dtrace/FunctionAttributes.java + src/share/classes/com/sun/tracing/dtrace/FunctionName.java + src/share/classes/com/sun/tracing/dtrace/ModuleAttributes.java + src/share/classes/com/sun/tracing/dtrace/ModuleName.java + src/share/classes/com/sun/tracing/dtrace/NameAttributes.java + src/share/classes/com/sun/tracing/dtrace/ProviderAttributes.java + src/share/classes/com/sun/tracing/dtrace/StabilityLevel.java + src/share/classes/com/sun/tracing/dtrace/package-info.java + src/share/classes/com/sun/tracing/package-info.java + src/share/classes/sun/tracing/MultiplexProviderFactory.java + src/share/classes/sun/tracing/NullProviderFactory.java + src/share/classes/sun/tracing/PrintStreamProviderFactory.java + src/share/classes/sun/tracing/ProbeSkeleton.java + src/share/classes/sun/tracing/ProviderSkeleton.java + src/share/classes/sun/tracing/dtrace/Activation.java + src/share/classes/sun/tracing/dtrace/DTraceProbe.java + src/share/classes/sun/tracing/dtrace/DTraceProvider.java + src/share/classes/sun/tracing/dtrace/DTraceProviderFactory.java + src/share/classes/sun/tracing/dtrace/JVM.java + src/share/classes/sun/tracing/package-info.java ! src/share/javavm/export/jvm.h + src/share/native/sun/tracing/dtrace/JVM.c + src/share/native/sun/tracing/dtrace/jvm_symbols.h + src/solaris/native/sun/tracing/dtrace/jvm_symbols_md.c + src/windows/native/sun/tracing/dtrace/jvm_symbols_md.c + test/com/sun/tracing/BasicFunctionality.java

3 2

hg: jdk7/tl/langtools: 6682380: Foreach loop with generics inside finally block crashes javac with -target 1.5
by maurizio.cimadamore＠sun.com 23 Apr '08

23 Apr '08

Changeset: ec29a1a284ca Author: mcimadamore Date: 2008-04-23 17:10 +0100 URL: http://hg.openjdk.java.net/jdk7/tl/langtools/rev/ec29a1a284ca 6682380: Foreach loop with generics inside finally block crashes javac with -target 1.5 Summary: A missing type-erasure in Lower.java causes the compiler to crash since JDK6 Reviewed-by: jjg ! src/share/classes/com/sun/tools/javac/comp/Lower.java + test/tools/javac/foreach/T6682380.java

1 0

hg: jdk7/tl/jdk: 6692027: Custom subclasses of QueryEval don't serialize
by eamonn.mcmanus＠sun.com 22 Apr '08

22 Apr '08

Changeset: 92ea0ac77d2f Author: emcmanus Date: 2008-04-22 18:58 +0200 URL: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/92ea0ac77d2f 6692027: Custom subclasses of QueryEval don't serialize Summary: Remove non-public superclass of QueryEval Reviewed-by: dfuchs ! src/share/classes/javax/management/AndQueryExp.java ! src/share/classes/javax/management/BetweenQueryExp.java ! src/share/classes/javax/management/BinaryRelQueryExp.java ! src/share/classes/javax/management/NotQueryExp.java ! src/share/classes/javax/management/ObjectName.java ! src/share/classes/javax/management/OrQueryExp.java ! src/share/classes/javax/management/Query.java ! src/share/classes/javax/management/QueryEval.java + test/javax/management/query/CustomQueryTest.java

1 0

sun.reflect.generics.*
by Rémi Forax 21 Apr '08

21 Apr '08

Hi all, Is someone knows why package sun.reflect.generics is so complex ? This package (and subpackage) it used to reify a generics signatures to a java.lang.reflect.Type tree. It creates a parser, parse the signature to create an AST, and use a visitor to create the tree. This package, contains in my opinion, lot of unecessary garbage. - It creates an AST even if the Type tree can be created in one pass. - A bunch of interfaces has only one implementation like Visitor. - Use a visitor even if there is only one operation. - Use lots of generics can be removed because only one instanciation is used. cheers, Rémi

2 1

hg: jdk7/tl/jdk: 6691494: doc build broken in tracingdocs
by keith.mcguigan＠sun.com 21 Apr '08

21 Apr '08

Changeset: 79b594e72df0 Author: kamg Date: 2008-04-21 11:24 -0400 URL: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/79b594e72df0 6691494: doc build broken in tracingdocs Summary: Wrong variable names in makefile Reviewed-by: tbell ! make/docs/Makefile

1 0

6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present
by Martin Buchholz 21 Apr '08

21 Apr '08

It's a little disconcerting to still keep finding basic correctness bugs in core Collections classes. Here's a fix (again demonstrating that the Mother Of All Collections Tests is not thorough enough): Review requested from Chris Hegarty, Doug Lea # HG changeset patch # User martin # Date 1208733844 25200 # Node ID fd80580439549ed34473cfa973f34d29f9efd7a6 # Parent 8513593a57f180641d06cf535f1647cb9160f9e0 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null value not present Reviewed-by: Contributed-by: Scott Blum <scottb(a)google.com> diff --git a/src/share/classes/java/util/IdentityHashMap.java b/src/share/classes/java/util/IdentityHashMap.java --- a/src/share/classes/java/util/IdentityHashMap.java +++ b/src/share/classes/java/util/IdentityHashMap.java @@ -188,7 +188,6 @@ public class IdentityHashMap<K,V> /** * Use NULL_KEY for key if it is null. */ - private static Object maskNull(Object key) { return (key == null ? NULL_KEY : key); } @@ -378,8 +377,8 @@ public class IdentityHashMap<K,V> */ public boolean containsValue(Object value) { Object[] tab = table; - for (int i = 1; i < tab.length; i+= 2) - if (tab[i] == value) + for (int i = 1; i < tab.length; i += 2) + if (tab[i] == value && tab[i - 1] != null) return true; return false; @@ -905,7 +904,6 @@ public class IdentityHashMap<K,V> * view the first time this view is requested. The view is stateless, * so there's no reason to create more than one. */ - private transient Set<Map.Entry<K,V>> entrySet = null; /** diff --git a/test/java/util/Collection/MOAT.java b/test/java/util/Collection/MOAT.java --- a/test/java/util/Collection/MOAT.java +++ b/test/java/util/Collection/MOAT.java @@ -25,7 +25,7 @@ * @test * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464 * 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753 - * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 + * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215 * @summary Run many tests on many Collection and Map implementations * @author Martin Buchholz */ @@ -247,6 +247,13 @@ public class MOAT { testEmptySet(m.keySet()); testEmptySet(m.entrySet()); testEmptyCollection(m.values()); + + try { check(! m.containsValue(null)); } + catch (NullPointerException _) { /* OK */ } + try { check(! m.containsKey(null)); } + catch (NullPointerException _) { /* OK */ } + check(! m.containsValue(1)); + check(! m.containsKey(1)); } private static void testImmutableMap(final Map<Integer,Integer> m) { Martin On Sun, Apr 20, 2008 at 3:07 AM, Alan Bateman <Alan.Bateman(a)sun.com> wrote: > Joshua Bloch wrote: > > > > > Folks, > > > > While we're at it, here's another Collections bug discovered recently by a > Googler (Scott Blum). The value of this expression should be false: > > > > new IdentityHashMap().containsValue(null) > > > > Unfortunately, it's true. Looking at the code for containsValue, it's > obvious what's wrong: > > > > /** > > * Tests whether the specified object reference is a value in this > identity > > * hash map. > > * > > * @param value value whose presence in this map is to be tested > > * @return <tt>true</tt> if this map maps one or more keys to the > > * specified object reference > > * @see #containsKey(Object) > > */ > > public boolean containsValue(Object value) { > > Object[] tab = table; > > for (int i = 1; i < tab.length; i+= 2) > > if (tab[i] == value) > > return true; > > > > return false; > > } > > > > Empty entries are masquerading as entries mapping to null. The fix is > easy: > > > > if (tab[i] == value) > > > > becomes: > > > > if (tab[i] == value && tab[i -1] != null) > > > > (Recall that the null key (but not value) is proxied by NULL_KEY.) > > > > Josh > > > > > I don't see this in the bug database so I've created the following so that > it doesn't get lost: > 6691215: (coll) IdentityHashMap.containsValue(null) returns true when null > value not present > > -Alan. >

3 3

TreeMap.navigableKeySet().descendingIterator() sequence ?
by charlie hunt 20 Apr '08

20 Apr '08

Been looking at TreeMap's implementation rather closely and observed something I don't understand. %-) TreeMap (as of JDK 6 and later) implements NavigableMap. NavigableMap requires an implementation of a navigableKeySet() method which returns a NavigableSet<K>. So, in TreeMap I see: public NavigableSet<K> navigableKeySet() Then, the NavigableSet interface has an Iterator<E> descendingIterator() and Iterator<E>iterator(). The former returns an iterator over the elements in descending order. The latter in ascending order. I also noticed in TreeMap, NavigableMap requires an implementation of a descendingKeySet(), i.e. public NavigableSet<K> descendingKeySet(). Again, the NavigableSet interface has an Iterator<E> descendingIterator() and iterator() as described above. When I populate a TreeMap with some dummy data, let's say I populate it with 15 Integer keys and String's representing those Integer keys as values, I observe something I don't understand when using the navigableKeySet().descendingIterator(). When, I try to iterate over the returned NavigableKeySet, I see the lowest key printed and that's it. Nothing else prints. From looking at the JavaDoc for TreeMap and NavigableSet, this doesn't seem right. Shouldn't it iterate over the entire set in descending order? I looked at the source and it creates an Iterator that starts at the lowest key and then tries to find the next lowest key (which obviously doesn't exist). Am I not reading something right in the JavaDoc? When iterating using navigableKeySet().iterator() I see all 15 keys printed in ascending order, (as expected). When I iterate with descendingKeySet().descendingIterator() I see the 15 keys printed in ascending order, (as expected since descending set followed by a descending iterator should give me ascending order). When iterating using descendingKeySet().iterator, I see the 15 keys printed in descending order, (as expected). I've attached a very simple program that illustrates what I'm describing. Could someone clarify this behavior? thanks, charlie ...

7 15

6636363: BufferUnderflowException decoding length 6 UTF-8 sequences with direct buffers
by Martin Buchholz 20 Apr '08

20 Apr '08

Xueming and/or Iris: Here's a fix for 6636363: BufferUnderflowException decoding length 6 UTF-8 sequences with direct buffers This is a very obscure bug, but I like very much real bug fixes that are smallest possible i.e. change only one bit of the source code. A regression test will be forthcoming once FindDecodingBugs.java and friends are opened. diff --git a/src/share/classes/sun/nio/cs/UTF_8.java b/src/share/classes/sun/nio/cs/UTF_8.java --- a/src/share/classes/sun/nio/cs/UTF_8.java +++ b/src/share/classes/sun/nio/cs/UTF_8.java @@ -326,7 +326,7 @@ class UTF_8 extends Unicode case 12: case 13: // 6 bytes, 31 bits - if (src.remaining() < 4) + if (src.remaining() < 5) return CoderResult.UNDERFLOW; if (!isContinuation(b2 = src.get())) return CoderResult.malformedForLength(1);

1 0

CFV: Project sponsorship: More New I/0 APIs for te Java Platform (JSR-203)
by iris clark 18 Apr '08

18 Apr '08

Greetings, voting members of the Core Libraries Group! Question: Should the Core Libraries Group sponsor the "More New I/O APIs for the Java Platform (JSR-203) Project[1]? Please cast your vote by replying, publicly, to this message with either Vote: yes or Vote: no as the first line of the message body. You may, at your option, indicate the reason for your decision on subsequent lines. Votes must be cast in the open; votes sent as private replies will not be counted. The sponsorship decision will be made by a simple majority vote of the Group's Members. Votes are due by midnight UTC next Wednesday, 22 April. As an optimization, if an absolute majority of the Group's Members votes one way or the other prior to that time then the decision may be rendered earlier. Once a decision has been made the votes will be tallied and reported to this list and also to discuss(a)openjdk.java.net. Only Members of the Core Libraries Group are eligible to vote on this decision. The current Members are: Alan Bateman Christopher Hegarty David Bristor Iris Clark Doug Lea Jeff Nisewanger Joe Darcy Mark Reinhold Martin Buchholz Pete Soper Peter Jones Xueming Shen Thanks, iris [1] http://mail.openjdk.java.net/pipermail/announce/2008-April/000063.html

9 10