Hash table performance
in [Java Programming]
|
Prev: The future of Java
Next: weird issue with new lines
From: Jon Harrop on 23 Nov 2009 11:11 Lew wrote: > 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. The JVM cannot generate type-specialized data structures as the CLR does because the types have been erased. > Type erasure has no effect on the number of allocations, let alone "orders > of magnitude". Type erasure forces all values to be cast to Object which forces value types (like double) to be boxed into objects which is an allocation. The JVM boxes all 20,000,000 of the doubles generated by this program whereas the CLR boxes none of them. That is the "orders of magnitude" difference I was referring to. > 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. Casting a primitive type to Object incurs an allocation. > 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. You are assuming that Foo is an object which is not true in general and is not true in this case. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Jon Harrop on 23 Nov 2009 11:21 I was considering the possibility of hand coding type-specialized hash tables in Java to work around this deficiency in generics on the JVM when I realised that it is actually impossible in the general case because the JVM lacks value types and, therefore, is incapable of expressing efficient hash tables. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Patricia Shanahan on 23 Nov 2009 10:12 Jon Harrop wrote: > I was considering the possibility of hand coding type-specialized hash > tables in Java to work around this deficiency in generics on the JVM when I > realised that it is actually impossible in the general case because the JVM > lacks value types and, therefore, is incapable of expressing efficient hash > tables. > Are you sure Java is the right language for your current project? If I were fighting the language to the extent you seem to be doing, I would seriously reexamine my choice of language. Patricia
From: Lew on 23 Nov 2009 11:03 Jon Harrop wrote: > Type erasure forces all values to be cast to Object which forces value types > (like double) to be boxed into objects which is an allocation. The JVM > boxes all 20,000,000 of the doubles generated by this program whereas the > CLR boxes none of them. That is the "orders of magnitude" difference I was > referring to. > That's not an issue of type erasure but of Java not supporting collections of primitive types. It is the autoboxing of 'double' to 'Double' that you discuss here, not the erasure of 'Double' to 'Object'. Type erasure has nothing to do with value types being boxed. The erasure from 'Double' to 'Object' has no further effect on performance. Others in this thread have tried to duplicate the degree of slowdown you report without being able to. No one else here seems to see a 32:1 ratio in performance. -- Lew
From: Patricia Shanahan on 23 Nov 2009 11:27
Lew wrote: .... > Others in this thread have tried to duplicate the degree of slowdown > you report without being able to. No one else here seems to see a > 32:1 ratio in performance. That may change with the opportunity to run Jon's F# code - let's see what other people who have F# installed get. Patricia |