RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size (original) (raw)

Doug Lea dl at cs.oswego.edu
Fri Jul 4 19:38:34 UTC 2014

On 07/04/2014 01:33 PM, Ivan Gerasimov wrote:

On 04.07.2014 8:14, David Holmes wrote:

Hi Ivan,

I find the change to capacity somewhat obfuscating and I can't see what the actual bug was. The bug was in rounding in the expression minCapacity = (3 * expectedMaxSize)/2. Suppose, we want the expected size to be 11, then minCapacity becomes (int)(11 * 3 / 2) == 16. The threshold is calculated later to be (int)(16 * 2 / 3) == 10, which is less than expected size 11.

So the bug report was based on someone noticing that with odd-valued sizes, the undocumented 2/3 target load was rounded down, not up, which they didn't like?

I don't object to rounding it up and modernizing the size calculations to use highestOneBit, but it's a weak pretense :-)

To address the issue I combined the division by 2 with the rounding up to the nearest power of two. I also took a chance to replace a while-loop with a single call to the highestOneBit method, which calculates exactly what we need here.

The recursive call to put after a resize seems very sub-optimal as you will re-search the map for the non-existent key. Can you not just recompute the correct indices and do the store?

The initial rationale for post-insert-resize was to avoid these issues given the need to preserve at least one empty slot. Which I expect to remain faster than pre-resize even with your modified patch. Please provide systematic performance comparisons before committing!

-Doug

More information about the core-libs-dev mailing list