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 < [EMAIL PROTECTED]> 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 <[EMAIL > PROTECTED]<https://mail.google.com/mail?view=cm&tf=0&[EMAIL PROTECTED]>> > 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 < > > > > [EMAIL PROTECTED]<https://mail.google.com/mail?view=cm&tf=0&[EMAIL > > PROTECTED]>> > 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 < > > > [EMAIL PROTECTED]<https://mail.google.com/mail?view=cm&tf=0&[EMAIL > > PROTECTED]> > <https://mail.google.com/mail?view=cm&tf=0&[EMAIL PROTECTED]>> > > > > > 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 <[EMAIL > > > PROTECTED]<https://mail.google.com/mail?view=cm&tf=0&[EMAIL PROTECTED]> > <https://mail.google.com/mail?view=cm&tf=0&[EMAIL PROTECTED]>> > > > 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 < > > > > > > > > [EMAIL PROTECTED]<https://mail.google.com/mail?view=cm&tf=0&[EMAIL > > PROTECTED]> > <https://mail.google.com/mail?view=cm&tf=0&[EMAIL PROTECTED]>> > > > > > > > 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 < > [EMAIL PROTECTED]<https://mail.google.com/mail?view=cm&tf=0&[EMAIL PROTECTED]> > <https://mail.google.com/mail?view=cm&tf=0&[EMAIL PROTECTED]> > > > <https://mail.google.com/mail?view=cm&tf=0&[EMAIL PROTECTED]>> > > > > > > > > > > > > > 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 > > > > > > > > > > > > > > > > > > > > >
