Return-Path: Delivered-To: apmail-harmony-dev-archive@www.apache.org Received: (qmail 35508 invoked from network); 18 Apr 2008 17:57:32 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.2) by minotaur.apache.org with SMTP; 18 Apr 2008 17:57:32 -0000 Received: (qmail 8084 invoked by uid 500); 18 Apr 2008 17:57:32 -0000 Delivered-To: apmail-harmony-dev-archive@harmony.apache.org Received: (qmail 8059 invoked by uid 500); 18 Apr 2008 17:57:32 -0000 Mailing-List: contact dev-help@harmony.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@harmony.apache.org Delivered-To: mailing list dev@harmony.apache.org Received: (qmail 8050 invoked by uid 99); 18 Apr 2008 17:57:32 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 18 Apr 2008 10:57:32 -0700 X-ASF-Spam-Status: No, hits=2.0 required=10.0 tests=HTML_MESSAGE,SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of sergey.i.salishev@gmail.com designates 74.125.46.153 as permitted sender) Received: from [74.125.46.153] (HELO yw-out-1718.google.com) (74.125.46.153) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 18 Apr 2008 17:56:40 +0000 Received: by yw-out-1718.google.com with SMTP id 4so412452ywq.0 for ; Fri, 18 Apr 2008 10:57:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:references; bh=Msy5S3RRVa2Muz4M6DEGXQ1omkHa8z1LmxlnA4qaYU0=; b=n0xurfDfNiRwhS+fNLWHspZocnwg7i4L+Q27c0exeGPmtaMcAlc9U3M92vo+U7YFfCHk9P2qePWvuSySv0QcBADeIlYLQ5Ycx+6/FdB+OKK0k6iKbhpWPlkoBHX198cNY+GM6aMmvvUKoMBOVmQgA/wtpEGmvhyFV1IzwDADDSw= 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=Jax1gSDnitVKpsYkYeA+ig4LLqPkKLNuhIP3c7HpQmwKRCG1M1vMGLb/5IxOTrLb5NCBnbvFsGiqk2Xg/cYdfXBoKrZAFkNYF6eTLad4dhQauVG4XSqkb6jagr+hbBHCiwY5uX6tj409dZtNrqWhmbA/Zq+zXsjJlbA4oLb8cyM= Received: by 10.150.135.2 with SMTP id i2mr3991698ybd.197.1208541420542; Fri, 18 Apr 2008 10:57:00 -0700 (PDT) Received: by 10.150.185.4 with HTTP; Fri, 18 Apr 2008 10:57:00 -0700 (PDT) Message-ID: <728dc7fa0804181057s3e82721cva72a3cf1f2150918@mail.gmail.com> Date: Fri, 18 Apr 2008 21:57:00 +0400 From: "Sergey Salishev" To: dev@harmony.apache.org Subject: Re: [classlib][luni][performance] Improvements in Collections In-Reply-To: <3b3f27c60804180955q1d2e7d89y8c00173618a46241@mail.gmail.com> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_2856_32068339.1208541420540" References: <4bebff790804172350r15419dd4v95e9c7a7adb8f14d@mail.gmail.com> <3b3f27c60804180913h214d861eqb4b937768d3b0bbf@mail.gmail.com> <728dc7fa0804180946y4a2ba333m9e7bba043b2942e@mail.gmail.com> <3b3f27c60804180955q1d2e7d89y8c00173618a46241@mail.gmail.com> X-Virus-Checked: Checked by ClamAV on apache.org ------=_Part_2856_32068339.1208541420540 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline Nathan I agree with you. This can be a problem. In my practice the biggest problems were with 1-2 sized hash maps taking 16 size arrays. Probably the best place to implement % optimization would bi CPU:) We can try the different approach. The HashMap growth is governed only by initial capacity so in the HashMap constructor one can say is 2^k or not. We can write something like final boolean powOf2 = isPowOf2(capacity); final int mod(int index, int length) { return powOf2? index & (length - 1) : index % length; } In theory the common path for the workload should be specialized by JIT. Ooops. When looking into HashMap code I've noticed someone already did this. https://issues.apache.org/jira/browse/HARMONY-4064 HashMap effectively does the rounding to the neares 2^k. Thanks. Sergey. On Fri, Apr 18, 2008 at 8:55 PM, Nathan Beyer wrote: > I know that people will notice; I have personal experience with systems > that > included custom Map implementations were written because HashMaps grew too > large for small data sets (less than 2000, actually) and wasted a lot of > memory for the unnecessary capacity. Even the use of the capacity and load > factor didn't provide enough compensation in these cases. > > -Nathan > > On Fri, Apr 18, 2008 at 11:46 AM, Sergey Salishev < > sergey.i.salishev@gmail.com> wrote: > > > Nathan, > > > > I don't think anyone will notice the hash map size rounding. It can lead > > to > > some memory overhead in very rare cases the user creates hash map with > the > > exact size. But in the most common case where the map is created with > > default size the rounding will not change the behavior at all as it's in > > agreement with the standard 2x growth policy. On the other hand size > > rounding gives substantial performance boost on all gets. > > > > Thanks. > > Sergey. > > > > > > On Fri, Apr 18, 2008 at 8:13 PM, Nathan Beyer https://mail.google.com/mail?view=cm&tf=0&to=ndbeyer@apache.org>> > > wrote: > > > > > https://issues.apache.org/jira/browse/HARMONY-5718 > > > > > > Again, I don't agree with the capacity rounding in the patch attached > to > > > this issue. I do like the change to the internal data structure; use > two > > > arrays for key/value instead a single array. It makes the code easier > to > > > read. > > > > > > -Nathan > > > > > > On Fri, Apr 18, 2008 at 1:50 AM, Aleksey Shipilev < > > > aleksey.shipilev@gmail.com< > https://mail.google.com/mail?view=cm&tf=0&to=aleksey.shipilev@gmail.com>> > > wrote: > > > > > > > Colleagues, > > > > > > > > I had recently filed two JIRAs with improvements in Collections, > > > > giving up to +30-40% to serialization benchmarks. Presumably they > will > > > > boost the performance across the all users since the optimization is > > > > pretty general: > > > > https://issues.apache.org/jira/browse/HARMONY-5761 > > > > https://issues.apache.org/jira/browse/HARMONY-5718 > > > > > > > > Would some classlib guru (Tim, Nathan, Tony?) review and commit > them? > > > > > > > > Thanks, > > > > Aleksey. > > > > > > > > > > ------=_Part_2856_32068339.1208541420540--