Bounds checks with unsafe array access

[John Rose]

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

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

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

— John