Hash table performance
in [Java Programming]
|
Prev: The future of Java
Next: weird issue with new lines
From: Marcin Rzeźnicki on 23 Nov 2009 13:36 On 23 Lis, 19:18, Patricia Shanahan <p...(a)acm.org> 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. > Actually it takes much longer. I had 2m double creations, and 1m entry creations - so I was expecting that ratio would be: (time_to_create_all_doubles) = 2 * (time_to_create_all_entries). It is not quite so looking at the profiled call trace. It costed me about 6x more to create single Double than to create single entry. 1m of entry <init> calls accounted for 1.4% of total time, while 2m of Double <init> calls accounted for 16.4% of total time. I think that it is because each Double must super-call the Number constructor. > The problem is explaining a 32x performance difference. The cause or > causes have to account for over 96% of the Java time. > That could well be hidden in GC/heap resizing costs if he did not allocate Java heap properly. I prevented these effects mostly from occurring by running this example with -Xms512m -Xmx512m.
From: Marcin Rzeźnicki on 23 Nov 2009 13:38 On 23 Lis, 20:30, Jon Harrop <j...(a)ffconsultancy.com> wrote: > Marcin Rzeźnicki wrote: > > On 23 Lis, 16:58, Jon Harrop <j...(a)ffconsultancy.com> wrote: > >> Patricia Shanahan wrote: > >> > My reasoning is that you never reuse a key, so every put call creates a > >> > new Entry instance. > > >> Note that an "Entry instance" is a value type on the CLR, something that > >> the JVM is incapable of expressing. > > >> > Creating a Double from a double is about as simple > >> > as object creation can be, > > >> Note that there is no object creation on the CLR and, indeed, I believe > >> that is precisely why it is so much faster. > > > But, correct me if I am wrong, it involves copying a value type. > > Correct. > > > If it is so, then I am not sure why copying would be better than an object > > allocation > > Copying a few bytes of data is a *lot* faster than allocating a few bytes of > data. > Yes, but I am talking about amortized cost. If Java has to create a new instance it does not allocate memory. Cost of memory allocations is amortized through many object creations - which cannot be done when copying.
From: Marcin Rzeźnicki on 23 Nov 2009 13:42 On 23 Lis, 19:31, Roedy Green <see_webs...(a)mindprod.com.invalid> wrote: > On Mon, 23 Nov 2009 12:57:53 +0000, Jon Harrop <j...(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. It is certainlynot THAT slow. According to profiling session results it did take about 1ms, while whole profiled program ran in 35s
From: markspace on 23 Nov 2009 13:45 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. > If you must use the Map interface, yes. If you can use a specific type, then you can overload the put() and get(). class DoubleMap extends AbstractMap<Double,Double> { ... @Overload public Double put( Double key, Double value ) ... public double put( double key, double value ) ... } I believe that the compiler will always chose the second put() method when the parameter types involved are double instead of Double. If the type of the object is DoubleMap, of course. If you use the generic Map interface as your type, the compiler will have no choice but to use the first method.
From: Jon Harrop on 23 Nov 2009 15:04
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. > 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. >> > 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. >> > 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. > 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. > 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. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u |