RFR: : (coll) IdentityHashMap is resized before exceeding the expected maximum size
peter.levart at gmail.com
Sun Jul 13 22:10:16 UTC 2014
On 07/13/2014 12:41 AM, Peter Levart wrote:
> On 07/12/2014 10:46 PM, Ivan Gerasimov wrote:
>> Peter, seems you need to fix capacity():
>> int capacity = Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
>> does not necessarily produces a negative number in the case of overflow.
> Good catch. You're right.
> So here's a better variant:
> return Math.min(
> expectedMaxSize > Integer.MAX_VALUE / 3
> ? MAXIMUM_CAPACITY // 3 * expectedMaxSize would
> : Integer.highestOneBit(expectedMaxSize +
> (expectedMaxSize << 1))
Incorporated in new webrev:
Also in this webrev: changing the condition by which putAll() decides to
call resize() makes a boolean return from resize() unnecessary again,
since it's only called when resize is actually needed (from put() when
3*size reaches 2*capacity, from putAll(), when capacity calculated from
argument map's size is greater than current capacity). Retry loop in
put() can be simplified consequently.
>> Sincerely yours,
>> On 12.07.2014 22:12, Peter Levart wrote:
>>> On 07/12/2014 05:47 PM, Peter Levart wrote:
>>>> If we're willing to pay the price of special-casing the
>>>> non-power-of-2 MAX_CAPACITY = (1 << 29) + (1 << 28), which amounts
>>>> to approx. 4% of performance,
>>>> Then here's a possible solution:
>>> Two fixes:
>>> One is a fix for possible overflow in resize() + rearrangement
>>> (which is specific to my proposal) and the other is replacement of
>>> condition that triggers resize in put() from (3*size > length) to
>>> (3*size >= length). The later should be applied to Martin's latest
>>> version too, I think, if it is decided that my proposal is inadequate.
>>> Why is (3*size >= length) more appropriate condition to trigger
>>> resize? Because it is more aligned with capacity(size) function
>>> which is basically a clamped Integer.highestOneBit(3 * size).
>>> Map preallocation makes a table with length = 2 *
>>> (3 * size < 2 * highestOneBit(3*size)) is true for any size, so IHM
>>> will never be resized if filled with size elements and table was
>>> preallocated with length =
>>> 2 * highestOneBit(3*size) even if condition for resizing is changed
>>> from (3*size > length) to (3*size >= length). Current condition
>>> sometimes resizes a little to late when preallocation would already
>>> create a bigger table.
>>> Now if we change that, my proposed webrev.07 does not need
>>> MAXIMUM_SIZE constant any more. Attempt to insert the 2^29-th
>>> element (when size is about to become 2^29) triggers resize since at
>>> that time length == 2 * MAXIMUM_CAPACITY which is exactly 3 * 2^29
>>> and this alone can be used as a trigger to throw OOME in resize()...
>>> Regards, Peter
More information about the core-libs-dev