Hash table performance
in [Java Programming]
|
Prev: The future of Java
Next: weird issue with new lines
From: Patricia Shanahan on 23 Nov 2009 13:18 Marcin Rzeźnicki wrote: .... > Now, the interesting part is > 30.3% of time spent in java.lang.Double.valueOf(double) <--- that's > boxing > Furthermore, there were 2m + 1 calls to new Double meaning that no > caching occurred. Interesting results. That is about what I would expect. If we were trying to explain a 30% performance difference I would seriously consider autoboxing as cause. If creating an Entry takes about as much time as creating a Double, object creation could account for up to 45% of the Java time. The problem is explaining a 32x performance difference. The cause or causes have to account for over 96% of the Java time. Patricia
From: Roedy Green on 23 Nov 2009 13:20 On Mon, 23 Nov 2009 12:51:58 +0000, Jon Harrop <jon(a)ffconsultancy.com> wrote, quoted or indirectly quoted someone who said : >I believe the JVM is doing orders of magnitude more allocations than .NET >here due to its type erasure approach to generics. I think you mean the extra overhead of boxing and unboxing, or perhaps the extra overhead of allocating independent objects, rather that plopping them into a single array the way you would with primitives. You could find out the boxing/allocation overhead by preboxing your elements, and saving the unboxing until you had waved the flag. -- 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 14:36 Patricia Shanahan wrote: > Jon Harrop wrote: >> 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. > > I don't think type erasure or generics have anything to do with it. > > On a non-rehashing call, the JVM would do three allocations, one of > which, for the Entry, would have been required regardless of the types. There is no need to allocate each entry separately because the hash table can be an array of unboxed entries. > The other two are due the lack of primitive-based implementations of the > java.util collections, causing two autobox conversions from double to > Double. Yes. > The .NET implementation may have a different way of storing the hash > chains that avoids allocating an object for each put call. I believe the chains are stored in the same array: closed hashing. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Roedy Green on 23 Nov 2009 13:28 On Sat, 21 Nov 2009 18:33:14 +0000, Jon Harrop <jon(a)ffconsultancy.com> wrote, quoted or indirectly quoted someone who said : >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 In the olden days of FORTRAN, you would have handled this by writing a version of HashMap that took a floating point primitive. You would hard code it in. You have to hold your nose, but if you want just to get the job done. -- 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: Roedy Green on 23 Nov 2009 13:31
On Mon, 23 Nov 2009 12:57:53 +0000, Jon Harrop <jon(a)ffconsultancy.com> wrote, quoted or indirectly quoted someone who said : > printf "%d %g\n" m.Count m.[100.0] > >That takes around 1s and the Java code takes around 32s here. How fast is it without the printf. Java's console i/o is painfully slow. -- 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. |