HashMap collision speed (regression 7->8)

[Chris Hegarty]

Interesting observations.

The class description of HashMap in Java SE 8 alludes to the behaviour you are seeing with respect to Comparable keys.

  "Note that using many keys with the same hashCode() is a sure way to slow down performance of any hash table. To ameliorate impact, when keys are Comparable, this class may use comparison order among keys to help break ties.”

-Chris.

On 8 Jan 2015, at 16:38, Bernd Eckenfels <ecki at zusammenkunft.net> wrote:

> Hello,
> 
> I think it was topic before, but I just wanted to point out, that it is
> still an topic on the internetz. :)
> 
> Motivated by a StackOverflow question regarding HashMap performance
> regression in Java 8
> 
> http://stackoverflow.com/questions/27759527/using-java-7-hashmap-in-java-8/27760442
> 
> I made a JMH test and compared 7 and 8 speed. (the test is not very scientific as I dont really know how to squeeze the longrunning loop which alters state into the harness, but the results seem to be consitent wth theory and stopwatch testing)
> 
> https://gist.github.com/ecki/9f69773eb29428a36077
> 
> What can be seen is, that with a good distribution of hash keys 8 looks
> faster than 7, and with a bad distribution of hash keys Java 7 is
> faster (unless you supply a Comparator for the key). (and a good distributed hashkey with comparable seems to be a bit slower)
> 
> I think the regression is somewhat expected, but I guess its not widely
> known.
> 
> (I do not use a cached hashcode, but it has a nearly trivial implementation just to make it more life like. the tests also compares different initial sizes, but they do not have
> an measurable effect on the performance, I show only default size below:)
> 
> java version "1.7.0_72"
> 
> Benchmark                      (initialSize) Mode Samp Score    Error Units
> n.e.j.h.HashMapCollision.badDistNoComp 16    avgt 4   10847,318 ± 5596,690 ms/op
> n.e.j.h.HashMapCollision.badDistWithComp 16  avgt 4   10761,430 ± 5376,975 ms/op
> n.e.j.h.HashMapCollision.goodDistNoComp 16   avgt 4    3613,923 ± 254,823 ms/op
> n.e.j.h.HashMapCollision.goodDistWithComp 16 avgt 4    3656,229 ± 274,350 ms/op
> 
> 
> java version "1.8.0_25"
> 
> Benchmark                      (initialSize) Mode Samp Score     Error Units
> n.e.j.h.HashMapCollision.badDistNoComp 16    avgt 4    14309,880 ± 1811,709 ms/op <-slower
> n.e.j.h.HashMapCollision.badDistWithComp 16  avgt 4     8232,037 ± 5974,530 ms/op
> n.e.j.h.HashMapCollision.goodDistNoComp 16   avgt 4     3304,698 ± 116,866 ms/op
> n.e.j.h.HashMapCollision.goodDistWithComp 16 avgt 4     3425,762 ± 107,659 ms/op
> 
> 
> Greetings
> Bernd