Hash table performance
in [Java Programming]
|
Prev: The future of Java
Next: weird issue with new lines
From: Jon Harrop on 23 Nov 2009 16:06 Marcin Rzeźnicki wrote: > I started from 32s of your Java program execution time which you'd > reported and subtracted all costs that were suggested not to affect F# > version (preallocation/boxing). This is quite inaccurate because of > different algorithms, environments etc but it enabled me to compare > what F#'s execution time could have been IF Java's was 32s as you'd > observed. The result, as you have seen, is that even if F# did not pay > any additional cost in execution time for value type copying etc it > should execute 2 times faster than Java version. So the only logical > conclusion is that 32 times faster is something not usual. You didn't account for time spent garbage collecting. FWIW, the F# performs only one collection of each generation. Verbose GC information on the Java code produces pages and pages of collections. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Jon Harrop on 23 Nov 2009 16:07 Jon Harrop wrote: > Doesn't seem to make any difference: Spoke too soon. This is 4x faster than before: $ time java -Xms2000m -Xmx2000m Hashtbl hashtable(100.0) = 0.01 real 0m8.198s user 0m45.227s sys 0m1.068s -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Marcin Rzeźnicki on 23 Nov 2009 15:19 On 23 Lis, 22:00, Jon Harrop <j...(a)ffconsultancy.com> wrote: > 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. > In your program you have: let m = System.Collections.Generic.Dictionary(n) Maybe I am not reading this line correctly but where are generics used here? > > 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. > More or less, I think that specialized double map would have performed ~50% better. > > 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. > Yes, but if a value type were descendants of Object (as it is done in CLR) then type erasure would not prevent compiler from using this optimization. The cost of type erasure would lie only in casts that would have to be performed. > >> > 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. > Sometimes :-) Here is great article explaining this matter: http://blogs.msdn.com/ericlippert/archive/2009/04/27/the-stack-is-an-implementation-detail.aspx > >> > 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. > Well, yes, it does not show GC costs. If you happened to use NetBeans profiler you could easily see what these are
From: Roedy Green on 23 Nov 2009 15:20 On Mon, 23 Nov 2009 20:18:04 +0000, Jon Harrop <jon(a)ffconsultancy.com> wrote, quoted or indirectly quoted someone who said : >You cannot do that in Java because it cannot represent the array that >underpins the hash table because it requires different primitive types in >the same array. Really really holding your nose, you have to map them to longs, stealing a low order bit to encode privitive type. -- 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: Marcin Rzeźnicki on 23 Nov 2009 15:23
On 23 Lis, 22:06, Jon Harrop <j...(a)ffconsultancy.com> wrote: > Marcin Rzeźnicki wrote: > > I started from 32s of your Java program execution time which you'd > > reported and subtracted all costs that were suggested not to affect F# > > version (preallocation/boxing). This is quite inaccurate because of > > different algorithms, environments etc but it enabled me to compare > > what F#'s execution time could have been IF Java's was 32s as you'd > > observed. The result, as you have seen, is that even if F# did not pay > > any additional cost in execution time for value type copying etc it > > should execute 2 times faster than Java version. So the only logical > > conclusion is that 32 times faster is something not usual. > > You didn't account for time spent garbage collecting. > > FWIW, the F# performs only one collection of each generation. Verbose GC > information on the Java code produces pages and pages of collections. > Right, so - the next conclusion is that real costs are elsewhere, in some place I did not take into account. That may be GC and heap resizing. If you start with (Xms) heap too small then you'll have frequent collections and, additionally, cost of heap resizing will be more and more noticeable. |