Bounds checks with unsafe array access
Vitaly Davidovich
vitalyd at gmail.com
Thu Sep 11 17:49:53 UTC 2014
Ok, thanks. Looking forward to final fields being treated as, well ...
final :)
On Thu, Sep 11, 2014 at 1:04 PM, Vladimir Ivanov <
vladimir.x.ivanov at oracle.com> wrote:
>
>
> On 9/11/14, 8:40 PM, Vitaly Davidovich wrote:
>
>> Thanks Vladimir.
>>
>> If a guard is used for arraylength, then that guard would have to be
>> checked each time anyway, right? In that case, given the guard would
>> perform a cmp against 0 (or a test), isn't the whole point defeated
>> (i.e. no range/length check)?
>>
> In some situations, yes. But it can be moved out of inner loops and
> performed less frequently.
>
> Right, currently dependencies are at the class level. But it sounded to
>> me like this will be extended to support dependencies on fields (i.e. to
>> support final fields)?
>>
> IMO changes to final variables through Reflection API are rare, so current
> dependency tracking mechanism should work pretty well. Conservatively
> invalidating all methods with embedded constants from objects of some
> particular type may pay off.
>
> It's not the case with arrays, since array writes are very common.
>
> Best regards,
> Vladimir Ivanov
>
>
>> On Thu, Sep 11, 2014 at 12:13 PM, Vladimir Ivanov
>> <vladimir.x.ivanov at oracle.com <mailto:vladimir.x.ivanov at oracle.com>>
>> wrote:
>>
>> Thanks, Vitaly.
>>
>> I think it's much simpler to profile array length and then add a
>> guard, if arrays of 0 length hasn't been seen.
>>
>> Considering how dependencies are implemented in HotSpot (on class
>> granularity), it looks too coarse-grained for tracking
>> instance-specific information.
>>
>> Best regards,
>> Vladimir Ivanov
>>
>> On 9/10/14, 6:51 PM, Vitaly Davidovich wrote:
>>
>> I'm sort of asking whether what I wrote earlier (inline below) is
>> feasible/practical:
>>
>> Yeah, I don't know how one would do that practically.
>> Compiler
>> would have to somehow always know that whenever the array
>> is set its
>> len > 0. One crazy idea is to treat this like other
>> speculation via
>> deopt. When jit compiling a method with array access, check
>> profiling info and see whether len has been seen > 0 always
>> thus
>> far. If so, compile that assumption in and register a
>> deopt if this
>> ever changes. This deopt would have to piggyback on write
>> barrier
>> or something, but this adds extra complexity and perf impact
>> on
>> writes. Maybe for cases where the array is predominantly
>> read this
>> could be a net win ...
>>
>>
>> If there was a way to track a dependency between writes to a
>> final field
>> and nmethods using that final field (and being able to
>> invalidate those
>> nmethods when a write is performed), then is there a way to
>> extend this
>> to allow tracking a dependency between a write into an array
>> field and
>> nmethods using that array? If so, one could presumably compile
>> this
>> nmethod with the assumption that the array's length is > 0 (and
>> thus
>> helps Paul's examples) assuming that's what profiling info tells
>> us.
>> But if this assumption is broken (i.e. this array is replaced
>> with a
>> null or 0-length array), the nmethod is invalidated.
>>
>> Does that make sense?
>>
>>
>> On Wed, Sep 10, 2014 at 10:41 AM, Vladimir Ivanov
>> <vladimir.x.ivanov at oracle.com
>> <mailto:vladimir.x.ivanov at oracle.com>
>> <mailto:vladimir.x.ivanov at __oracle.com
>> <mailto:vladimir.x.ivanov at oracle.com>>> wrote:
>>
>> Vitaly,
>>
>> Can you elaborate on what do you mean by "this mechanism
>> could be
>> extended to track non-final arrays"? I don't see strong
>> relation
>> between value profiling and tracking Reflection API usage.
>>
>> Best regards,
>> Vladimir Ivanov
>>
>> On 9/10/14, 5:47 PM, Vitaly Davidovich wrote:
>>
>> Vladimir,
>>
>> Nice to hear you guys are looking to do something about
>> this.
>> Supposing
>> there was a way to track nmethod dependencies on final
>> fields (with
>> invalidation upon change), presumably this mechanism
>> could be
>> extended
>> to track non-final arrays as well and thus support the
>> examples Paul
>> brought up?
>>
>> Sent from my phone
>>
>> On Sep 10, 2014 9:36 AM, "Vladimir Ivanov"
>> <vladimir.x.ivanov at oracle.com
>> <mailto:vladimir.x.ivanov at oracle.com>
>> <mailto:vladimir.x.ivanov at __oracle.com
>> <mailto:vladimir.x.ivanov at oracle.com>>
>> <mailto:vladimir.x.ivanov@
>> <mailto:vladimir.x.ivanov@>__or__acle.com <http://oracle.com>
>>
>>
>> <mailto:vladimir.x.ivanov at __oracle.com
>> <mailto:vladimir.x.ivanov at oracle.com>>>> wrote:
>>
>> Remi,
>>
>> @Stable isn't a full match for final field case,
>> since it
>> doesn't
>> treat default values as constants. But I agree,
>> it's close.
>>
>> Hotspot already constant folds loads from static
>> final
>> fields and
>> there's an experimental flag
>> TrustFinalNonStaticFields for
>> final
>> instance fields.
>>
>> What we miss right now for preserving correctness
>> w.r.t.
>> Reflection
>> API is a way to track dependencies between final
>> fields and
>> nmethods
>> and invalidate all nmethods which (possibly) embed
>> changed
>> final values.
>>
>> Best regards,
>> Vladimir Ivanov
>>
>> On 9/10/14, 5:04 PM, Remi Forax wrote:
>>
>>
>> On 09/10/2014 02:41 PM, Vitaly Davidovich wrote:
>>
>>
>> I think there's a fundamental problem in
>> trying to
>> "convey"
>> things to
>> the compiler. Clearly, it can't be some
>> metadata
>> approach since
>> compiler can't just trust user blindly.
>> The only
>> way I know
>> to convey
>> things is through code shape.
>>
>> One thing that bothers me is that even
>> fields
>> marked final
>> aren't
>> really treated as such by compiler because
>> it's
>> paranoid of
>> things
>> like reflection.
>>
>>
>> It's not paranoid, most of the dependency
>> injection
>> libraries,
>> Hibernate
>> or serialization code allow you to set the
>> value of
>> final field
>> at runtime.
>>
>> If there was some way to reassure it that
>> final fields
>> aren't modified
>> behind its back, then more type info can be
>> captured at init
>> time
>> (e.g. array is not null and length is
>> captured as a
>> constant).
>>
>>
>> @java.lang.invoke.Stable
>>
>> Rémi
>>
>> Sent from my phone
>>
>> On Sep 10, 2014 6:48 AM, "Paul Sandoz"
>> <paul.sandoz at oracle.com
>> <mailto:paul.sandoz at oracle.com>
>> <mailto:paul.sandoz at oracle.com
>> <mailto:paul.sandoz at oracle.com>__>
>> <mailto:paul.sandoz at oracle.com <mailto:paul.sandoz at oracle.com>
>> <mailto:paul.sandoz at oracle.com
>> <mailto:paul.sandoz at oracle.com>__>__>
>> <mailto:paul.sandoz at oracle.com
>> <mailto:paul.sandoz at oracle.com>
>> <mailto:paul.sandoz at oracle.com
>> <mailto:paul.sandoz at oracle.com>__>
>>
>> <mailto:paul.sandoz at oracle.com
>> <mailto:paul.sandoz at oracle.com>
>> <mailto:paul.sandoz at oracle.com
>> <mailto:paul.sandoz at oracle.com>__>__>__>> wrote:
>>
>> Hi,
>>
>> This method:
>>
>> static int aaload(int[] a, int i) {
>> int index = i & (a.length - 1);
>>
>> return a[index];
>> }
>>
>> compiles to:
>>
>> 0x000000010466a56c: mov
>> 0xc(%rsi),%r11d
>> ;*arraylength
>>
>> ; implicit
>> exception: dispatches to
>> 0x000000010466a5a5
>> 0x000000010466a570: mov
>> %r11d,%r10d
>> 0x000000010466a573: dec %r10d
>> 0x000000010466a576: and %r10d,%edx
>> ;*iand
>>
>> 0x000000010466a579: cmp %r11d,%edx
>> 0x000000010466a57c: jae
>> 0x000000010466a58e
>> 0x000000010466a57e: mov
>> 0x10(%rsi,%rdx,4),%eax
>>
>>
>> For the bounds check there is only
>> one unsigned
>> comparison check
>> since the array length is
>> non-negative (this
>> will also
>> catch the
>> case if "i" is -ve and the array
>> length is 0).
>>
>> If the patch for JDK-8003585 is
>> applied the
>> check gets
>> strength
>> reduced to:
>>
>> 0x000000010d9e06ec: mov
>> 0xc(%rsi),%r11d
>> ;*arraylength
>>
>> ; implicit
>> exception: dispatches to
>> 0x000000010d9e0725
>> 0x000000010d9e06f0: mov
>> %r11d,%r10d
>> 0x000000010d9e06f3: dec %r10d
>> 0x000000010d9e06f6: and %r10d,%edx
>> ;*iand
>>
>> 0x000000010d9e06f9: test
>> %r11d,%r11d
>> 0x000000010d9e06fc: jbe
>> 0x000000010d9e070e
>> 0x000000010d9e06fe: mov
>> 0x10(%rsi,%rdx,4),%eax
>>
>> and if the array is constant or there
>> is a
>> dominating check
>> (hoisted out of a loop) then the
>> bounds check
>> will go
>> away. More
>> on that later.
>>
>>
>> This method:
>>
>> int unsafe_aaload(int[] a, int i) {
>> int index = i & (a.length - 1);
>>
>> // Emulate return a[index]
>> if (index < 0 || index >=
>> a.length)
>> throw new
>> ArrayIndexOutOfBoundsException______();
>>
>>
>>
>>
>> long address = (((long)
>> index) << 2) +
>> UNSAFE.ARRAY_INT_BASE_OFFSET;
>> return UNSAFE.getInt(a,
>> address);
>> }
>>
>> compiles to:
>>
>> 0x000000010495be8c: mov
>> 0xc(%rdx),%r10d
>> ;*arraylength
>>
>> ; implicit
>> exception: dispatches to
>> 0x000000010495bee9
>> 0x000000010495be90: mov %r10d,%r8d
>> 0x000000010495be93: dec %r8d
>> 0x000000010495be96: and %r8d,%ecx
>> ;*iand
>>
>> 0x000000010495be99: test %ecx,%ecx
>> 0x000000010495be9b: jl
>> 0x000000010495beb6 ;*iflt
>>
>> 0x000000010495be9d: cmp %r10d,%ecx
>> 0x000000010495bea0: jge
>> 0x000000010495becd
>> ;*if_icmplt
>>
>> 0x000000010495bea2: movslq %ecx,%r10
>> 0x000000010495bea5: mov
>> 0x10(%rdx,%r10,4),%eax
>> ;*invokevirtual getInt
>>
>>
>> The patch for JDK-8003585 makes no
>> difference.
>>
>> (Note: in general we cannot assume
>> that "int
>> index = i
>> & (a.length
>> - 1)" always occurs before the bounds
>> checks,
>> otherwise
>> i would
>> have explicitly written "if (a.length
>> == 0)
>> throw ...")
>>
>> Ideally similar code as shown for an
>> aaload
>> should be
>> generated.
>> Any suggestions/ideas on how to make
>> that happen?
>>
>>
>> --
>>
>> Regarding removing the bounds checks,
>> as
>> previously
>> referred to.
>> If it is known the array length is
>> always > 0 the
>> bounds check can
>> be removed. The general context here
>> is code
>> in the
>> ForkJoinPool.WorkQueue, such as:
>>
>> final ForkJoinTask<?> poll() {
>> ForkJoinTask<?>[] a; int b;
>> ForkJoinTask<?> t;
>> while ((b = base) - top <
>> 0 && (a
>> = array)
>> != null) {
>> int j = (((a.length -
>> 1) & b) <<
>> ASHIFT) + ABASE;
>> t =
>>
>> (ForkJoinTask<?>)U.______getObjectVolatile(a, j);
>>
>> if (base == b) {
>> if (t != null) {
>> if
>> (U.compareAndSwapObject(a,
>> j, t, null)) {
>> base = b +
>> 1;
>> return t;
>> }
>> }
>> else if (b + 1 ==
>> top) //
>> now empty
>> break;
>> }
>> }
>> return null;
>> }
>>
>> If "array" is not null it's length is
>> always >
>> 0 (a
>> zero length
>> array is never allocated by the code).
>> Is
>> there a way
>> to safely
>> convey that knowledge to the
>> runtime/compiler?
>> thereby
>> enabling
>> removal of bounds checks for any
>> replacement
>> of Unsafe
>> in such code.
>>
>> Paul.
>>
>>
>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140911/66a67085/attachment-0001.html>
More information about the hotspot-compiler-dev
mailing list