Details

Bug

Resolution: Fixed

P4

6u18

None

b23

x86

linux_2.6

Verified
Backports
Issue  Fix Version  Assignee  Priority  Status  Resolution  Resolved In Build 

JDK8065496  8u45  Ivan Gerasimov  P4  Resolved  Fixed  b01 
JDK8064413  8u40  Ivan Gerasimov  P4  Resolved  Fixed  b15 
JDK8070047  emb8u47  Ivan Gerasimov  P4  Resolved  Fixed  team 
JDK8194022  openjdk7u  Ivan Gerasimov  P4  Resolved  Fixed  master 
Description
There are two performance issues in IdentityHashMap causing that the map is resized (rehashed) before the number of entries exceeds the expected maximum.
The Javadoc of IdentityHashMap(int) specifies that "putting more than the expected number of keyvalue mappings into the map may cause the internal data structure to grow". Strictly taken, this statement does not promise that the internal data structure would not grow sooner, but I believe it was meant that way and that most developers understand it that way.
The fact is that the internal data structure may grow before the expected number of keyvalue mappings inserted into the map exceeds the expected number specified by the constructor's parameter. This is the case if the expected number of entries is one of the following values:
2, 3, 5, 10, 11, 21, 42, 43, 85, 170, 171, 341,
682, 683, 1365, 2730, 2731, 5461, 10922, 10923,
21845, 43690, 43691, 87381, 174762, 174763, 349525,
699050, 699051, 1398101, 2796202, 2796203, 5592405,
11184810, 11184811, 22369621, 44739242, 44739243,
89478485, 178956970, 178956971 and all numbers
greater than or equal to 357913941
To test this, set a line breakpoint to the first line of code in method resize(int) and fill the map with the expected maximum number of entries. A breakpoint hit confirms the bug.
The first issue is that the capacity of the table is incorrectly computed for the given expected maximum number of entries. The load factor of IdentityHashMap is fixed to always be 2/3, so the capacity is computed as follows:
int minCapacity = (3 * expectedMaxSize)/2;
This seems to be correct at first sight. The problem is that if 'expectedMaxSize' is an odd number, the computed minCapacity is less than 3/2 of the expected maximum size. Because the threshold for rehashing is computed from the minimum capacity, the rounding bug propagates to the incorrect result of the threshold, which is then 1 lower than it should be.
Fortunately, the above formula is followed by another forumula that rounds the computed minCapacity to the lowest power of two equal to or greater than the initial minCapacity. This eliminates the damage in most cases.
The second issue is that even if the initial capacity and the threshold are computed correctly, the threshold is incorrectly used. The table should get resized (rehashed) if the number of entries _exceeds_ (or would be about to exceed) the threshold. But the table is rehashed as soon as the threshold is _reached_:
public V put(K key, V value) {
...
if (++size >= threshold)
resize(len);
return null;
}
If only one of the issues shows, the table gets resized as soon as the number of entries reaches the expected maximum number of elements. If both the issues show, the table gets resized when the number of entries is one below the expected maximum number of elements.
This bug is present in JDK 6u18 and also in JDK 5u22.
A simple test application is attached.
The Javadoc of IdentityHashMap(int) specifies that "putting more than the expected number of keyvalue mappings into the map may cause the internal data structure to grow". Strictly taken, this statement does not promise that the internal data structure would not grow sooner, but I believe it was meant that way and that most developers understand it that way.
The fact is that the internal data structure may grow before the expected number of keyvalue mappings inserted into the map exceeds the expected number specified by the constructor's parameter. This is the case if the expected number of entries is one of the following values:
2, 3, 5, 10, 11, 21, 42, 43, 85, 170, 171, 341,
682, 683, 1365, 2730, 2731, 5461, 10922, 10923,
21845, 43690, 43691, 87381, 174762, 174763, 349525,
699050, 699051, 1398101, 2796202, 2796203, 5592405,
11184810, 11184811, 22369621, 44739242, 44739243,
89478485, 178956970, 178956971 and all numbers
greater than or equal to 357913941
To test this, set a line breakpoint to the first line of code in method resize(int) and fill the map with the expected maximum number of entries. A breakpoint hit confirms the bug.
The first issue is that the capacity of the table is incorrectly computed for the given expected maximum number of entries. The load factor of IdentityHashMap is fixed to always be 2/3, so the capacity is computed as follows:
int minCapacity = (3 * expectedMaxSize)/2;
This seems to be correct at first sight. The problem is that if 'expectedMaxSize' is an odd number, the computed minCapacity is less than 3/2 of the expected maximum size. Because the threshold for rehashing is computed from the minimum capacity, the rounding bug propagates to the incorrect result of the threshold, which is then 1 lower than it should be.
Fortunately, the above formula is followed by another forumula that rounds the computed minCapacity to the lowest power of two equal to or greater than the initial minCapacity. This eliminates the damage in most cases.
The second issue is that even if the initial capacity and the threshold are computed correctly, the threshold is incorrectly used. The table should get resized (rehashed) if the number of entries _exceeds_ (or would be about to exceed) the threshold. But the table is rehashed as soon as the threshold is _reached_:
public V put(K key, V value) {
...
if (++size >= threshold)
resize(len);
return null;
}
If only one of the issues shows, the table gets resized as soon as the number of entries reaches the expected maximum number of elements. If both the issues show, the table gets resized when the number of entries is one below the expected maximum number of elements.
This bug is present in JDK 6u18 and also in JDK 5u22.
A simple test application is attached.
Attachments
Issue Links
 backported by

JDK8064413 (coll) IdentityHashMap is resized before exceeding the expected maximum size
 Resolved

JDK8065496 (coll) IdentityHashMap is resized before exceeding the expected maximum size
 Resolved

JDK8070047 (coll) IdentityHashMap is resized before exceeding the expected maximum size
 Resolved

JDK8194022 (coll) IdentityHashMap is resized before exceeding the expected maximum size
 Resolved
 relates to

JDK8164793 new ArrayDeque(2**N) allocates backing array of size 2**(N+1)
 Resolved