<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div></div><div>FTR, here are some observations on optimizing new acmp semantics which will help motivate adopting the L-world design. <br><br></div><div><b>From:</b> John Rose <<a href="mailto:john.r.rose@oracle.com">john.r.rose@oracle.com</a>><br><b>Date:</b> January 29, 2018 at 9:42:49 PM GMT+1<br><b>To:</b> valhalla-dev <<a href="mailto:valhalla-dev@openjdk.java.net">valhalla-dev@openjdk.java.net</a>><br><b>Subject:</b> <b>optimizing acmp in L-World</b><br><br></div><div><span>Tobias, Roland, and I had a chat in Santa Clara last week</span><br><span>about optimizing the acmp operation in the JVM.  Here are</span><br><span>my notes on it.</span><br><span></span><br><span>Background:  The acmp operation, also known as reference</span><br><span>comparison, is overloaded in L-World to handle values as well,</span><br><span>with a specific semantics of returning false if either operand is</span><br><span>a value (similar to NaN behavior for fcmp).  The rationale for</span><br><span>this is that acmp is reference comparison, even in L-World,</span><br><span>and since values have no references, they can never be</span><br><span>equal as references.</span><br><span></span><br><span>(Alternatively, it is *as if* both operands were converted</span><br><span>*to references* before the acmp operation, which means</span><br><span>that either operand, if it is a value, *would be* boxed to a</span><br><span>reference value, which then, being a new reference, is</span><br><span>automatically unequal to any other reference.  This tricky</span><br><span>account may be appealing in some circumstances.)</span><br><span></span><br><span>OK, so how do we make it fast?  Ideally, we would like</span><br><span>to strength-reduce the enhanced acmp instruction down</span><br><span>to the original acmp instruction, which after all is just a</span><br><span>single instruction (such as cmpq) on all platforms.</span><br><span></span><br><span>The first thing to notice, before going into details, is</span><br><span>that in L-world all Q-values are buffered in the interpreter.</span><br><span>This means that, at least for interpreter-generated values,</span><br><span>all values can be treated as physical pointers, even</span><br><span>if they are logically Q-values.</span><br><span></span><br><span>(Crib sheet:  In L-world, all kinds of values except primitives</span><br><span>are formally carried by L-values, under L-descriptors.  True</span><br><span>references can be referred to as R-values of R-type, reference</span><br><span>type, or object class.  New value types are referred to as Q-values</span><br><span>of Q-type, value type, or value class.  When you don't know what</span><br><span>you have, you can say it's a U-type, which just like a Q-type or</span><br><span>R-type is carried by an L-value under an L-descriptor.)</span><br><span></span><br><span>This means that the old acmp semantics are almost correct,</span><br><span>in many cases.  If you have two L-values and do a pointer</span><br><span>comparison on their physical pointers, and if the pointers</span><br><span>differ, you are done.  If the physical pointers compare equal,</span><br><span>then there is one more thing you have to do:  Make sure that</span><br><span>the L-value carried by both physical pointers is in fact a</span><br><span>reference, an R-value.</span><br><span></span><br><span>So the logic looks like this, and the new semantics are in</span><br><span>the second "if" statement:</span><br><span></span><br><span>  bool new_acmp(ptr x, ptr y) {</span><br><span>    if (!old_acmp(x, y))  return false;  // x != y => false</span><br><span>    if (is_value_ptr(x))  return false;  // x.is_value => false</span><br><span>    return true;</span><br><span>  }</span><br><span>  bool old_acmp(ptr x, ptr y) {</span><br><span>    return x == y;  // cmpq etc.</span><br><span>  }</span><br><span></span><br><span>Note that since acmp is symmetric, the JVM has the option</span><br><span>to silently test either x or y for "is_value_ptr" if the two physical</span><br><span>pointers compare equal.</span><br><span></span><br><span>This leads immediately to the first set of optimizations, which</span><br><span>probably are enough to get us where we want to go.  (There</span><br><span>is a second set we can add later.)  All the JVM has to do is</span><br><span>prove or detect that one or the other physical pointer either</span><br><span>*is certainly* a Q-value, or *is certainly not* a Q-value.</span><br><span></span><br><span>If either physical pointer is certainly a Q-value, then the</span><br><span>new_acmp instruction is a constant false.  If either physical</span><br><span>pointer is certainly not a Q-value, then the new_acmp</span><br><span>instruction strength reduces to the old_acmp instruction.</span><br><span></span><br><span>The strength reduction to false can be done in any place</span><br><span>where the type of either operand is known to be a Q-type.</span><br><span>The interpreter doesn't track types, and the acmp instruction</span><br><span>isn't resolved so it can't be quickened to a type context,</span><br><span>but the JIT has lots of type information.  Thus, if either</span><br><span>operand of acmp is statically known (or accurately speculated)</span><br><span>to be a value type, then the acmp instruction constant folds</span><br><span>to false.</span><br><span></span><br><span>Likewise, if either operand is known to be an R-type</span><br><span>(true reference) the acmp may be strength reduced to</span><br><span>a simple reference comparison.  This also is likely to</span><br><span>happen in the JIT.  It also happens in the interpreter</span><br><span>in the acmp_null instruction, where (obviously) the</span><br><span>second operand is a reference (i.e., null).</span><br><span></span><br><span>(Note that the type Object is a U-type in L-world, so</span><br><span>Object-to-Object comparisons such as are found in</span><br><span>generic collection code do not benefit from this</span><br><span>optimization.  More later on that.)  </span><br><span></span><br><span>The JIT can also track, in its profile, whether various</span><br><span>instructions "see" only Q-values or only R-values.</span><br><span>(The classic HotSpot already tracks "sightings" of</span><br><span>null for similar purposes.)  In that case, speculative</span><br><span>narrowings (only Q-types or only R-types) can be</span><br><span>used to short circuit new_acmp down to old_acmp.</span><br><span></span><br><span>This is useful because the speculation can sometimes</span><br><span>be verified out of a loop body, where the actual acmp</span><br><span>instruction is executed in a loop.  Remember that the</span><br><span>JIT can choose which operand of acmp to test for</span><br><span>value-ness; if it chooses a loop invariant, and the</span><br><span>invariant is always Q or always R, then the acmp</span><br><span>inside the loop folds up, no matter what the dynamic</span><br><span>value of the other operand.</span><br><span></span><br><span>For that matter, even if speculation fails, loop</span><br><span>unswitching can get to a similar result, at the cost</span><br><span>of two copies of the loop.</span><br><span></span><br><span>So, in many cases, contextual information can allow</span><br><span>the JVM to fold up new_acmp to old_acmp or constant</span><br><span>false.</span><br><span></span><br><span>In cases such folding fails, there is as simple trick</span><br><span>which can make things easier.  Recall that folding</span><br><span>fails when *both* operands are statically U-types,</span><br><span>*neither* operand folding to a Q-type or R-type.</span><br><span></span><br><span>In that case, the JVM must pick one operand or</span><br><span>the other (it doesn't matter which) and perform</span><br><span>the is_value_ptr operation on it, in such a way</span><br><span>that the result of that operand affects the final</span><br><span>result in the correct way.  A naive implementation</span><br><span>of new_acmp adds an extra test-and-branch</span><br><span>to fold in the is_value_ptr test, but a clever might</span><br><span>be able to avoid it.</span><br><span></span><br><span>Suppose there is a branch free technique for</span><br><span>implementing is_value_ptr, such as extracting</span><br><span>a bit from the physical pointer to the U-value,</span><br><span>or (after a null check) extracting a bit from the</span><br><span>physical pointer of the class metadata pointer</span><br><span>in the value's header, or (after two indirections)</span><br><span>extracting a bit from the structure of the class</span><br><span>metadata.  (Mr. Simm's prototype puts such</span><br><span>a bit in the metadata pointer, in the object</span><br><span>header.)</span><br><span></span><br><span>If such a bit can be obtained in a branch-free</span><br><span>manner, then it can be used to perturb the result</span><br><span>of the old_acmp in a useful manner.  For example:</span><br><span></span><br><span>  bool new_acmp(ptr x, ptr y) {</span><br><span>    if (x == null)  return y == null;</span><br><span>    int bit = (x->class_in_header & Q_TYPE_BIT);</span><br><span>    ptr x1 = x | swar_broadcast_bit(bit != 0);</span><br><span>    return old_acmp(x1, y);</span><br><span>  }</span><br><span>  int swar_broadcast_bit(bool z) {</span><br><span>    return z ? -1 : 0;  // use ALU ops</span><br><span>  }</span><br><span></span><br><span>The idea is to extract a bit which signals the presence</span><br><span>of a Q-type (in either operand) and use it to "mess up"</span><br><span>the equality comparison, using and, or, or xor as needed.</span><br><span></span><br><span>This perturbation technique has two costs:  First,</span><br><span>it requires a null check (unless the Q-bit is in the</span><br><span>actual physical reference).  Second, it requires</span><br><span>an ALU operation or two to spread the perturbation.</span><br><span>But these costs will probably be negligible, except</span><br><span>(perhaps) in very tight loops in generic code.</span><br><span></span><br><span>Generic code loops performing frequent acmp operations</span><br><span>on untyped (Object) operands will need to perform</span><br><span>extra null checks and/or value/reference detections</span><br><span>if they are not already present (by luck) in the loop</span><br><span>context.  In this case, loop unswitching may be useful.</span><br><span></span><br><span>There is one more contextual operation which may be</span><br><span>helpful in such cases, if all else fails (and loop unswitching</span><br><span>is not desirable).  Honestly, I haven't seen any real-world</span><br><span>code yet that needs it, but it is comforting to have as a</span><br><span>fall-back.  The idea is this:  If the acmp is contextually</span><br><span>followed by a call to Object.equals, in the usual Legacy</span><br><span>Idiom For Equality (L.I.F.E.), then there is one more trick</span><br><span>we can play.  We'd like to force the new_acmp down to</span><br><span>an old_acmp in these cases.  Can we?  Here's the choice:</span><br><span></span><br><span>  bool dutiful_life(ptr x, ptr y) {</span><br><span>    if (new_acmp(x, y))  return true;</span><br><span>    return x->Object_equals(y);</span><br><span>  }</span><br><span>  bool clever_life(ptr x, ptr y) {</span><br><span>    if (old_acmp(x, y))  return true;</span><br><span>    return x->Object_equals(y);</span><br><span>  }</span><br><span></span><br><span>Note that the only semantic difference between old_acmp</span><br><span>and new_acmp arises when *both* operands are the *same*</span><br><span>value.  (Work out the cases:  In every other case, the simple</span><br><span>pointer comparison detects the difference and produces the</span><br><span>correct "false" answer.)  Thus, in the L.I.F.E., the only case</span><br><span>where old_acmp gives the wrong answer produces an</span><br><span>immediate answer of "true", instead of following up with</span><br><span>a call to x.equals(x) on the Q-value.</span><br><span></span><br><span>To put it in a nutshell, the only difference between dutiful_life</span><br><span>and clever_life is that the former always calls Object::equals</span><br><span>if either operand is a value, and the the latter calls</span><br><span>Object::equals in a subset of those cases (when the</span><br><span>physical pointers differ).  When the physical pointers</span><br><span>do *not* differ, there is no call to Object::equals.  But</span><br><span>clever_life always delivers the same answer as dutiful_life.</span><br><span></span><br><span>So is there a problem?  Not much, although it requires us to treat</span><br><span>Object::equals as an intrinsic with some predictable semantics.</span><br><span>The crucial inside that allows us to adopt clever_life is that,</span><br><span>if you call x.equals(x) on a non-null x, the result must always</span><br><span>be true.  Now, this is not enforced by the JVM, but it is clearly</span><br><span>documented in the API specification for Object::equals, and</span><br><span>lots of stuff would be already broken if that were ever false.</span><br><span></span><br><span>Thus, if we are willing to rule out implementations of Object::equals</span><br><span>for which a value can ever compare *not equal* to itself, then</span><br><span>we can substitute clever_life for dutiful_life.  We also have to</span><br><span>allow one more thing:  That we can silently drop calls to equals</span><br><span>(at least in the context of L.I.F.E.) when the JVM can prove that</span><br><span>the contract of equals allows the JVM to predict the outcome.</span><br><span>This means that if you put side effects (like print statements)</span><br><span>into an equals method on a value type, you might not see the</span><br><span>side effects, after the JVM has optimized things.  This corner</span><br><span>case may require further thought in order to straighten it out.</span><br><span></span><br><span>Note that L.I.F.E. is frequently found in generic code, where</span><br><span>instead of operating on Object values it operates on type</span><br><span>parameter types.  (The JVM just sees Object, after erasure.)</span><br><span>In that case, if the JVM were to specialize the generic code</span><br><span>separately for some types (such as value types), along the</span><br><span>lines of the template class proposals, then the L.I.F.E.</span><br><span>code would fold up in the JIT using the rules given at the</span><br><span>top of this note.  The generic expression "a == b", where</span><br><span>a or b was a value of a specialized type parameter T,</span><br><span>would fold up to false in every specialization where T was</span><br><span>a Q-type.  Likewise, as noted above, if L.I.F.E. is applied</span><br><span>to a true R-type (or specialized to such a type), then any</span><br><span>new_acmp on that type can be short-circuited to the faster</span><br><span>old_acmp.</span><br><span></span><br><span>All in all, it appears that the cost of the new acmp semantics</span><br><span>can, for all practical purposes, be pushed down into the noise.</span><br><span></span><br><span>— John</span></div></body></html>