harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Nathan Beyer" <ndbe...@apache.org>
Subject Re: [classlib][luni][performance] Improvements in Collections
Date Fri, 18 Apr 2008 19:04:16 GMT
Yes, I'm well aware of all of hashing algorithms. I'm talking about the
patches --- the code in the patch wasn't clear. I'm very particular about
what code does and what is says it does.

In any case, didn't you just comment that this capacity rounding WAS NOT
what gives the performance boost? I'm confused.

-Nathan

On Fri, Apr 18, 2008 at 1:59 PM, Aleksey Shipilev <
aleksey.shipilev@gmail.com> wrote:

> Nathan,
>
> I'm afraid you had messed up two things: "computing the n-th power of
> 2" and "rounding to next power of 2". First one could be implemented
> using Math.pow(...), while second does not. This method is essential
> part of the issue since it provides the rounding facility that is used
> further for performance optimization.
>
> There is nice Wikipedia article on hash tables describing load factor
> and its impact on performance: http://en.wikipedia.org/wiki/Hash_table
>
> Thanks,
> Aleksey.
>
> On Fri, Apr 18, 2008 at 10:40 PM, Nathan Beyer <ndbeyer@apache.org<https://mail.google.com/mail?view=cm&tf=0&to=ndbeyer@apache.org>>
> wrote:
> > BTW - I wasn't suggesting moving this to Math, I was asking why write a
> >  method for executing a 2^K that's already in Math [1]. I'm not keen on
> >  optimizing things in an language that's compiled to an interpreted
> bytecode
> >  -- that's the whole point of JITs. Keep the code clean, correct and
> easy to
> >  maintain.
> >
> >  [1]
> >
> http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Math.html#pow(double,%20double)<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Math.html#pow%28double,%20double%29>
> >
> >  On Fri, Apr 18, 2008 at 12:10 PM, Aleksey Shipilev <
> >
> > aleksey.shipilev@gmail.com<https://mail.google.com/mail?view=cm&tf=0&to=aleksey.shipilev@gmail.com>>
> wrote:
> >
> >  > Nathan,
> >  >
> >
> > > The method name is inaccurate, right, it can be named like you want.
> >  > The reason of performance boost _is_not_ in this method (nevertheless
> >  > this method probably is fastest available for rounding). This method
> >  > is utility and I see no point in moving it to Math.
> >  >
> >  > The reason of the performance boost is:
> >  > > On Fri, Apr 18, 2008 at 11:51 AM, Aleksey Shipilev <
> >  > aleksey.shipilev@gmail.com<https://mail.google.com/mail?view=cm&tf=0&to=aleksey.shipilev@gmail.com>
> <https://mail.google.com/mail?view=cm&tf=0&to=aleksey.shipilev@gmail.com>>
> >
> > > wrote:
> >  > >> I'm pushing the idea that
> >  > >> this optimization is general because it moves long-latency modulo
> (%)
> >  > >> operations to really cheap mask (&), but to guarantee this, we
> should
> >  > >> guarantee the storage is 2^k, where k is 0..N.
> >  >
> >  > Thanks,
> >  > Aleksey.
> >  >
> >
> > > On Fri, Apr 18, 2008 at 9:03 PM, Nathan Beyer <ndbeyer@apache.org<https://mail.google.com/mail?view=cm&tf=0&to=ndbeyer@apache.org>
> <https://mail.google.com/mail?view=cm&tf=0&to=ndbeyer@apache.org>>
> >  > wrote:
> >  > > So the method 'roundTo2k' is incorrectly named, then? Should it be
> >  > >  'roundTo2ToTheK'? Isn't there a Math method that should be used to
> do
> >  > this,
> >  > >  which in turn should be the focus of optimization? I'd rather see
> such
> >  > a
> >  > >  "general" optimization pushed into Math and then have all of the
> >  > XHashMap
> >  > >  implementations use the Math methods consistently.
> >  > >
> >  > >  -Nathan
> >  > >
> >  > >  On Fri, Apr 18, 2008 at 11:51 AM, Aleksey Shipilev <
> >  > >
> >  > > aleksey.shipilev@gmail.com<https://mail.google.com/mail?view=cm&tf=0&to=aleksey.shipilev@gmail.com>
> <https://mail.google.com/mail?view=cm&tf=0&to=aleksey.shipilev@gmail.com>>
> >
> >
> > > wrote:
> >  > >
> >  > >
> >  > > > Nathan,
> >  > >  >
> >  > >  > I think we have a sort of misunderstanding here. I'm not
> rounding to
> >  > >  > 2000, rather I round to next power of 2. I'm pushing the idea
> that
> >  > >  > this optimization is general because it moves long-latency
> modulo (%)
> >  > >  > operations to really cheap mask (&), but to guarantee this,
we
> should
> >  > >  > guarantee the storage is 2^k, where k is 0..N.
> >  > >  >
> >  > >  > Thanks,
> >  > >  > Aleksey.
> >  > >  >
> >  > >  > On Fri, Apr 18, 2008 at 8:44 PM, Nathan Beyer <
> ndbeyer@apache.org<https://mail.google.com/mail?view=cm&tf=0&to=ndbeyer@apache.org>
> <https://mail.google.com/mail?view=cm&tf=0&to=ndbeyer@apache.org>
> >  > <https://mail.google.com/mail?view=cm&tf=0&to=ndbeyer@apache.org>>
> >  > >
> >  > >
> >  > > > wrote:
> >  > >  > >  I'm sure this optimization shows an improvement in the
> >  > serialization
> >  > >  > use
> >  > >  > >  case, but you'd be hard pressed to say that this improvement
> will
> >  > make
> >  > >  > 80%
> >  > >  > >  of all uses of HashMap, WeakHashMap and IdentityHashMap
> better. If
> >  > you
> >  > >  > want
> >  > >  > >  to round to 2000 to improve serialization, then do that in
> the
> >  > >  > >  serialization.
> >  > >  > >
> >  > >  > >  I don't think this should be applied as is.
> >  > >  > >
> >  > >  > >  -Nathan
> >  > >  > >
> >  > >  >
> >  > >
> >  >
> >
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message