Heisenboxing, Escape Analysis, and HOF-iness.

[Graves, Ian L]

All,

I've been playing around more with the CodeSnippets and Methodhandles as they relate to loop-customization with respect to higher order functionality with the Vector API.

Generally higher order functionality can be constrained by the shape of the vectorization operations we wish to support, which mirror arithmetic operations that are unary or binary operations.  Essentially this means that we're looking at mapping functionality (unary) or zip-style reductions (binary).  So I'm looking to construct kernels that can be represented as binary or unary MethodHandles (eschewing lambdas for now).  In experimenting with this, I've noticed that the Long2/4/8 objects have a particular kind of behavior where they sometimes escape on the heap when I wouldn't otherwise expect them to, but on the flip side, sometimes LongX objects exist only in the ether and are passed around between registers, never to see the light of day.

I've observed code that puts LongX on the heap when the following is uttered:

void someMethod(..){
   Long4 l = Long4.make();
   ...VectorAPI Operations
   return;
}

Usually sees:

  0x00007f58243bd124: mov    QWORD PTR [r15+0x78],r10
  0x00007f58243bd128: prefetchw BYTE PTR [r10+0xc0]
  0x00007f58243bd130: mov    r10,QWORD PTR [rsp+0x18]
  0x00007f58243bd135: mov    r10,QWORD PTR [r10+0xb0]
  0x00007f58243bd13c: mov    QWORD PTR [rbx],r10
  0x00007f58243bd13f: mov    DWORD PTR [rbx+0x8],0x20002725
    |   |   |   |   |   |   |   |   |   |       ;   {metadata('java/lang/Long4')}
  0x00007f58243bd146: mov    DWORD PTR [rbx+0xc],r12d
  0x00007f58243bd14a: mov    QWORD PTR [rbx+0x10],r12
  0x00007f58243bd14e: mov    QWORD PTR [rbx+0x18],r12
  0x00007f58243bd152: mov    QWORD PTR [rbx+0x20],r12
  0x00007f58243bd156: mov    QWORD PTR [rbx+0x28],r12


For utterances of Long4.make(), as well as some invocations of the VectorAPI that result in a new Vector object that is derived from existing values in registers.

It seems as though that these objects are reified from their heisenvalues (forgive me) if they "fall off" the end of some dependency chain.  For a simple make() of a LongX object, the value is created and thus has to live somewhere, so it gets placed on the heap(?).  For VectorAPI computations and even MethodHandle invocation chains, I've seen similar code generated when a LongX value/object has to be realized as the result of executing a chain of MethodHandles.

What I'm not clear on is whether this is an artifact of escape analysis missing something or if it's an artifact of heisenboxing, or even if it's some interplay of both.  What I have noticed is that there are programming patterns that can prevent these values from being reified by never accepting or returning LongX objects.  In the case of running a binary HOF-style operation on two arrays if you structure a MethodHandle invocation chain such that it takes the two arrays as input and sinks the result into another array, never returning a LongX object, you can dodge the issue of having to realize the object at runtime.

//Something akin to:
void binaryOperation (float[] left, float[] right, float[] dst, MethodHandle kernel){
    for(int i=0; i < left.length; i+=VECTORSIZE)
       kernel.invokeExact(left,right,dst,i);
   return;
}


Incidentally, this approach is also similar to one's we've discussed online[1] and others discussions that have occurred offline.  Code Snippets are all in MethodHandle and we can use MethodHandles to meaningfully structure their composition under the hood.  We can hide this composition under something like VectorOp, or even a light-weight ad-hoc, type-parameterized, syntax tree system for specifying vectorizable kernels.

What I'm not sure about is that if this approach is a bit too out there (it's quite monadic!) or arising as a defense against a lack of relief from optimizations that we can easily add.  Would appreciate thoughts and feedback on the above.  I'm certain these topics will also come up at JVMLS, but wanted to get them out in advance, too!

Thanks!

--Ian

[1] http://cr.openjdk.java.net/~jrose/arrays/vector/VectorOp.java