RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size
Peter Levart
peter.levart at gmail.com
Tue Jul 8 11:25:18 UTC 2014
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):
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