Hash table performance
in [Java Programming]
|
Prev: The future of Java
Next: weird issue with new lines
From: Arne Vajhøj on 21 Nov 2009 14:07 Marcin Rzeźnicki wrote: > On 21 Lis, 19:33, Jon Harrop <j...(a)ffconsultancy.com> wrote: >> I'm having trouble getting Java's hash tables to run as fast as .NET's. >> Specifically, the following program is 32x slower than the equivalent >> on .NET: >> >> import java.util.Hashtable; >> >> public class Hashtbl { >> public static void main(String args[]){ >> Hashtable hashtable = new Hashtable(); >> >> for(int i=1; i<=10000000; ++i) { >> double x = i; >> hashtable.put(x, 1.0 / x); >> } >> >> System.out.println("hashtable(100.0) = " + hashtable.get(100.0)); >> } >> } >> >> My guess is that this is because the JVM is boxing every floating point >> number individually in the hash table due to type erasure whereas .NET >> creates a specialized data structure specifically for a float->float hash >> table with the floats unboxed. Consequently, the JVM is doing enormously >> numbers of allocations whereas .NET is not. >> >> Is that correct? > You are using Hashtable instead of HashMap - probably the performance > loss you've observed is due to synchronization (though "fat" > synchronization might be optimized away in case of single thread you > still pay the price, though lower). If you took a look at JavaDoc, > you'd notice that HashTable methods are synchronized As of boxing, you > are correct (though there is no type erasure in your example because > you did not specify type parameters at all) but I suspect that these > costs are not the most contributing factor to overall poor > performance. I'd blame synchronization in the first place. That does not match measurements. Arne
From: Tom Anderson on 21 Nov 2009 14:44 On Sat, 21 Nov 2009, Marcin Rze?nicki wrote: > On 21 Lis, 19:33, Jon Harrop <j...(a)ffconsultancy.com> wrote: >> I'm having trouble getting Java's hash tables to run as fast as .NET's. >> Specifically, the following program is 32x slower than the equivalent >> on .NET: >> >> � import java.util.Hashtable; >> >> � public class Hashtbl { >> � � public static void main(String args[]){ >> � � � Hashtable hashtable = new Hashtable(); >> >> � � � for(int i=1; i<=10000000; ++i) { >> � � � � double x = i; >> � � � � hashtable.put(x, 1.0 / x); >> � � � } >> >> � � � System.out.println("hashtable(100.0) = " + hashtable.get(100.0)); >> � � } >> � } >> >> My guess is that this is because the JVM is boxing every floating point >> number individually in the hash table due to type erasure whereas .NET >> creates a specialized data structure specifically for a float->float hash >> table with the floats unboxed. Consequently, the JVM is doing enormously >> numbers of allocations whereas .NET is not. >> >> Is that correct? > > You are using Hashtable instead of HashMap - probably the performance > loss you've observed is due to synchronization (though "fat" > synchronization might be optimized away in case of single thread you > still pay the price, though lower). If you took a look at JavaDoc, you'd > notice that HashTable methods are synchronized As of boxing, you are > correct (though there is no type erasure in your example because you did > not specify type parameters at all) but I suspect that these costs are > not the most contributing factor to overall poor performance. I'd blame > synchronization in the first place. I'd be *very* surprised if that was true. In this simple program, escape analysis could eliminate the locking entirely - and current versions of JDK 1.6 do escape analysis. Even if for some reason it didn't, you'd only be using a thin lock here, which takes two x86 instructions and one memory access for each lock and unlock operation, far less than the boxing or unboxing. I modified the test code to look like this (yes, with no warmup - this is very quick and dirty): import java.util.Map; import java.util.HashMap; import java.util.Hashtable; public class HashPerf { public static void main(String args[]) throws InterruptedException{ for(int i=1; i<=100; ++i) { long t0 = System.nanoTime(); test(); long t1 = System.nanoTime(); long dt = t1 - t0; System.out.println(dt); System.gc(); Thread.sleep(200); } } private static void test(){ Map<Double, Double> hashtable = new HashMap<Double, Double>(); // Map<Double, Double> hashtable = new Hashtable<Double, Double>(); for(int i=1; i<=1000; ++i) { double x = i; // synchronized (hashtable) { hashtable.put(x, 1.0 / x); // } } } } And then ran it with three variations on the comments: one as above, one uncommenting the synchronization of the hashtable, and one switching the HashMap to a Hashtable. I have java 1.5.0_19 on an elderly and ailing PowerPC Mac laptop. I ran with -server and otherwise stock settings. The timings for each show the usual power curve distribution: 80% of the measurements are no more than 50% longer than the fastest, and 90% are no more than twice as long, with the last 10% being up to 10 times longer. If we say that the slowest 10% are artifacts of warmup, GC, the machine doing other things, etc, and ignore them, then the average times i got were (with standard error of the mean, which is broadly like a ~60% confidence limit IIRC): HashMap 933500 +/- 15006 sync HashMap 1003200 +/- 16187 Hashtable 868322 +/- 11602 That is, adding synchronization to the accesses adds a 7.5% overhead. Although somehow, the old Hashtable comes out faster! So, even with java 1.5, adding synchronization to HashMap.put() imposes only a small performance penalty - i'd expect it to be less with 1.6. I doubt very much that this is the major factor in the OP's performance problem. tom -- .... the gripping first chapter, which literally grips you because it's printed on a large clamp.
From: Tom Anderson on 21 Nov 2009 14:46 On Sat, 21 Nov 2009, Arne Vajh?j wrote: > Tom Anderson wrote: >> Could you try changing the put line to: >> >> hashtable.put(Double.toString(x), Double.toString(1.0 / x)); >> >> And making the corresponding change in the C# or whatever version, and >> making the comparison again? That eliminates boxing in java, so if the >> difference is due to boxing, it will be significantly reduced, which will >> give you some clues as to what's going on. > > I would still consider it boxing - just to String instead of Double. I take the point that it's still creating an object. But it is simply, undeniably, not boxing. Moreover, the point is that i was suggesting adding the *same* object creation to both the java and .NET versions, which would eliminate any differences in language-level boxing behaviour. tom -- Ten years of radio astronomy have taught humanity more about the creation and organization of the universe than thousands of years of religion and philosophy. -- P. C. W. Davis
From: Peter Duniho on 21 Nov 2009 16:02 Tom Anderson wrote: > On Sat, 21 Nov 2009, Arne Vajh?j wrote: > >> Tom Anderson wrote: >>> Could you try changing the put line to: >>> >>> hashtable.put(Double.toString(x), Double.toString(1.0 / x)); >>> >>> And making the corresponding change in the C# or whatever version, >>> and making the comparison again? That eliminates boxing in java, so >>> if the difference is due to boxing, it will be significantly reduced, >>> which will give you some clues as to what's going on. >> >> I would still consider it boxing - just to String instead of Double. > > I take the point that it's still creating an object. But it is simply, > undeniably, not boxing. > > Moreover, the point is that i was suggesting adding the *same* object > creation to both the java and .NET versions, which would eliminate any > differences in language-level boxing behaviour. But you can force boxing in .NET just by using Object as the type for the collection class type parameters instead of Double. So wouldn't a better test be to do that? Rather than introducing yet another point of possible incongruity? If you are concerned about "differences in language-level boxing behavior", I'd think there'd be just as much concern about "differences in language-level string conversion behavior". I see no reason to think that boxing in .NET would be any more or less different from boxing in Java than string conversion in ..NET would be from string conversion in Java. In any case, I think Arne's point still stands though: "boxing" can be thought of generally or specifically. Specifically, you're right...conversion to String isn't strictly speaking boxing. But generally, inasmuch as "boxing" is simply a way to convert a value type (primitive) to a reference type (class), converting to String is as valid a way to "box" a value type as converting to Object or Double. It really just depends on how strictly you choose to define boxing, and how literally you take the phrase "consider it boxing". In some sense, converting to a String isn't "eliminating boxing in Java", but rather just accomplishing the same thing as boxing but in a slightly different way. A person who insists with absolute stubbornness that there is only one possible interpretation of a particular term or phrase may of course disagree with my analysis of the question. :) Pete
From: markspace on 21 Nov 2009 16:07
Jon Harrop wrote: > My guess is that this is because the JVM is boxing every floating point > number individually in the hash table due to type erasure whereas .NET > creates a specialized data structure specifically for a float->float hash > table with the floats unboxed. Consequently, the JVM is doing enormously > numbers of allocations whereas .NET is not. > > Is that correct? No, not primarily. In my testing I found: 1. I think the JVM itself makes the most difference. 2. Next was synchronization. 3. Autoboxing appears to have an impact but it's less than either #1 or #2. The first time I ran your program, it took over 79 seconds to execute. During the course of testing the other algorithms, that time reduced to about 13 seconds and stayed there. Very odd, but I assume that something somewhere optimized the code. Unlike a lot of the posters here, I'm running a 32 client JVM, which is slow to optimize code. 64 bit systems run in -server mode by default, which optimizes code before executing it. The first place to look is your environment: memory, flags to the JVM, which JVM version and vendor, other "system" variables, etc. Somewhat surprising to me, just substituting a a HashMap for the HashTable reduced the time to about half -- 6 seconds instead of 13. Both autobox, the only difference is synchronization. Lastly, removing the autoboxing by writing a specialized class saved about 0.7 second from just using HashMap. The specialized version time was 5.3 seconds. Note that I allocated a new object myself -- the "Entry" for the HashMap -- each time a new double is added. I suspect that any reasonable C# hash object must do the same, so you're not losing as much time as you think by Java's auto object creation. I'm curious to see your C# version, and see actual times for both programs on your system. The results might tell us what is going on. "32x" doesn't really give us much of a clue. Output of the following: <output> run-single: HashTable time: 12844 hashtable(100.0) = 0.01 HashMap time: 6016 hashtable(100.0) = 0.01 HashTest time: 5373 hashtable(100.0) = 0.01 BUILD SUCCESSFUL (total time: 29 seconds) </output> <code> package cljp; import java.util.HashMap; import java.util.Hashtable; import static java.lang.System.out; public class HashTest { public static void main( String[] args ) { Hashtbl.test(); HashM.test(); HashTest.test(); } HashMap<Entry,Entry> hash = new HashMap<Entry,Entry>(); private static class Entry { final double key; final double value; public Entry( double key, double value ) { this.key = key; this.value = value; } @Override public int hashCode() { long bits = Double.doubleToLongBits( key ); bits ^= bits >>> 32; return (int)bits; } @Override public boolean equals( Object obj ) { if( !(obj instanceof Entry ) ){ return false; } return key == ((Entry)obj).key; } } public void put( double key, double value ) { Entry e = new Entry(key, value ); hash.put( e, e ); } public double get( double key ) { Entry e = new Entry( key, 0.0 ); Entry valueEntry = hash.get( e ); if( valueEntry != null ) { return valueEntry.value; } else { throw new IllegalArgumentException("Not found: "+key); } } public static void test() { long start = System.nanoTime(); HashTest hashTest = new HashTest(); for( int i = 1; i <= 10000000; ++i ) { double x = i; hashTest.put( x, 1.0 / x ); } long end = System.nanoTime(); out.println( "HashTest time: "+ (end-start)/1000000 ); out.println( "hashtable(100.0) = " + hashTest.get( 100.0 ) ); } } class HashM { public static void test() { long start = System.nanoTime(); HashMap<Double,Double> hashM = new HashMap<Double, Double>(); for( int i = 1; i <= 10000000; ++i ) { double x = i; hashM.put( x, 1.0 / x ); } long end = System.nanoTime(); out.println( "HashMap time: "+ (end-start)/1000000 ); out.println( "hashtable(100.0) = " + hashM.get( 100.0 ) ); } } class Hashtbl { public static void test() { long start = System.nanoTime(); Hashtable hashtable = new Hashtable(); for( int i = 1; i <= 10000000; ++i ) { double x = i; hashtable.put( x, 1.0 / x ); } long end = System.nanoTime(); out.println( "HashTable time: "+ (end-start)/1000000 ); out.println( "hashtable(100.0) = " + hashtable.get( 100.0 ) ); } } </code> |