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

[Ivan Gerasimov]

Ah, yes, sure.
I overlooked the reference to the table :-)

On 09.07.2014 2:42, Peter Levart wrote:
>
> On 07/09/2014 12:06 AM, Ivan Gerasimov wrote:
>>
>> On 09.07.2014 1:44, Peter Levart wrote:
>>>
>>> On 07/08/2014 11:39 PM, Ivan Gerasimov wrote:
>>>> Might be worth to add modCount++ before this line:
>>>>
>>>>   487         table = newTable;
>>>>   488         return true;
>>>>
>>> Not quite, I think. The map has just been resized, but it's contents 
>>> has not changed yet logically.
>>>
>> IdentityHashMapIterator's methods assume that if modCount didn't 
>> change, then the indices calculated earlier remain valid, and this is 
>> wrong in the case of resize.
>>
>> Sincerely yours,
>> Ivan
>
> IdentityHashMapIterator:
>
>   713     private abstract class IdentityHashMapIterator<T> implements Iterator<T> {
>   714         int index = (size != 0 ? 0 : table.length); // current slot.
>   715         int expectedModCount = modCount; // to support fast-fail
>   716         int lastReturnedIndex = -1;      // to allow remove()
>   717         boolean indexValid; // To avoid unnecessary next computation
>   718         Object[] traversalTable = table; // reference to main table or copy
>
> ...takes a snap-shot of reference to current table when created, so 
> indexes would still be valid ...
>
> ...but resize() also clears old table as it copies elements to new table:
>
>   478                 oldTable[j] = null;
>   479                 oldTable[j+1] = null;
>
> So it would appear that modCount should be incremented even before the 
> copying loop.
>
> But as it seems, no user call-backs are possible during resize() in 
> same thread and normal writes are not ordered anyway for other threads 
> and after each "successful" resize() at least one new key will be 
> added to the map so modCount will be incremented before control is 
> returned to user code anyway.
>
> Regards, Peter
>
>>
>>
>>> Regards, Peter
>>>
>>>> On 09.07.2014 0:07, Martin Buchholz wrote:
>>>>> I updated my webrev and it is again "feature-complete".
>>>>> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity/ 
>>>>> <http://cr.openjdk.java.net/%7Emartin/webrevs/openjdk9/IdentityHashMap-capacity/>
>>>>> (old webrev at
>>>>> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity.0/ 
>>>>> <http://cr.openjdk.java.net/%7Emartin/webrevs/openjdk9/IdentityHashMap-capacity.0/>
>>>>> )
>>>>>
>>>>> This incorporates Peter's idea of making resize return a boolean, 
>>>>> keeps the map unchanged if resize throws, moves the check for 
>>>>> capacity exceeded into resize, and minimizes bytecode in put(). 
>>>>>  I'm happy with this (except for degraded behavior near MAX_CAPACITY).
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> On Tue, Jul 8, 2014 at 8:06 AM, Peter Levart 
>>>>> <peter.levart at gmail.com <mailto:peter.levart at gmail.com>> wrote:
>>>>>
>>>>>     On 07/08/2014 03:00 PM, Ivan Gerasimov wrote:
>>>>>
>>>>>             I took your latest version of the patch and modified
>>>>>             it a little:
>>>>>
>>>>>             http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.01/
>>>>>             <http://cr.openjdk.java.net/%7Eplevart/jdk9-dev/IdentityHashMap/webrev.01/>
>>>>>
>>>>>
>>>>>         But isn't it post-insert-resize vs pre-insert-resize
>>>>>         problem Doug mentioned above?
>>>>>         I've tested a similar fix and it showed slow down of the
>>>>>         put() operation.
>>>>>
>>>>>     Hi Ivan,
>>>>>
>>>>>     Might be that it has to do with # of bytecodes in the method
>>>>>     and in-lining threshold. I modified it once more, to make
>>>>>     put() method as short as possible:
>>>>>
>>>>>     http://cr.openjdk.java.net/~plevart/jdk9-dev/IdentityHashMap/webrev.05/
>>>>>     <http://cr.openjdk.java.net/%7Eplevart/jdk9-dev/IdentityHashMap/webrev.05/>
>>>>>
>>>>>     With this, I ran the following JMH benchmark:
>>>>>
>>>>>     @State(Scope.Thread)
>>>>>     public class IHMBench {
>>>>>
>>>>>         Map<Object, Object> map = new IdentityHashMap<Object,
>>>>>     Object>();
>>>>>
>>>>>         @Benchmark
>>>>>         public void putNewObject(Blackhole bh) {
>>>>>             Object o = new Object();
>>>>>             bh.consume(map.put(o, o));
>>>>>             if (map.size() > 100000) {
>>>>>                 map = new IdentityHashMap<Object, Object>();
>>>>>             }
>>>>>         }
>>>>>     }
>>>>>
>>>>>     I get the following results on my i7/Linux using:
>>>>>
>>>>>     java -Xmx4G -Xms4G -XX:+UseParallelGC -jar benchmarks.jar -f 0
>>>>>     -i 10 -wi 8 -gc 1 -t 1
>>>>>
>>>>>     Original:
>>>>>
>>>>>     Benchmark                     Mode   Samples  Score  Score
>>>>>     error    Units
>>>>>     j.t.IHMBench.putNewObject    thrpt        10 13088296.198
>>>>>     <tel:13088296.198> 403446.449    ops/s
>>>>>
>>>>>     Patched:
>>>>>
>>>>>     Benchmark                     Mode   Samples  Score  Score
>>>>>     error    Units
>>>>>     j.t.IHMBench.putNewObject    thrpt        10 13180594.537
>>>>>     282047.154    ops/s
>>>>>
>>>>>
>>>>>     Can you run your test with webrev.05 and see what you get ?
>>>>>
>>>>>     Regards, Peter
>>>>>
>>>>>
>>>>
>>>
>>
>