Bounds checks with unsafe array access
Vladimir Ivanov
vladimir.x.ivanov at oracle.com
Thu Sep 11 17:04:21 UTC 2014
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.
>
>
>
>
More information about the hotspot-compiler-dev
mailing list