Hash table performance
in [Java Programming]
|
Prev: The future of Java
Next: weird issue with new lines
From: Roedy Green on 22 Nov 2009 17:41 On Sat, 21 Nov 2009 18:33:14 +0000, Jon Harrop <jon(a)ffconsultancy.com> wrote, quoted or indirectly quoted someone who said : >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: see http://mindprod.com/jgloss/hashmap.html#SPEED -- Roedy Green Canadian Mind Products http://mindprod.com Finding a bug is a sign you were asleep a the switch when coding. Stop debugging, and go back over your code line by line.
From: Jon Harrop on 23 Nov 2009 07:48 Marcin Rzeźnicki wrote: > On 22 Lis, 20:43, Jon Harrop <j...(a)ffconsultancy.com> wrote: >> Marcin Rzeźnicki wrote: >> > Yeah, I see. Well, what VM did Jon use? That might be crucial to know >> > what happened. >> >> $ java -version >> java version "1.6.0_13" >> Java(TM) SE Runtime Environment (build 1.6.0_13-b03) >> Java HotSpot(TM) Server VM (build 11.3-b02, mixed mode) > > Quite recent. And were your measurements affected by using HashMap > instead? Not affected. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Jon Harrop on 23 Nov 2009 07:51 Martin Gregorie wrote: > Did you try setting the initial capacity to 1000? I just tried setting it to the final size of the hash table (10M) and the time actually got slightly worse. > I've had terrible performance from C programs that malloced for every one > of a huge number of little items it wanted to put on the heap. I'd hope > any JVM was better than that but you never know.... Besides, its quite > possible NET allocates bigger chunks since Windows memory allocation was/ > is quite slow. I believe the JVM is doing orders of magnitude more allocations than .NET here due to its type erasure approach to generics. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Jon Harrop on 23 Nov 2009 07:57 Patricia Shanahan wrote: > It might help to show your .NET program as well. If people ran both it > and the Java version on a few different systems, we could see how much, > if any, of the performance difference is configuration-specific. Sure, here's the F# code for .NET: let n = 10000000 let m = System.Collections.Generic.Dictionary(n) for i=1 to n do m.[float i] <- 1.0 / float i printf "%d %g\n" m.Count m.[100.0] That takes around 1s and the Java code takes around 32s here. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Lew on 23 Nov 2009 08:59
Jon Harrop wrote: > I believe the JVM is doing orders of magnitude more allocations than .NET > here due to its type erasure approach to generics. Type erasure has no effect on your original problem. Type erasure has no effect on the number of allocations, let alone "orders of magnitude". It simply means that a parametrized type is treated as an 'Object' by the JVM. It affects the number of casts, which may be affected by the HotSpot optimizer. If you allocate, say, a 'Set<Foo>' then fill it with 1000 'Foo' instances, you have 1001 allocations plus however many allocation/copy operations are necessary to grow the 'Set' to hold 1000 references (six with a typical default initial size, zero if you made it big enough to hold 1000). Type erasure has nothing to do with it - you're still creating only 'Foo' objects and enough 'Set' slots to refer to them. -- Lew |