RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size
Ivan Gerasimov
ivan.gerasimov at oracle.com
Tue Jul 8 11:53:02 UTC 2014
On 08.07.2014 15:25, Peter Levart wrote:
> Hi again,
>
> Here's a version with (3*size > len) replaced with (size > len/3) as
> suggested by Ivan Gerasimov to avoid overflow and also fixed if block
> if put() that enclosed too much code (in my changed version of
> Martin's latest webrev):
>
It shouldn't be needed, since size < MAXIMUM_CAPACITY-1 at this point.
> http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.02/
>
> I don't think there's a danger of overflow in capacity() since
> (expectedMaxSize + (expectedMaxSize << 1)) is evaluated only if
> expectedMaxSize <= MAXIMUM_CAPACITY / 3;
>
> Here's a diff to latest Martin's version:
>
> *** src/share/classes/java/util/IdentityHashMap.java.mb 2014-07-08
> 12:37:57.267916926 +0200
> --- src/share/classes/java/util/IdentityHashMap.java 2014-07-08
> 13:05:46.351810826 +0200
> ***************
> *** 437,449 ****
>
> if (size == MAXIMUM_CAPACITY - 1)
> throw new IllegalStateException("Capacity exhausted.");
> modCount++;
> tab[i] = k;
> tab[i + 1] = value;
> size++;
> - int x = size + (size << 1); // Optimized form of 3 * size
> - if (x > len)
> - resize(len); // len == 2 * current capacity.
> return null;
> }
>
> --- 437,454 ----
>
> if (size == MAXIMUM_CAPACITY - 1)
> throw new IllegalStateException("Capacity exhausted.");
> +
> + if (size >= len / 3 && resize(len)) { // len == 2 * current
> capacity.
> + tab = table;
> + len = tab.length;
> + i = hash(key, len);
> + while (tab[i] != null)
> + i = nextKeyIndex(i, len);
> + }
> modCount++;
> tab[i] = k;
> tab[i + 1] = value;
> size++;
> return null;
> }
>
> ***************
> *** 452,468 ****
> *
> * @param newCapacity the new capacity, must be a power of two.
> */
> ! private void resize(int newCapacity) {
> // assert (newCapacity & -newCapacity) == newCapacity; //
> power of 2
> int newLength = newCapacity * 2;
>
> Object[] oldTable = table;
> int oldLength = oldTable.length;
> if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any
> further
> ! return;
> }
> if (oldLength >= newLength)
> ! return;
>
> Object[] newTable = new Object[newLength];
>
> --- 457,473 ----
> *
> * @param newCapacity the new capacity, must be a power of two.
> */
> ! private boolean resize(int newCapacity) {
> // assert (newCapacity & -newCapacity) == newCapacity; //
> power of 2
> int newLength = newCapacity * 2;
>
> Object[] oldTable = table;
> int oldLength = oldTable.length;
> if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any
> further
> ! return false;
> }
> if (oldLength >= newLength)
> ! return false;
>
> Object[] newTable = new Object[newLength];
>
> ***************
> *** 480,485 ****
> --- 485,491 ----
> }
> }
> table = newTable;
> + return true;
> }
>
> /**
> ***************
> *** 494,500 ****
> int n = m.size();
> if (n == 0)
> return;
> ! if (n + (n << 1) > table.length) // conservatively pre-expand
> resize(capacity(n));
>
> for (Entry<? extends K, ? extends V> e : m.entrySet())
> --- 500,506 ----
> int n = m.size();
> if (n == 0)
> return;
> ! if (n > table.length / 3) // conservatively pre-expand
> resize(capacity(n));
>
> for (Entry<? extends K, ? extends V> e : m.entrySet())
>
>
> Regards, Peter
>
> On 07/08/2014 12:41 PM, Peter Levart wrote:
>> On 07/08/2014 12:12 PM, Peter Levart wrote:
>>> On 07/08/2014 09:33 AM, Martin Buchholz wrote:
>>>> I've updated the webrev
>>>> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity/
>>>>
>>>> It now has all my TODOs done.
>>>> The test case has been testng-ified.
>>>
>>> Hi Martin,
>>>
>>> What happened to the desire that when OOME is thrown on resizing,
>>> IHM is left unchanged?
>>>
>>> Regards, Peter
>>
>> Hi Martin,
>>
>> I took your latest version of the patch and modified it a little:
>>
>> http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.01/
>>
>> Here's a diff to your version:
>>
>> *** src/share/classes/java/util/IdentityHashMap.java.mb 2014-07-08
>> 12:37:57.267916926 +0200
>> --- src/share/classes/java/util/IdentityHashMap.java 2014-07-08
>> 12:34:25.739767669 +0200
>> ***************
>> *** 437,449 ****
>>
>> if (size == MAXIMUM_CAPACITY - 1)
>> throw new IllegalStateException("Capacity exhausted.");
>> ! modCount++;
>> ! tab[i] = k;
>> ! tab[i + 1] = value;
>> ! size++;
>> ! int x = size + (size << 1); // Optimized form of 3 * size
>> ! if (x > len)
>> ! resize(len); // len == 2 * current capacity.
>> return null;
>> }
>>
>> --- 437,457 ----
>>
>> if (size == MAXIMUM_CAPACITY - 1)
>> throw new IllegalStateException("Capacity exhausted.");
>> !
>> ! int x = size + (size << 1) + 3; // Optimized form of 3 *
>> (size + 1)
>> ! if (x > len) {
>> ! if (resize(len)) { // len == 2 * current capacity.
>> ! tab = table;
>> ! len = tab.length;
>> ! i = hash(key, len);
>> ! while (tab[i] != null)
>> ! i = nextKeyIndex(i, len);
>> ! }
>> ! modCount++;
>> ! tab[i] = k;
>> ! tab[i + 1] = value;
>> ! size++;
>> ! }
>> return null;
>> }
>>
>> ***************
>> *** 452,468 ****
>> *
>> * @param newCapacity the new capacity, must be a power of two.
>> */
>> ! private void resize(int newCapacity) {
>> // assert (newCapacity & -newCapacity) == newCapacity; //
>> power of 2
>> int newLength = newCapacity * 2;
>>
>> Object[] oldTable = table;
>> int oldLength = oldTable.length;
>> if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand
>> any further
>> ! return;
>> }
>> if (oldLength >= newLength)
>> ! return;
>>
>> Object[] newTable = new Object[newLength];
>>
>> --- 460,476 ----
>> *
>> * @param newCapacity the new capacity, must be a power of two.
>> */
>> ! private boolean resize(int newCapacity) {
>> // assert (newCapacity & -newCapacity) == newCapacity; //
>> power of 2
>> int newLength = newCapacity * 2;
>>
>> Object[] oldTable = table;
>> int oldLength = oldTable.length;
>> if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand
>> any further
>> ! return false;
>> }
>> if (oldLength >= newLength)
>> ! return false;
>>
>> Object[] newTable = new Object[newLength];
>>
>> ***************
>> *** 480,485 ****
>> --- 488,494 ----
>> }
>> }
>> table = newTable;
>> + return true;
>> }
>>
>> /**
>>
>>
>> Regards, Peter
>>
>>>
>>>>
>>>> On Mon, Jul 7, 2014 at 6:54 PM, Ivan Gerasimov
>>>> <ivan.gerasimov at oracle.com>
>>>> wrote:
>>>>
>>>>> Unfortunately, x + x << 1 causes the same overflow bug as 3*x:
>>>>>
>>>> x + (x << 1) is merely supposed to be possibly more efficient than
>>>> 3*x.
>>>>
>>>>
>>>>> (int)(1431655766 + 1431655766 << 1) == 2
>>>>>
>>>> OK, I think my latest version doesn't have any overflow bugs.
>>>
>>
>
>
>
More information about the core-libs-dev
mailing list