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

[Peter Levart]

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/ 
> <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).

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