Bounds checks with unsafe array access

[Paul Sandoz]

On Sep 12, 2014, at 7:04 PM, John Rose <john.r.rose at oracle.com> wrote:
> On Sep 12, 2014, at 5:40 AM, Paul Sandoz <paul.sandoz at oracle.com> wrote:
> 
>> On Sep 11, 2014, at 10:51 PM, John Rose <john.r.rose at oracle.com> wrote:
>>> In some cases of highly tuned code the author can work with the JIT engineer to insert the right code shapes from the start.
>>> The "test length against zero" code shape is one of these, and can often be merged with a check that is required any way (e.g., is the data structure logically empty?).
>>> For example:
>>> http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/f08705540498/src/java.base/share/classes/java/util/HashMap.java#l569
>>> 
>> 
>> A great example, i was just recently looking at that :-)
>> 
>> My understanding is that check ("(n = tab.length) > 0") is in place solely to generate more efficient bounds checks, since it should always return true (table is either null or non-null with a length > 0). If/when JDK-8003585 gets fixed we might be able to update the code and remove that check (or turn it into an assert if it did not interfere with inlining...).
> 
> Actually, that would be a step backwards.  It is best to initialize HashMap.table to a constant zero-length array:
>  https://bugs.openjdk.java.net/browse/JDK-8003586
> If the table is never null, then the null check becomes mergeable into the following load instruction.
> 

I thought the explicit null check would get merged with the load of the array length, at least in a simple case that is what i observe:

  0x000000010c2c958c: mov    0x24(%rsi),%r10d   ;*getfield table
                                                ; - java.util.HashMap::getNode at 1 (line 568)

  0x000000010c2c9590: mov    0xc(%r12,%r10,8),%r8d  ;*arraylength
                                                ; - java.util.HashMap::getNode at 10 (line 568)
                                                ; implicit exception: dispatches to 0x000000010c2c964d
  0x000000010c2c9595: test   %r8d,%r8d
  0x000000010c2c9598: jle    0x000000010c2c960d  ;*ifle
                                                ; - java.util.HashMap::getNode at 14 (line 568)

  0x000000010c2c959a: mov    %r8d,%ebp
  0x000000010c2c959d: dec    %ebp
  0x000000010c2c959f: and    %edx,%ebp          ;*iand
                                                ; - java.util.HashMap::getNode at 23 (line 568)

  0x000000010c2c95a1: cmp    %r8d,%ebp
  0x000000010c2c95a4: jae    0x000000010c2c95f1   <--- this will go away
  0x000000010c2c95a6: shl    $0x3,%r10
  0x000000010c2c95aa: mov    0x10(%r10,%rbp,4),%r11d  ;*aaload


>> I was naively pondering whether that table field:
>> 
>> http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/f08705540498/src/java.base/share/classes/java/util/HashMap.java#l395
>> 
>> could be annotated with something like @ArrayHasElementsIfNonNull, so that a write to that field would be guarded by a check which would throw an assertion error if the field would otherwise be set to an empty array.
> 
> If we can auto-detect this sort of thing then we don't need annotations.  A simple class-wide analysis at JIT time could detect such invariants.

And/or perhaps AOT?


>  The missing bit (from the JVM perspective) is a robust way to protect those invariants from invasive changes, via JNI, reflection, or (perhaps in some cases) subclassing.
> 
>> 
>> Final field optimizations would be a bigger bang for the buck though.
> 
> And they would supply that important missing bit.
> 
>> Combine that with specialization and perhaps there is an alternative implementation approach to the current VarHandles prototype?
> 
> Yes, of course.  You know, any class in java.lang.invoke has a special perk:  the final field optimization already works on it:
>  http://hg.openjdk.java.net/jdk9/jdk9/hotspot/file/efe1eb043ee1/src/share/vm/ci/ciField.cpp#l187

I was pleasantly surprised to find that out :-) and recently experimented with it after some discussions with Remi on the valhalla list.


> 
>> class FieldHandle<R, any V> {
>>  /* really */ final Class<?> rType;
>>  /* really */ final Class<?> vType;
>>  /* really */ final long foffset;
>> 
>>  <where reference V>
>>  V getVolatile(R r) {
>>      r.getClass();
>>      rType.cast(r); // Should go away (well almost!) if FieldHandle instance is constant
>>      return vType.cast(U.getObjectVolatile(r, foffset));
>>  }
>> 
>>  <where V = int>
>>  int getVolatile(R r) {
>>      r.getClass();
>>      rType.cast(r);
>>      return U.getIntVolatile(r, foffset);
>>  }
>> }
> 
> Type "any" is the right way to do full polymorphism for single arguments, no?
> 

Perhaps for a comment set?  I presume certain atomic operations are unlikely to be supported for all primitive types, and certain operations are only applicable to primitive types (such as getAndAdd, although i wonder how should that apply, if at all, to say a LongLong value type).

Also, maybe there is an intermediate step if specialization gets there before the value machinery, as you sketch below, is in place. 


> The "where" bits don't quite extend to value types, without some sort of value-generic magic for Unsafe.  Which is doable:
> 
>>  <where value V>
>>  V getVolatile(R r) {
>>      r.getClass();
>>      rType.cast(r);
>>      return vType.cast(U.<V.box>getValueVolatile(r, foffset, V.unbox.class));
>>  }
> 
> The magic there would be something like (1) Class.cast works on boxed values only, (2) there is always implicit box/unbox conversion, (3) the JIT is aggressive about cleaning out boxes, and (4) the internals of U.getValueVolatile would operate on the unboxed value, and simply return a box with the expectation of immediate unboxing.
> 
> (There are language design issues with which occurrences of the value type denote boxes, etc.)
> 

Thanks, seems to be some intersection here with potential LF improvements for cleaning out boxes.

Paul.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 841 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140917/3e95dd43/signature-0001.asc>