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

[Martin Buchholz]

If size == MAXIMUM_CAPACITY - 1 and you're in resize, presumably you're
about to fill that last empty slot after returning, so you want to throw
instead of returning false?

Benchmarks welcome.


On Tue, Jul 8, 2014 at 2:15 PM, Peter Levart <peter.levart at gmail.com> wrote:

>
> On 07/08/2014 10:07 PM, Martin Buchholz wrote:
>
> I updated my webrev and it is again "feature-complete".
>
> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/IdentityHashMap-capacity/
>  (old webrev at
>
> http://cr.openjdk.java.net/~martin/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).
>
>
> Nice solution. I hope that resize:
>
>  458     private boolean resize(int newCapacity) {
>  459         // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
>  460         int newLength = newCapacity * 2;
>  461
>  462         Object[] oldTable = table;
>  463         int oldLength = oldTable.length;
>  464         if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
>  465             if (size == MAXIMUM_CAPACITY - 1)
>  466                 throw new IllegalStateException("Capacity exhausted.");
>  467             return false;
>  468         }
>  469         if (oldLength >= newLength)
>  470             return false;
>
> ... is never (going to be) called in context that would make oldLength >=
> newLength && oldLength == 2 * MAXIMUM_CAPACITY && size == MAXIMUM_CAPACITY
> - 1 ...
>
> In that case it would be better to return false than to throw
> IllegalStateException, since no re-sizing was actually requested. if
> statement (L469,470) could be moved just after newLength assignment (L460)
> to make resize() more robust to possible future changes of calling code.
>
> I wonder what the benchmarks will say.
>
> Regards, Peter
>
>
>
>
> On Tue, Jul 8, 2014 at 8:06 AM, Peter Levart <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/
>>>>
>>>>
>>> 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/
>>
>> 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 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
>>
>>
>
>