Hash table performance
in [Java Programming]
|
Prev: The future of Java
Next: weird issue with new lines
From: markspace on 23 Nov 2009 13:53 Marcin Rzeźnicki wrote: > 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. I ran my test (18 seconds for Jon's code on a 32 bit laptop) with -Xmx800m. Which is why I keep saying that Jon should look at his JVM flags before trying anything else.
From: Roedy Green on 23 Nov 2009 13:54 On Mon, 23 Nov 2009 10:16:21 -0800, Roedy Green <see_website(a)mindprod.com.invalid> wrote, quoted or indirectly quoted someone who said : >Could you elaborate a bit on what value types would look like if they >existed in Java and how you would use them for efficient hash tables? for a little background on them see http://mindprod.com/jgloss/valuetype.html -- 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 15:09 Marcin Rzeźnicki wrote: > Oh yes, conclusions: > Taking Jon's 32s of the execution time he could have saved around 3-4s > had he preallocated HashMap. I already posted results using preallocation: it was no faster. > He actually did that in his F# so this > modification alone might have caused F# version to run in, let's say, > 28s. Are you speculating that F# would take 28x longer had I not preallocated? Measuring it, F# takes 1.24s if you don't preallocate and 0.945s if you do. > He, of course, could not eliminate boxing which might have taken > around 10s of his original execution time. So subtracting costs of > boxing from implied theoretical F# version's execution time we end up > with conclusion that F# should have executed in ~18s (which is > erroneous proceeder in itself because F# probably copies values from > stack). Roughly 1:2 in favor of F#. Eh? -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Jon Harrop on 23 Nov 2009 15:16 Patricia Shanahan wrote: > 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. I'm more interested in modern JVM-based languages like Clojure and Scala. Do you know if they have done anything to work around these deficiencies in the JVM? Also, some influential people on the JVM Languages mailing list were discussing what they perceived to be the main issues with the JVM today and they flagged lack of value types as a major issue. This benchmark seems to have verified their findings. Moreover, I am amazed that I watched a lecture where a guy from Azul Systems described the enormous lengths they'd gone to in creating a scalable hash table built upon the JVM for parallel machines. Their implementation would have to scale across at least 32 cores (far more than any of today's consumer-level machines) just to catch up with the CLR! -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: Jon Harrop on 23 Nov 2009 15:18
Roedy Green wrote: > 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. 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. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u |