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

[Peter Levart]

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
>>>>
>>>>
>>>
>>
>