harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Aleksey Shipilev" <aleksey.shipi...@gmail.com>
Subject Re: [classlib][luni][performance] Improvements in Collections
Date Fri, 18 Apr 2008 18:59:58 GMT
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> 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)
>
>  On Fri, Apr 18, 2008 at 12:10 PM, Aleksey Shipilev <
>
> 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>>
>
> > 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>>
>  > 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>>
>
>
> > 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>>
>  > >
>  > >
>  > > > 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
View raw message