Yep, I second that.
On Fri, Apr 18, 2008 at 11:01 PM, Sergey Salishev <[EMAIL PROTECTED]> wrote: > Hi, > > It also should be noticed that replacing the IdentityHashMap with HashMap in > Thread impl gives 4.5x boost on ThreadLocalBench. > > Thanks. > Sergey. > > > > On Fri, Apr 18, 2008 at 10:53 PM, Aleksey Shipilev < > [EMAIL PROTECTED]> wrote: > > > Hi there, > > > > I had instrumented the current implementation of j.u.IdentityHashMap > > and ran it through ThreadLocalBench and SerialBench. Surprisingly, the > > collision rate there (frequency of sutiations when objects have > > identical identityHashCode) is rather high - 8 collisions per one > > get() on average with load factor of 0.75. > > > > That mean identityHashCode does not disperse elements well and the > > map's performance is subject to clustering. Moreover, the collision > > chains are sometimes so big that they're covering a half of storage > > array and IHM looses access performance degrading to linear search. > > And also the performance of essentially the same IHMs (in terms of > > contents) may vary because of different clustering layouts. > > > > That's essentially the disadvantage of open-addressed hash tables and > > there are known ways to overwhelm this problem [1]. But before > > actually researching on this topic I need to answer some > > "java-spec-legal" questions: > > 1. Is it required for IdentityHashMap to use open addressing? > > 2. Is it required for IdentityHashMap to use linear probing as > > collision resolution scheme? > > 3. What's the reason of having the separate implementation of > > IdentityHashMap while it can be implemented with overriding of > > "equality" operation in ordinary HashMap? > > 4. Can identityHashCode be salted with some additional hash to break > > clustering? > > > > I'm actually interested in performance optimization of IHM, so I will > > appreciate anyone comments on this topic. > > > > Thanks, > > Aleksey. > > > > [1] http://en.wikipedia.org/wiki/Hash_table > > >
