Hashtable's and the tale of runtime

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Andrew Haley writes:
 > Christian Thalinger writes:
 >  > Hi!
 >  > 
 >  > We had a curious problem with SPECjvm98 _213_javac and cacao.  A newly
 >  > recompiled cacao ended with 10% preformance degradation.  After further
 >  > investigation we ended with VMSystem.identityHashCode() and it's return
 >  > value.
 >  > 
 >  > _213_javac make heavy use of Hashtable's and the objects stored in the
 >  > hashtable use VMSystem.identityHashCode() as their hash function.  Since
 >  > alignment is normally 8 or 16-bytes, the distribution of the objects
 >  > seems to be not optimal.  We ended with 40000 Object.equals() calls more
 >  > and a doubled runtime for Hashtable.get() (measured clock cycles), as
 >  > Object.equals() is used in Hashtable.get().
 > 
 > This seems a bit strange.  Hashtable.rehash() seems always to generate
 > a new capacity based on the old capacity * 2 + 1, so you wouldn't
 > expect to see a great many collisions as the definition of hash() is
 > 
 >    key.hashCode() % buckets.length
 > 
 > Okay, buckets.length isn't necessarily prime, but you wouldn't expect
 > this to have a very non-uniform distribution.
 > 
 >  > A shifting of the VMSystem.identityHashCode() pointer value helps
 >  > (sometimes), but shifting by 3 makes it even worse (what was my guess to
 >  > make it better).
 >  > 
 >  > Any thoughts?  Should we change Hashtable.hash()?  Or return a better
 >  > value for VMSystem.identityHashCode()?  But most runtimes only return
 >  > the memory pointer...
 > 
 > There are things that we can try, such a using a better way to turn an
 > address into a hash.  But it would be nice first to know the real
 > cause of the very non-uniform distribution, if indeed that's what is
 > happening.

A bit more thinking: the hash table size is guranteed never to be a
multiple of a power of two, so the fact that the addresses always are
multiples of power of two shouldn't matter.

After a bit of experimenting, I get 1651956 collisions per 10716023
probes (about 16%) which is not far from what Knuth expects for an
unsuccessful lookup with a truly random hash function and a half-full
table.

This percentage didn't improve when I used a scrambling function to do
the hashing: in fact it got slightly worse, but that might be in the
noise.

   unsigned long addr = (unsigned long)obj;
   unsigned long rotate = (addr >> 5 | addr << 27);
   return (addr ^ rotate) & 0x7fffffff;

So, Twisti: what proportion of hash table probles generate collisions
when you do the experiment?

Andrew.


[Index of Archives]     [Linux Kernel]     [Linux Cryptography]     [Fedora]     [Fedora Directory]     [Red Hat Development]

  Powered by Linux