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

[Ivan Gerasimov]

Thanks Martin!

On 03.07.2014 21:12, Martin Buchholz wrote:
> Martin's law of expanding capacity:
>
> Always grow by using the form
>
> newCapacity = oldCapacity + oldCapacity >> n
>
> for some suitable constant n.  This will be efficient and more 
> overflow resistant than the alternative
>
> newCapacity = oldCapacity * (2**n + 1) / (2**n)
>
> Here n == 1.
>

More precisely here n == 0, because the capacity gets doubled when 
increased.

The formula cap = expSize * 3 / 2 is used to estimate the capacity based 
on the expected number of the items to be inserted.

Sincerely yours,
Ivan

>
> On Thu, Jul 3, 2014 at 9:00 AM, Ivan Gerasimov 
> <ivan.gerasimov at oracle.com <mailto:ivan.gerasimov at oracle.com>> wrote:
>
>     Hello!
>
>     IdentityHasMap has a couple of small issues.
>     The first one is a performance issue: If you create a map,
>     specifying 42 as the expected number of element, you'll be able to
>     insert only 41 elements into the preallocated table. Inserting the
>     42th element will trigger resizing of the storage.
>
>     Another issue is that resizing occurs only after the element
>     insertion.
>     In the extreme case it can lead to the situation when the element
>     is successfully inserted and then en exception is thrown due the
>     map been unable to grow.
>
>     Would you please help review the fix?
>
>     BUGURL: https://bugs.openjdk.java.net/browse/JDK-6904367
>     WEBREV: http://cr.openjdk.java.net/~igerasim/6904367/0/webrev/
>     <http://cr.openjdk.java.net/%7Eigerasim/6904367/0/webrev/>
>
>     Sincerely yours,
>     Ivan
>
>