Hash table performance
in [Java Programming]
|
Prev: The future of Java
Next: weird issue with new lines
From: Jon Harrop on 23 Nov 2009 15:31 Lew wrote: > 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 means that Java's generics cannot be used to improve the performance of my benchmark. > 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. Has anyone else here even benchmarked the F# code? If so, what performance ratio did they get? -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Marcin Rzeźnicki on 23 Nov 2009 14:23 On 23 Lis, 21:04, Jon Harrop <j...(a)ffconsultancy.com> wrote: > Marcin Rzeźnicki wrote: > > On 23 Lis, 17:11, Jon Harrop <j...(a)ffconsultancy.com> wrote: > >> Lew wrote: > >> > 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 true Jon. Type erasure does not force anything in your > > example - you even did not use generics at all, so how can it affect > > anything? > > Type erasure prevents generics from helping on the JVM as they do on the > CLR. > In your case I cannot see generics used at all. > > The problem here is that Java lacks value types which is orthognal to > > generics implementation > > The non-generic F# solution is roughly as slow as the Java. Only the generic > F# solution is faster. > So you are running different program than you showed us. But that's not the point. The point is that the only thing which may make it run so fast is the presence of value types. Which still has nothing to do with type erasure. Type erasure does not forbid compiler from making this kind of optimization which you've been talking about. > >> > 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. > > > Not necessarily - Java specification permits caching instances of > > boxed numerics. > > Sure. That obviously isn't helping on this benchmark. > Yes, unfortunately. > >> > 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. > > > It is true in general, > > In this case, Foo is double which is not an object and Lew's statements do > not apply. > Ok, nevermind. It is not relevant to our discussion I suppose (his assumption that "Foo is an object" IS true) > > furthermore it is always true in F# or any  > > language implemented on top of CLR where there is no notion of > > "primitive type". > > My program is a counter example. In general, the CLR's notion of value types > are equivalent to the JVM's primitive types. > No, it is not. Value types can be heap-allocated while primitives cannot. > > The thing we should discuss after filtering half- > > truths out is whether difference between value types and reference > > types might cause 32x performance degradation > > When using reference types, F# is roughly as slow as Java. The difference > occurs when a generic data structure is parameterized over a value type. > Could you please take a look at my benchmark (it states that slowdown should be ~30%) and, if you have access to a machine with NetBeans (or any Java profiler), and perform similar profiling on your own? I am suspecting there is something more than than meets the eye.
From: Lew on 23 Nov 2009 14:30 Jon Harrop wrote: > Copying a few bytes of data is a *lot* faster than allocating a few bytes of > data. > According to sun.com and Brian Goetz's articles on DeveloperWorks, object allocation in Java (discounting GC) is an O(1) operation involving 10-12 machine instructions. <http://www.ibm.com/developerworks/java/library/j-jtp09275.html> "The answer may surprise you -- allocation in modern JVMs is far faster than the best performing malloc implementations. The common code path for new Object() in HotSpot 1.4.2 and later is approximately 10 machine instructions (data provided by Sun; see Resources)," -- Lew
From: Marcin Rzeźnicki on 23 Nov 2009 14:43 On 23 Lis, 21:31, Jon Harrop <j...(a)ffconsultancy.com> wrote: > Patricia Shanahan wrote: > > 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. > > I think the bottleneck must be the GC by a long long way. Look at this: > > $ time java Hashtbl -Xmx800m > hashtable(100.0) = 0.01 > > real   0m34.676s > user   1m55.723s > sys   0m3.332s > > The CPU time taken is actually ~100x worse than for F#. Given that this is a > serial benchmark, that parallelism could only have come from the GC. > When I was running mine I observed that only ~6% of time was marked as spent in GC and even that only if I allocated too little space for the heap (then, right before OutOfMemory it started to reclaim space wildly but, of course, failed). When I set heap to -Xms512m -Xmx512m GC time was negligibly small. I wonder what would happened if you repeated your tests with -Xms800m -Xmx800m.
From: Jon Harrop on 23 Nov 2009 16:00
Marcin Rzeźnicki wrote: > In your case I cannot see generics used at all. In the F#? >> The non-generic F# solution is roughly as slow as the Java. Only the >> generic F# solution is faster. > > So you are running different program than you showed us. I showed you the generic F# program that is 32x faster than the Java program. > But that's > not the point. The point is that the only thing which may make it run > so fast is the presence of value types. Perhaps you mean that without generics but with value types you could obtain the same performance by writing a type specialized DoubleDoubleHashMap? I'd agree with that. My point was that using a non-generic Hashtable in F# destroys its performance. > Which still has nothing to do > with type erasure. Type erasure does not forbid compiler from making > this kind of optimization which you've been talking about. The VM cannot type specialize data structures if the type information has been erased. >> > furthermore it is always true in F# or any >> > language implemented on top of CLR where there is no notion of >> > "primitive type". >> >> My program is a counter example. In general, the CLR's notion of value >> types are equivalent to the JVM's primitive types. > > No, it is not. Value types can be heap-allocated while primitives > cannot. Local value/primitive types are stack allocated. Heap allocated reference types may contain value/primitive types. >> > The thing we should discuss after filtering half- >> > truths out is whether difference between value types and reference >> > types might cause 32x performance degradation >> >> When using reference types, F# is roughly as slow as Java. The difference >> occurs when a generic data structure is parameterized over a value type. > > Could you please take a look at my benchmark (it states that slowdown > should be ~30%) No, it shows that ~30% of the time is spent allocating in the mutator. It says nothing about how much time is spent collecting in the GC. Given that this benchmark spends half of its time burning all eight of my cores, I think collection must be the bottleneck. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u |