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

David Holmes david.holmes at oracle.com
Sat Jul 5 03:19:07 UTC 2014

Ivan,

Fields like MAXIMUM_CAPACITY are compile-time constants. Their values are placed directly into the code that uses them - there is no associated getField to load it. Hence changing the field via reflection has no affect on any existing code that references the field.

I'm still uncomfortable about the scope of the changes - and Doug rightly mentions doing detailed performance runs before submitting this. I still think recovering from a post-put resize failure might be better than resizing first.

David

On 5/07/2014 3:33 AM, Ivan Gerasimov wrote:

Thanks David for looking at the change!

On 04.07.2014 8:14, David Holmes wrote: Hi Ivan,

I find the change to capacity somewhat obfuscating and I can't see what the actual bug was. The bug was in rounding in the expression minCapacity = (3 * expectedMaxSize)/2. Suppose, we want the expected size to be 11, then minCapacity becomes (int)(11 * 3 / 2) == 16. The threshold is calculated later to be (int)(16 * 2 / 3) == 10, which is less than expected size 11. To address the issue I combined the division by 2 with the rounding up to the nearest power of two. I also took a chance to replace a while-loop with a single call to the highestOneBit method, which calculates exactly what we need here. The recursive call to put after a resize seems very sub-optimal as you will re-search the map for the non-existent key. Can you not just recompute the correct indices and do the store? Okay, I replaced the recursive call with the index recomputation. As was suggested by Jeff, I added a comment to the MAXIMUMCAPACITY constant. I also reverted some part of the changes to the resize() function, as it turned out that the new code failed to deal correctly with the table of maximum capacity. I wanted to add checking of this behavior to the regression test, but faced an obstacle: I used reflection to make the MAXIMUMCAPACITY constant smaller, so it wouldn't be needed to insert 2**29 element to fill the table up. The debugger was showing that the constant was changed, but the old value was still used in the conditions. Currently I commented this test out. If anyone could suggest me how I can properly change MAXIMUMCAPACITY in this situation, it would be very appreciated. Here is the updated webrev: http://cr.openjdk.java.net/~igerasim/6904367/2/webrev/ Would you please help review it? Sincerely yours, Ivan. Alternatively use the original code and if an exception occurs on resize then simply undo the "put". I'm always worried that inverting the behaviour like you will have some unexpected side effect somewhere - this code has been like this for a very, very long time. Cheers, David On 4/07/2014 5:38 AM, Ivan Gerasimov wrote: Thank you Jeff!

On 03.07.2014 23:07, Jeff Hain wrote: Hi.

>WEBREV: http://cr.openjdk.java.net/~igerasim/6904367/0/webrev/ <http://cr.openjdk.java.net/%7Eigerasim/6904367/0/webrev/> The "while" loop in put(...) supposes that there is at least one free slot, which was the case before (that could be added as comment). Now if you try to go past max capacity, instead of getting an IllegalStateException, you get an infinite loop. Yes, you're right! It's easy to test with a loop of 1000 puts and MAXCAPACITY = 1<<8_ _(=256, needs to be larger than DEFAULTCAPACITY, else it can be_ _"ignored")._ _With previous version you get IllegalStateException on trying to add_ _255th mapping_ _(on the resize that occurs when just-after-put-size is 255 >= threshold = 255), and with new version you get infinite loop on trying to add 257th mapping. Solutions I see would be adding a throw if size >= MAXCAPACITY before the loop, This would break the case when an existing key is added to the already full table. Moreover, the full table without a single empty slot could cause an infinite looping in get(), remove(), etc. or not adding that overhead and instead throwing when "size >= MAXCAPACITY-1" instead of when "size >= MAXCAPACITY". This seems appropriate. With the current implementation we can only put MAXCAPACITY-1 elements anyway. I would also rather use "==" over ">=" for these tests, to underline the fact that size is not supposed to be larger, but there might be some reasons not to. I think it makes the code a bit more stable from the perspective of the future changes. Here's the updated webrev: http://cr.openjdk.java.net/~igerasim/6904367/1/webrev/ Sincerely yours, Ivan

-Jeff

More information about the core-libs-dev mailing list