HashMap collision speed (regression 7->8)
Bernd Eckenfels
ecki at zusammenkunft.net
Fri Jan 9 19:22:30 UTC 2015
Hello Brent,
thank you for digging that out! It describes basically what is
documented in the javadoc as well. Having 8 colliding keys is regarded
as extremly rare when hashCode is poision distributed. From that point
of view using this threshold makes sense.
However it was not checked (at least I havent seen it in the archive) to
what point a linear search is faster implemented as the treeifying
(especially if it is known the keys wont sort very nicely anyway). At
least I could not see it in the discussions.
I would think this aspect needs a bit of thought as well, now that
the bit scrambeling is removed. But it is not only about attackers
trying to provoke that, it seems to me (from the SO question and other
discussions) that there is unfortunatelly some bad hashCode() out there.
My naive suggestion would be to delay the treeifying a bit longer if
the hash keys are not Compareable and the hash tables are large(er).
Gruss
Bernd
Am Fri, 09 Jan
2015 10:31:52 -0800 schrieb Brent Christian
<brent.christian at oracle.com>:
> Hi, Bernd
>
> The initial discussion of the change that set TREEIFY_THRESHOLD to 8
> (it was initially 16) can be read here:
>
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-July/018685.html
>
> ...continuing here...
>
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-August/019853.html
>
>
> The code review discussion is archived here:
>
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-August/020131.html
>
> -Brent
>
> On 1/8/15 4:10 PM, Bernd Eckenfels wrote:
> > Hello Vitaly,
> >
> > the TREEIFY_THRESHOLD in HashMap is 8 (6 for UNTREEIFY). Not sure if
> > there have been benchmarks for this, I dont see an justification in
> > the source comments. There is a comment, that it is expected to
> > waste a factor of two time and space when not compareable.
> >
> > I would also expect that larger thresholds make sense (especially
> > when key is not compareable).
> >
> > The JEP 180 also does not mention results from the benchmarks, maybe
> > somebody knows details?
> >
> > http://openjdk.java.net/jeps/180
> >
> > Gruss
> > Bernd
> >
> >
> > Am Thu, 8 Jan 2015 18:38:53 -0500
> > schrieb Vitaly Davidovich <vitalyd at gmail.com>:
> >
> >> Hmmm, 15 entries doesn't seem like a large enough number to drop
> >> linear search. I'd have expected something like 60-80 entries (in
> >> some binary vs linear search benchmarks I've come across, that
> >> seems to be crossover point). It's hard to beat linear search for
> >> small sets when the comparison function is dirt cheap.
> >>
> >> Sent from my phone
> >> On Jan 8, 2015 6:25 PM, "Bernd Eckenfels" <ecki at zusammenkunft.net>
> >> wrote:
> >>
> >>> Hello Peter,
> >>>
> >>> hm not sure what you mean, i was not suggesting the regression is
> >>> caused by simpler hashCode bits. (do you mean my comment about the
> >>> removed randomizer? that is not a problem for the benchmark, but
> >>> it might be an opportunity for DOS (again)).
> >>>
> >>> I think the regression itself is caused by the fact that a tree is
> >>> used instead of the linear search. The benchmark does colide
> >>> heavily, but only places 15 or so entries in one bucket. This is
> >>> enough to trigger the migration from linear search to tree, but
> >>> not enough to hurt for linear search performance (at least I
> >>> think this is the case).
> >>>
> >>> The way the nodes are constructed they actually do sort pretty
> >>> good if compareable is implemented. It would most likely not help
> >>> if Compareable cannot distinguish more than hashCode would.
> >>>
> >>> Gruss
> >>> Bernd
> >>>
> >>>
> >>>
> >>> Am Thu, 08 Jan 2015 23:10:10 +0100
> >>> schrieb Peter Levart <peter.levart at gmail.com>:
> >>>
> >>>> Bernd,
> >>>>
> >>>> I tried to change the "comparableClassFor" myself and it didn't
> >>>> work (HashMap is used very early in boot-up sequence and
> >>>> initializing ClassValue at that time triggers a NPE).
> >>>>
> >>>> Anyway, caching of "comparableClassFor" result would only
> >>>> potentially improve the "badDistWithComp" result. But can not
> >>>> improve "badDistNoComp" which is the one with speed regression as
> >>>> you're benchmark suggests.
> >>>>
> >>>> But your feeling that this is caused by "simpler" hashCode bits
> >>>> spreading function is not correct. I tried to replace the hash()
> >>>> method with the one that was in HM before and I get comparable
> >>>> results. This is the JDK8 HashMap.hash() method:
> >>>>
> >>>> static final int hash(Object key) {
> >>>> int h;
> >>>> return (key == null) ? 0 : (h = key.hashCode()) ^ (h
> >>>> >>> 16); }
> >>>>
> >>>> Benchmark (initialSize) Mode
> >>>> Samples Score Score error Units
> >>>> j.t.HashMapCollision.badDistNoComp 16 avgt 4
> >>>> 3171.264 1152.995 ms/op
> >>>> j.t.HashMapCollision.badDistWithComp 16 avgt 4
> >>>> 2819.342 422.861 ms/op
> >>>> j.t.HashMapCollision.goodDistNoComp 16 avgt 4
> >>>> 1026.064 72.049 ms/op
> >>>> j.t.HashMapCollision.goodDistWithComp 16 avgt 4
> >>>> 1025.312 39.858 ms/op
> >>>>
> >>>>
> >>>> ...and this is my re-interpretation of pre JDK8 HashMap.hash():
> >>>>
> >>>>
> >>>> static final int randomHash =
> >>>> mix32(System.currentTimeMillis() ^ System.nanoTime());
> >>>>
> >>>> private static int mix32(long z) {
> >>>> z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;
> >>>> return (int)(((z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L)
> >>>> >>> 32); }
> >>>>
> >>>> static final int hash(Object k) {
> >>>> int h = k == null ? randomHash : randomHash ^
> >>>> k.hashCode();
> >>>>
> >>>> // This function ensures that hashCodes that differ
> >>>> only by // constant multiples at each bit position have a bounded
> >>>> // number of collisions (approximately 8 at default
> >>>> load factor). h ^= (h >>> 20) ^ (h >>> 12);
> >>>> return h ^ (h >>> 7) ^ (h >>> 4);
> >>>> }
> >>>>
> >>>> Benchmark (initialSize) Mode
> >>>> Samples Score Score error Units
> >>>> j.t.HashMapCollision.badDistNoComp 16 avgt 4
> >>>> 3257.348 1079.088 ms/op
> >>>> j.t.HashMapCollision.badDistWithComp 16 avgt 4
> >>>> 2866.740 414.687 ms/op
> >>>> j.t.HashMapCollision.goodDistNoComp 16 avgt 4
> >>>> 1041.068 99.370 ms/op
> >>>> j.t.HashMapCollision.goodDistWithComp 16 avgt 4
> >>>> 1041.653 53.925 ms/op
> >>>>
> >>>>
> >>>> Your benchmark does not show much difference. Perhaps the
> >>>> regression for "badDistNoComp" case could be caused by the fact
> >>>> that with really bad hashCode and no Comparable interface, the
> >>>> red-black tree becomes less performant to search than a simple
> >>>> linked list of Nodes...
> >>>>
> >>>>
> >>>> Regards, Peter
> >>>>
> >>>>
> >>>>
> >>>>
> >>>>
> >>>> On 01/08/2015 08:41 PM, Bernd Eckenfels wrote:
> >>>>> Hello Peter,
> >>>>>
> >>>>> yes it is only keys without an Compareable interface, but they
> >>>>> are quite common. I think the main problem with the internal
> >>>>> comparator (based on instance identity) is, that it would work
> >>>>> for looking up the same instance again, but not for the case
> >>>>> where the actual instance is re-created (as in my example code).
> >>>>>
> >>>>> I would love to test your modified code, but I don't have a
> >>>>> OpenJDK build environment handy. Or actually I can try to get
> >>>>> one, is there somewhere a Virtulisation or Cloud Image
> >>>>> available which is pre-installed?
> >>>>>
> >>>>> I have (1.6) a compiled benchmark.jar here, in case anyone
> >>>>> wants to try it:
> >>>>>
> >>>>>
> >>> https://onedrive.live.com/redir?resid=A98B6F4E09966AFD!20440&authkey=!AFFk03-5jq21Xz0&ithint=file%2cjar
> >>>>>
> >>>>> BTW: I am (as usual) not expecting commoents on that, but just
> >>>>> to mention it: the expected good behavior of degenerated
> >>>>> hashmaps (due to the tree) was reason for removing the hashcode
> >>>>> secret randomization. I wonder if that was such a good idea if
> >>>>> colliding lookups (with more than a handfull of entries in a
> >>>>> bucket) have this 50% penalty.
> >>>>>
> >>>>> Greetings
> >>>>> Bernd
> >>>>>
> >>>>>
> >>>>>
> >>>>> Am Thu, 08 Jan 2015 20:22:13 +0100
> >>>>> schrieb Peter Levart <peter.levart at gmail.com>:
> >>>>>
> >>>>>> Hi Bernd,
> >>>>>>
> >>>>>> It seems that only bad hash codes (without comparable keys) in
> >>>>>> JDK8 HM are worse than JDK7 HM.
> >>>>>>
> >>>>>>
> >>>>>> Since you have already taken time to measure JDK7 vs JDK8 HM,
> >>>>>> could you try to take the JDK8 source and just replace the
> >>>>>> internal "comparableClassFor" method with the following
> >>>>>> implementation:
> >>>>>>
> >>>>>> static final ClassValue<Boolean> selfComparable = new
> >>>>>> ClassValue<Boolean>() {
> >>>>>> @Override
> >>>>>> protected Boolean computeValue(Class<?> c) {
> >>>>>> Type[] as; ParameterizedType p;
> >>>>>> for (Type t : c.getGenericInterfaces()) {
> >>>>>> if (t instanceof ParameterizedType &&
> >>>>>> (p = (ParameterizedType) t).getRawType()
> >>>>>> == Comparable.class &&
> >>>>>> (as = p.getActualTypeArguments()).length
> >>>>>> == 1 && as[0] == c) // type arg is c
> >>>>>> return true;
> >>>>>> }
> >>>>>> return false;
> >>>>>> }
> >>>>>> };
> >>>>>>
> >>>>>> static Class<?> comparableClassFor(Object x) {
> >>>>>> if (x instanceof Comparable) {
> >>>>>> Class<?> c = x.getClass();
> >>>>>> if (c == String.class || selfComparable.get(c))
> >>>>>> { return c;
> >>>>>> }
> >>>>>> }
> >>>>>> return null;
> >>>>>> }
> >>>>>>
> >>>>>>
> >>>>>> ...and retry your measurements. I just want to see if it has
> >>>>>> any impact.
> >>>>>>
> >>>>>>
> >>>>>> Thanks, Peter
> >>>>>>
> >>>>>>
> >>>>>> On 01/08/2015 05:38 PM, Bernd Eckenfels 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
> >>>>
> >>>>
> >>>
> >>
> >
More information about the core-libs-dev
mailing list