Mailing-List: contact dev-help@harmony.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@harmony.apache.org
Received-SPF: pass (athena.apache.org: domain of sergey.i.salishev@gmail.com
 designates 74.125.46.157 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=message-id:date:from:to:subject:in-reply-to:mime-version:content-type:references;
        b=pjqw1imgEPdHIZkq16Ev4T8y6DN9dpixWnkx+LU3tDD3r2fST43vty+hDSLFCv9GeQBNXV3xxIp7WBGgz0+GRnhod1gz0qiy00g4vn5t/wZNeYyU7EQzpRCrQDkVI5SAQZ1oAS2BooyDDsa0D+2x+CSMk721yyQ78h3ZaKP7IOk=
Message-ID: <728dc7fa0804181201n9debd8i4ea43f1e95bf236f@mail.gmail.com>
Date: Fri, 18 Apr 2008 23:01:27 +0400
From: "Sergey Salishev" <sergey.i.salishev@gmail.com>
To: dev@harmony.apache.org
Subject: Re: [classlib][luni][performance] IdentityHashMap implementation
In-Reply-To: <4bebff790804181153w61231384y436c4c4aa9500ba4@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----=_Part_3113_19993128.1208545287142"
References: <4bebff790804181153w61231384y436c4c4aa9500ba4@mail.gmail.com>

------=_Part_3113_19993128.1208545287142
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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 <
aleksey.shipilev@gmail.com> 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
>

------=_Part_3113_19993128.1208545287142--