Hash table performance
in [Java Programming]
|
Prev: The future of Java
Next: weird issue with new lines
From: John B. Matthews on 25 Nov 2009 08:08 In article <hl2Pm.37938$We2.32256(a)newsfe09.iad>, Daniel Pitts <newsgroup.spamfilter(a)virtualinfinity.net> wrote: [...] > I did a quick microbench to test division versus shifting. I was > surprised by the result, I expected them to be "close enough", but it > looks like, on my machine at least, there is an order of magnitude > difference: > > <results> > Nothing: count = 874270000 > Shift: count = 869828000 > Divide: count = 91958000 > Nothing: count = 832932000 > Shift: count = 760583000 > Divide: count = 82123000 > Nothing: count = 890739000 > Shift: count = 881628000 > Divide: count = 92349000 > </results> I got comparable results using 1.5: Nothing: count = 332,836,000 Shift: count = 338,866,000 Divide: count = 99,577,000 Nothing: count = 333,075,000 Shift: count = 340,184,000 Divide: count = 102,828,000 Nothing: count = 333,083,000 Shift: count = 340,614,000 Divide: count = 102,943,000 I had to change count to long for 1.6: Nothing: count = 5,907,189,000 Shift: count = 7,800,343,000 Divide: count = 131,041,000 Nothing: count = 5,987,631,000 Shift: count = 7,828,927,000 Divide: count = 131,351,000 Nothing: count = 6,928,390,000 Shift: count = 10,237,517,000 Divide: count = 128,373,000 [Format = "%,14d"] -- John B. Matthews trashgod at gmail dot com <http://sites.google.com/site/drjohnbmatthews>
From: Thomas Pornin on 25 Nov 2009 08:14 According to Thomas Pornin <pornin(a)bolet.org>: > The Intel optimization manual It seems I forgot to say that this is the manual for Pentium IV. --Thomas Pornin
From: Roedy Green on 25 Nov 2009 14:40 On Mon, 23 Nov 2009 18:43:09 -0800, Roedy Green <see_website(a)mindprod.com.invalid> wrote, quoted or indirectly quoted someone who said : > >Hashtbl.exe(jet statically compiled, hashtable(100.0) = null)--> 5 sec >(Why did this code fail? I have reported the bug to jet). Ticket: JET1021 The Jet people reproduced the problem. This is first bug I have found in Jet. This is in 7.0 beta 3. -- Roedy Green Canadian Mind Products http://mindprod.com I mean the word proof not in the sense of the lawyers, who set two half proofs equal to a whole one, but in the sense of a mathematician, where half proof = 0, and it is demanded for proof that every doubt becomes impossible. ~ Carl Friedrich Gauss
From: Roedy Green on 25 Nov 2009 15:16 On Tue, 24 Nov 2009 14:06:54 -0800, markspace <nospam(a)nowhere.com> wrote, quoted or indirectly quoted someone who said : >I noticed that I was getting >terrible performance with a ton of collisions and everything was heaped >up in a tiny spot in the table. for a few tips on writing hashCode methods see http://mindprod.com/jgloss/hashcode.html -- Roedy Green Canadian Mind Products http://mindprod.com I mean the word proof not in the sense of the lawyers, who set two half proofs equal to a whole one, but in the sense of a mathematician, where half proof = 0, and it is demanded for proof that every doubt becomes impossible. ~ Carl Friedrich Gauss
From: Roedy Green on 25 Nov 2009 15:21
On Tue, 24 Nov 2009 14:58:31 -0800, Patricia Shanahan <pats(a)acm.org> wrote, quoted or indirectly quoted someone who said : >If integer remainder had been within a factor of 10 of masking the prime >bucket count would have won. Hashtable does a remainder. HashMap masks off the high bits. You can improve things further by chosing a prime divisor. -- Roedy Green Canadian Mind Products http://mindprod.com I mean the word proof not in the sense of the lawyers, who set two half proofs equal to a whole one, but in the sense of a mathematician, where half proof = 0, and it is demanded for proof that every doubt becomes impossible. ~ Carl Friedrich Gauss |