Quantcast

Unsafe for array access

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Unsafe for array access

Paul Sandoz
Hi,

As part of some investigatory work for JEP 193: Enhanced Volatiles i have been looking at how enhanced (and safe) access to array elements could be implemented.

The obvious and simple choice is to reach for unsafe with a few safety checks, for example:

    @ForceInline
    static void setVolatile(ArrayRefHandle handle, Object[] array, int index,
            Object value) {
        if (index < 0 || index >= array.length) // bounds and null check
            throw new ArrayIndexOutOfBoundsException();
        UNSAFE.putObjectVolatile(array,
                                 (((long) index) << handle.ashift) + handle.abase,
                                 castReference(handle.componentType, value));
    }

The problem is the compiler does fully recognize an array access is going on and so certain optimizations tend not to kick in, such as removing or strength reducing bounds checks, or treating "index" as a signed value rather than unsigned.

Any clues/pointers on how i can hack things so that hotspot knows that an array access is going on in the above code, and views it as almost equivalent to following in terms of optimizations?

    @ForceInline
    static void setVolatile(ArrayRefHandle handle, Object[] array, int index,
            Object value) {
        if (index < 0 || index >= array.length) // bounds and null check
            throw new ArrayIndexOutOfBoundsException();
        array[i] = castReference(handle.componentType, value);
    }


Some context: ForkJoinPool is peppered with code like the following:

                            int i = (((a.length - 1) & b) << ASHIFT) + ABASE;
                            ForkJoinTask<?> t =
                                (ForkJoinTask<?>)U.getObjectVolatile(a, i);

Any viable replacement for direct Unsafe usages in that code will want those strength reducing optimizations to kick in.

Paul.

signature.asc (858 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Unsafe for array access

John Rose-3
Paul, this is a reasonable request.  Please file a P3 bug against the hotspot compiler.

Our iteration range splitting transform is gated by a pattern match on a loop body (after inlining).  One of the pattern conditions is that there is an array reference (incl. range check) in the body of the loop.  (Not surprising.)

1. The user-written code should be an alias for a JVM-issued range check.  (The signed/unsigned identities are tricky, and some parts are probably broken.)

2. We should extend our pattern match to allow code like yours to trigger range splitting.

I don't think the above points require deep cuts.

Some background is here:  https://wiki.openjdk.java.net/display/HotSpot/RangeCheckElimination

— John

On May 5, 2014, at 8:20 AM, Paul Sandoz <[hidden email]> wrote:

> Hi,
>
> As part of some investigatory work for JEP 193: Enhanced Volatiles i have been looking at how enhanced (and safe) access to array elements could be implemented.
>
> The obvious and simple choice is to reach for unsafe with a few safety checks, for example:
>
>    @ForceInline
>    static void setVolatile(ArrayRefHandle handle, Object[] array, int index,
>            Object value) {
>        if (index < 0 || index >= array.length) // bounds and null check
>            throw new ArrayIndexOutOfBoundsException();
>        UNSAFE.putObjectVolatile(array,
>                                 (((long) index) << handle.ashift) + handle.abase,
>                                 castReference(handle.componentType, value));
>    }
>
> The problem is the compiler does fully recognize an array access is going on and so certain optimizations tend not to kick in, such as removing or strength reducing bounds checks, or treating "index" as a signed value rather than unsigned.
>
> Any clues/pointers on how i can hack things so that hotspot knows that an array access is going on in the above code, and views it as almost equivalent to following in terms of optimizations?
>
>    @ForceInline
>    static void setVolatile(ArrayRefHandle handle, Object[] array, int index,
>            Object value) {
>        if (index < 0 || index >= array.length) // bounds and null check
>            throw new ArrayIndexOutOfBoundsException();
>        array[i] = castReference(handle.componentType, value);
>    }
>
>
> Some context: ForkJoinPool is peppered with code like the following:
>
>                            int i = (((a.length - 1) & b) << ASHIFT) + ABASE;
>                            ForkJoinTask<?> t =
>                                (ForkJoinTask<?>)U.getObjectVolatile(a, i);
>
> Any viable replacement for direct Unsafe usages in that code will want those strength reducing optimizations to kick in.
>
> Paul.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Unsafe for array access

Doug Lea
In reply to this post by Paul Sandoz
On 05/05/2014 11:20 AM, Paul Sandoz wrote:

> Hi,
>
> As part of some investigatory work for JEP 193: Enhanced Volatiles i have been looking at how enhanced (and safe) access to array elements could be implemented.
>
> The obvious and simple choice is to reach for unsafe with a few safety checks, for example:
>
>      @ForceInline
>      static void setVolatile(ArrayRefHandle handle, Object[] array, int index,
>              Object value) {
>          if (index < 0 || index >= array.length) // bounds and null check
>              throw new ArrayIndexOutOfBoundsException();
>          UNSAFE.putObjectVolatile(array,
>                                   (((long) index) << handle.ashift) + handle.abase,
>                                   castReference(handle.componentType, value));
>      }
>

Relatedly, it might be be nice to have an intrinsic boundsCheck(array, index)
that could be used in such cases that implemented using the more efficient
(using C): (unsigned)index >= (unsigned)array.length, plus relied on more
efficient VM throw mechanics on failure.

>
> Some context: ForkJoinPool is peppered with code like the following:
>
>                              int i = (((a.length - 1) & b) << ASHIFT) + ABASE;
>                              ForkJoinTask<?> t =
>                                  (ForkJoinTask<?>)U.getObjectVolatile(a, i);
>
> Any viable replacement for direct Unsafe usages in that code will want those strength reducing optimizations to kick in.
>

Similarly for ConcurrentHashMap. It's hard to say how typical
this style of use is outside of these two classes though. The need to
use Unsafe array access impacted overall class design. To maintain
a proper level of paranoia about using Unsafe, arrays are always
powers of two, indexes use masks and explicit int (not long) shifts
guaranteed so that offsets cannot escape bounds unless array lengths
are zero or >= than 1<<(31-sizeof(pointer)). Construction is
isolated to make it easily statically checkable (in principal)
that lengths are OK.

(Also, in FJ, these constructions are not often used in loops, so
loop optimizations will have less impact than just streamlining
get/put/cas, which are the main operations in fork() and work-stealing,
so slowdowns will have measurable impact.)

-Doug

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Unsafe for array access

John Rose-3
> On May 7, 2014, at 4:30 AM, Doug Lea <[hidden email]> wrote:

>
> Relatedly, it might be be nice to have an intrinsic boundsCheck(array, index)
> that could be used in such cases that implemented using the more efficient
> (using C): (unsigned)index >= (unsigned)array.length, plus relied on more
> efficient VM throw mechanics on failure.

We need an intrinsic like this for Arrays 2.0. Might as well do it now, since we have an immediate application.

Counterpoint:  optimizer can and should generate similar code for plain user written range tests.

Advice:  Do both, and the intrinsic will give everybody a clearer target to aim for. Unit test the intrinsic optimization, and several similar formulations.

– John
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Unsafe for array access

Vladimir Kozlov
Note, we do convert some user's bound check to array's range check. The example is Integer::valueOf():

     public static Integer valueOf(int i) {
         if (i >= IntegerCache.low && i <= IntegerCache.high)
             return IntegerCache.cache[i + (-IntegerCache.low)];
         return new Integer(i);
     }

The check is converted to ((i-IntegerCache.low) u< IntegerCache.length) and removed as duplicate of the generated range
check for the following load.

length = (high - low) + 1

Vladimir

On 5/7/14 8:56 AM, John Rose wrote:

>> On May 7, 2014, at 4:30 AM, Doug Lea <[hidden email]> wrote:
>
>>
>> Relatedly, it might be be nice to have an intrinsic boundsCheck(array, index)
>> that could be used in such cases that implemented using the more efficient
>> (using C): (unsigned)index >= (unsigned)array.length, plus relied on more
>> efficient VM throw mechanics on failure.
>
> We need an intrinsic like this for Arrays 2.0. Might as well do it now, since we have an immediate application.
>
> Counterpoint:  optimizer can and should generate similar code for plain user written range tests.
>
> Advice:  Do both, and the intrinsic will give everybody a clearer target to aim for. Unit test the intrinsic optimization, and several similar formulations.
>
> – John
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Unsafe for array access

David Chase
In reply to this post by John Rose-3
Don't we now have an Unsigned class providing these operations? (which could be intrinsified)
Or did we want to tie the intrinsic more closely to array classes?

David

On 2014-05-07, at 11:56 AM, John Rose <[hidden email]> wrote:

>> On May 7, 2014, at 4:30 AM, Doug Lea <[hidden email]> wrote:
>
>>
>> Relatedly, it might be be nice to have an intrinsic boundsCheck(array, index)
>> that could be used in such cases that implemented using the more efficient
>> (using C): (unsigned)index >= (unsigned)array.length, plus relied on more
>> efficient VM throw mechanics on failure.
>
> We need an intrinsic like this for Arrays 2.0. Might as well do it now, since we have an immediate application.
>
> Counterpoint:  optimizer can and should generate similar code for plain user written range tests.
>
> Advice:  Do both, and the intrinsic will give everybody a clearer target to aim for. Unit test the intrinsic optimization, and several similar formulations.
>
> – John


signature.asc (817 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Unsafe for array access

John Rose-3
On May 7, 2014, at 10:23 AM, David Chase <[hidden email]> wrote:

> Don't we now have an Unsigned class providing these operations? (which could be intrinsified)
> Or did we want to tie the intrinsic more closely to array classes?

It's not a class.  (Some day a value type!)  We have the method Integer.compareUnsigned, which should not even need intrinsifying, but may need a little pattern matching help in GVN.

Doug is suggesting (and I concur) that it would be good to package up both the test and the error path, or at least have a test method that the optimizer can treat as a never failing test.

In whatever form, the test should play nicely with range check elimination, and (probably) also with any optimistic range check related conditions, such as are found in deoptimization.hpp.

— John

> David
>
> On 2014-05-07, at 11:56 AM, John Rose <[hidden email]> wrote:
>
>>> On May 7, 2014, at 4:30 AM, Doug Lea <[hidden email]> wrote:
>>
>>>
>>> Relatedly, it might be be nice to have an intrinsic boundsCheck(array, index)
>>> that could be used in such cases that implemented using the more efficient
>>> (using C): (unsigned)index >= (unsigned)array.length, plus relied on more
>>> efficient VM throw mechanics on failure.
>>
>> We need an intrinsic like this for Arrays 2.0. Might as well do it now, since we have an immediate application.
>>
>> Counterpoint:  optimizer can and should generate similar code for plain user written range tests.
>>
>> Advice:  Do both, and the intrinsic will give everybody a clearer target to aim for. Unit test the intrinsic optimization, and several similar formulations.
>>
>> – John
>

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Unsafe for array access

Andrew Haley
In reply to this post by Vladimir Kozlov
On 05/07/2014 05:15 PM, Vladimir Kozlov wrote:
> Note, we do convert some user's bound check to array's range check. The example is Integer::valueOf():
>
>      public static Integer valueOf(int i) {
>          if (i >= IntegerCache.low && i <= IntegerCache.high)
>              return IntegerCache.cache[i + (-IntegerCache.low)];
>          return new Integer(i);
>      }
>
> The check is converted to ((i-IntegerCache.low) u< IntegerCache.length)

Did you mean

((i-IntegerCache.low) u< IntegerCache.high)

?


 and removed as duplicate of the generated range

> check for the following load.
>
> length = (high - low) + 1
>
> Vladimir
>
> On 5/7/14 8:56 AM, John Rose wrote:
>>> On May 7, 2014, at 4:30 AM, Doug Lea <[hidden email]> wrote:
>>
>>>
>>> Relatedly, it might be be nice to have an intrinsic boundsCheck(array, index)
>>> that could be used in such cases that implemented using the more efficient
>>> (using C): (unsigned)index >= (unsigned)array.length, plus relied on more
>>> efficient VM throw mechanics on failure.
>>
>> We need an intrinsic like this for Arrays 2.0. Might as well do it now, since we have an immediate application.
>>
>> Counterpoint:  optimizer can and should generate similar code for plain user written range tests.
>>
>> Advice:  Do both, and the intrinsic will give everybody a clearer target to aim for. Unit test the intrinsic optimization, and several similar formulations.
>>
>> – John
>>

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Unsafe for array access

Paul Sandoz
In reply to this post by John Rose-3

On May 6, 2014, at 8:38 PM, John Rose <[hidden email]> wrote:

Paul, this is a reasonable request.  Please file a P3 bug against the hotspot compiler.


Thanks.  Logged:

  https://bugs.openjdk.java.net/browse/JDK-8042997

Paul.

signature.asc (858 bytes) Download Attachment
Loading...