Sunday, January 08, 2012

The invokedynamic API

I thought I should write a bit about the invokedynamic API, since the API is very powerful and flexible, but sometimes needs a bit getting used to it. I won't write about everything or even in detail, just some hints for thinking on a few elements - the ones I used for Groovy mostly and are most probably the ones you will use as well.

Let us say we are in the situation, that we have the method we want to call as handle already and we have the target type of our call site. I call that method handle SM (for selected method) and the target type TT - for obvious reasons.

Now normally in Groovy you would do the following: you transform the arguments into a form you can use for calling the method. If you for example have an int, but want to call an long taking method, then you have to transform the int into a long. You normally do this by using a general type transforming method, that takes the argument and a goal type, inspects the argument and then goes through quite big code parts for all the transformations that are allowed. We do this not during method selection itself, but for each call of course. What we do is kind of like wrapping the method object into something new, that we can call in our call site and that for each call will test if it has to apply the big standard transformation - and well, apply it too.

If you read that big transformation code, then you will have a direct transformation of the arguments to whatever the SM needs. In invokedynamic we work a slightly bit different. Instead of having only one transformation we have many small ones, that we combine into a specialized one. We do this by taking our SM, apply transformers to it and use the result for our method calls. Since the main work is now no longer correcting the big transformer code, but the combination of the many small transformers the workflow feels kind of reversed to me. You now want to apply transformers to make out of your SM, one that accepts the target type TT.

Some notes for better understanding:

  • One thing to remember when working with MethodHandles for example is that it has no receiver. In a method call foo.bar(x), we say normally that foo is the receiver (well the class of foo), bar the method name and x the argument. For a MethodHandle it itself is the receiver of course. So if we work on its arguments, then the first argument is the receiver of our method call. A MethodHandle for above would maybe have this MethodType: (Foo,X)Object - taking the foo receiver and an x argument, returning an Object.
  • The classes you work with mostly... You have MethodType to describe a method's parameters, including return type and receiver. There is MethodHandle of course, the core of it all, representing your SM. And there is a collection of helper methods in the class MethodHandles. Note the additional s. Well, and SwitchPoint, but I haven't used it really yet... that is still to come soon.
  • Type matching... your SM has to be changed by the usage of the transforms to fit the requested target type of your call site. For this you use for example asType

But without further delay...

MethodHandles#dropArguments is one quite useful method, that at the same time shows very much the reversed thinking that needs to be applied. This is a transform, that will drop arguments, it does not do it right away. In the old thinking we have for example arguments a,b,c and if we would drop there, we would for example get a,b. This transform *will* do exact this, but what we look at gives a different impression. We have a handle that takes A,B (A being type of a and B being type of b) and dropping then means we will take that and produce a new handle that can take A,B,C. This new handle will then ignore the argument c of type C and in doing so, it does exactly what I described above, but if we debug the code producing the combinations of transformers we see a method handle that gets the dropArguments transformation applied and now takes one more argument instead of one less. So again.... assuming you want to get rid of an argument you start with the handle, that is without it and have to transform it into a handle that takes it... for me that is like reversed thinking and really sometimes produces problems for me. You may want to apply this one if your SM takes less arguments than provided.

MethodHandle#bindTo is also one I use often. Assuming we have a handle taking A,B,C and A will be the same for each call, we can bind it to produce a new handle taking B,C... but only for the first argument. So for example if you have a method call that will be done through the meta class system, then this results mostly in calling a method MetaClass#invokedMethod. But the receiver there is not the receiver from my callsite, so I bind the first argument, the meta class. A changed meta class would require a new method selection so it is kind of constant for this selection. You may want to apply this one if your SM has one more argument than the ones provided and it is the first one

But what to do if we have more than one extra argument our SM would like to take? In this case you use MethodHandles#insertArguments. For example your SM would like to take A,B,C, your TT is A,B and you want to bind a c. Then you can use newHandle = insertArguments(oldHandle,2,c).If it where A,B,C,D, and you want to bind for C and D, then it is insertArguments(oldHandle,2,c,d). If you have A,B,C,D and you want to bind B and D, then it is for example (there are two ways): newHandle = insertArguments(oldHandle,1,b); newHandle = insertArguments(newHandle,2,d). You may have noticed the chaining of transforms in this one. The first makes A,B,C,D into A,C,D, moving D from position 3 to position 2. The second makes A,C then. You may want to apply this one if your SM has more arguments than the ones provided.


MethodHandle#asCollector is also a nice one. There are several invokeMethod methods in Groovy that take an Object[] as argument to contain all the arguments and then delegate calls to builders or do other things. The callsite you start with though may not provide the Object[], but the arguments one by one. So your TT may look like this: A,B,C,D and your SM may accept this: A,Object[]. Meaning we somehow have to wrap B,C,D into an Object[], if thought from the perspective of the arguments. And that is why the method is called asCollector. What you see on your method handle is that with handle = handle.asCollector(Object[].class, 3), your A,Object[] handle is now a A,Object,Object,Object handle. You will need asType to get to the final form. Should you want to collect the arguments at a different place than the last one, you may have to permute the arguments. The opposite way is asSpreader, but I didn't use that one yet. I may do so when I extend the implementation to include the spread operator. You may want to apply this one if your SM has arguments you want to collect into an array

Sometimes we have to make an transformation, that changes the runtime class of a reference type. This is of course not possible, because the JVM is strong typed - but we can create a new object with the desired result. For example Groovy has GString, which is a kind of String. A method call done with an GString argument is supposed to be able to call a method that takes a String. Now GString and String are not in a subclass relation, meaning that we will have to do a real type transformation here and MethodHandles#filterArguments will help us with that. A filter takes one argument and returns the transformed value. For our case it should take a GString and return a String. Let us say our SM takes A,String,String,B; TT be A,GString,GString,B and our filter MethodHandle takes GSTRING. Then we can simply do newHandle = MethodHandles.filterArguments(oldHandle, 1, GSTRING, GSTRING) to produce a handle for A,GString,GString,B. Again I had here some problems with the reversed thinking: The filter's return type must match the type in the SM and the argument type the type of our TT. If you think about it, it is quite clear and obvious, but when I work on a program I always have to stop here and rethink. Anyway... You may want to apply this one if your SM argument differs form the provided argument in a way that boxing and casting alone don't do the transformation requried.

And the last one I want to mention: MethodHandles#guardWithTest. In many situations you have to handle the invalidation of your call site to some extend. One way is for example (if you use a MutableCallsite) to have a guard causing exchanging the target for your callsite by a new method selection. Let us assume we have a call foo(a,x) and the methods foo(Object,Object) and foo(Object,String). Now x may be a String and we want to call foo(Object,String) then, or we want to call foo(Object,Object) if it is not String. Let us assume there will be three calls: The first done with an Integer, the second with String and the last one with an Integer again. We will have to exchange the method each time. A guard takes a number of arguments (0-N) and returns a boolean, which will be used to determine if we call our normal target or a fallback handle. For this case here I have used a handle called SAME_CLASS. It takes a class and an Object argument and tests if argument.getClass() is equal to the provided class. Since the first argument, the class, is fixed I bind it upfront, leaving me a guard handle which takes an Object argument only. guardWithTest does not support any position, but we want to check the second argument to the method, not the first... and there is the receiver too. If you did not jump to this section, then you may find we are in a situation in which we have less arguments than given... only it is not the SM, but our guard now. But that doesn't matter. Still we drop the first two to get a handle Object,Object,Object, which will ignore the 0 position argument, the receiver, and the argument at position 1, but test the one at position 2. Then it is simply newHandle = MethodHandles.guardWithTest(guard, oldHandle, fallback) and be done with it. If you want to have multiple guards, you continue to apply this kind of transform. I haven't found a way to combine guards themselves to have only one guardWithTest call. But maybe that isn't needed too. You may apply this one if your call site needs to be invalidated based on the given arguments.

This is just a short overview and by far nowhere near complete or a replacement for reading the javadoc. Just a little guide that may be of help.

8 comments:

thurston said...

Hello Jochen,

I was looking into the invokedynamic bytecode instruction, and I have to say I'm a bit perplexed.
Take the method used as an example on the java site (http://docs.oracle.com/javase/7/docs/technotes/guides/vm/multiple-language-support.html):

def addtwo(a, b)
return a + b;

btw, this is of course a perfectly valid groovy method.

I assumed groovyc would compile that method like this(elliding some and pseudo bytecode):

aload-b //(push b on stack)
aload-a //push a on stack)
invokedynamic 'bootstrap-method' '+' (Object,Object)Object

My assumption is that the run-time objects a and b would be passed to the bootstrap method (by the JVM)!!
But in looking at the documentation more closely, that isn't correct. a and b are never passed to the bootstrap method, their types are passed to the bootstrap method (as a MethodType).
But the MethodType is 'resolved' at compile time, i.e. it's a constant, but of course groovyc can't know their types (they can only be determined at run-time)

So isn't groovyc left pretty much in the same place as before invokedynamic?
You'd have to have a huge switch-like statement to branch to the invokedynamic ... "(Integer, Integer)Integer" or
invokedynamic ... "(String, String)String" or
.... (and so on)

Surely, I'm missing something

Jochen "blackdrag" Theodorou said...

@thursten
You are right, the bootstrap method will get only the static types. The trick is to make it a two step approach. In the first step we are in the bootstrap method and direct the call to a general method selector. In the second step this method selector will give the callsite the real target. in this second step I have the objects of the callsite call and can react to the dynamic types. This also means that only on the second invocation of the method you will have the target method being called directly.

thurston said...

"In the first step we are in the bootstrap method and direct the call to a general method selector"

I'm assuming that you mean by this that the boostrap method returns a MethodHandle (via the returned Callsite object) that is a reference to a "general method selector (gms)", and this gms (in the addtwo example) would have a signature of Object (Object o1, Object o2).

And then within the GMS you do the 'real' method 'linkage'? How do you get the reference to the Callsite object (because the JVM won't just automatically pass it as an argument when the GMS is invoked) that the bsm returned? I'm assuming in some ungodly global map.

I guess I still don't see how this is going to produce drastic performance speedup. It seems that groovyc could (and probably is) doing this already (without invokedynamic).

Not to mention of course that if the groovy script has:

addtwo(5, 10);
addtwo("Hello", "world");
addtwo(new Date(...), 5)

the CallSite (in the addtwo method) will have to be 're-linked' anyway

Jochen "blackdrag" Theodorou said...

You are partially right with the gms. The call site will have the signature... in invoke dynamic speak... the target type (Object,Object)Object, but the selector method can be different. IN the bootstrap method I first get a handle to the selector method, then I transform that handle to make it fitting to the needs of my callsite. So it is perfectly possible to have a selector method with a signature (Object, String, Object[])Object for example. The "a" would go into the first object, the String would become "plus" and the "b" would go via asCollector transformation into the Object[]. I can also produce a handle with bound values to transport flag and the MutableCallSite object. So no ungodly global map needed for that ;) This ability to bind arguments is actually an essential feature. Otherwise I would not have been able to for example solve the issue with enabling calls on null for Groovy.

But you are right, that groovyc can go without invokedynamic. Alex Tkachman introduced an inline call site cache in Groovy 1.6 already. There are several problems with that though:
(1) the Groovy call site cache produce helper classes, which is bad for permgen. MethodHandles do not.
(2) the Groovy call site cache cannot handle primitive arguments and thus needs them boxed. MethodHandle can do.
(3) the Groovy call site cache makes the bytecode almost unreadable and expand the size of it. The invokedynamic way is almost as lean as the direct method invocation way and the method names are directly visible again, thus leading to shorter and better bytecode. Shorter bytecode is important for the JIT
(4) the Groovy call site cache depends on continuous checks against volatile structures, MethodHandles not. The problem with such structures is, that they prevent any JIT action in the current HotSpot
(5) the usage of invokedynamic encourages the JIT to a more aggressive inlining. As I understand it, this last part is not yet always the case. Later versions will contain much tweaking still here.
(6) Not directly MethodHandles based.. but ClassValue allows us to dynamically bind values to classes. Current it is here where we have to use an ungodly global structure, which will be removed completely in the future.

As for performance... the mostly not yet optimized implementation performs already at about the same level as Groovy call site caching. So I am positive there are performance improvements. If thy are drastic I cannot tell yet though. Compared with the primitive optimizations of 1.8 they still have to go some longer way.

As for relinking... you are right about that part. That is where a simple inline cache as Groovy uses it now, also has problems. There are ways to solve that case as well and in the long term Groovy will get that. But of course that is not really special to invokedynamic, as current Groovy call site caching would improve with such a logic as well.

thurston said...

Well, keep in mind that MethodHandle does not imply invokedynamic.
Clearly MethodHandle obviates
"helper classes" (nee a class per method)
which are only used (AFAIK) because java.lang.reflect.Method is painfully slow

I guess I was originally thinking (again with some ellision):
MethodHandle mh = GroovyDispatcher.resolve("+", a, b)
return mh.invokeExact(a, b)

After all, GroovyDispatcher.resolve is, in essence, your selector method and in any case must still be called at least once.
This was the source of my original confusion: the so-called bootstrap method doesn't actually do any real method 'linkage'!

Now of course the code suggested above doesn't make any concession to Callsite (MethodHandle) caching (which IIHTG is the real performance winner). I can think of a few possibilities (all of them ugly).
But even with invokedynamic there isn't going to be any direct method invocation (to GString.plus, Number.plus, Date.plus, etc), because you have to dynamically "reverify" the Callsite each and every time (which makes MethodHandle.guard(...) and other MH transforms so awesome--I do see that).

As far as the JIT optimizations, I can't say but I'm confident your right.

Just curious, how much can your "method resolution" code be refactored to use the Lookup.find* methods? Because of course those methods don't 'do' double-dispatch and of course know nothing about .metaclass's etc.

Jochen "blackdrag" Theodorou said...

You are right, MethodHandle doesn't imply invokedynamic. Later versions of Java 1.7 will probably have the ability to recognize a method call made on a handle and thus do the more aggressive inlining it does for indy too. That is the point where MethodHandles should be finally much faster than reflective invocation.

As for the GroovyDispatcher... yes, it must be called at least once. If you take normal Java, then you wouldn't need such a dispatcher. You can there do everything you need to do in the bootstrap method already, solely depending on the static types. That is for example because MethodHandles can do invokeVirtual and invokeStatic. So the bootstrap method can do the actual linkage if the logic of the language permits it. And for Groovy that is not the case. For once we have a method selection depending additionally (additionally to Java) on the runtime types of the arguments, in some cases we replace the receiver and in other cases we call a whole different method.

And yes, I have to reverify the call site every time. But there are some tricks I can use to minimize the usage of them. If there is the static type information that the operands for the plus are primitives, then I can actually skip the check that a and b are still int every time I do the call. I can do that because an int is an int and is not going to change. I can do the same for objects if the argument's static type of the class is final. That again is based on the thought that it cannot change then. There is an additional argument check I have to do and that is for null. In case of a null argument we take the most general type as fitting instead of the most exact. In Other words if you have foo(String) and foo(Object) then even if the static type of your argument is String, we will still call the foo(Object) method if the actual argument value is null. On the other hand I can omit this check if there is only one method. Doing those two optimizations will cause Groovy to be faster if you use static type information for primitives or final classes as arguments and if the method is not overloaded.

So direct method calls to int.plus(int) will be possible

As of how much my method resolution code can be refactored to use Lookup.find* methods.... At the moment, not at all. As you said, they don't do double dispatch. For now I ask the meta class for the MetaMethod to be called, and from there I create the method handle. It would be of course better to have the handle in the MetaMethod too, but this is a bit difficult with the current API. Currently the user can make MetaMethods by his own. That means the API would reveal JDK7 stuff, which means Groovy2 would not be usable with a JVM before 1.7. I guess this part will have to wait for Groovy 3 next year, unless I find a way around this. It would certainly help reducing one time costs, and sadly many callsites are called only once or twice.

Actually I am also thinking of adding a counter and not to do actual MethodHandle based code unless the call site has been called a certain number of times, to avoid these one time costs. Would be nice if I found a way to do this in the bootstrap method already, we will see.

Anyway, Lookup.find would then be done much later, cached and lazy initialized in the meta class logic.

Calls without actually getting the meta class could be done as well in some cases... for example if the receiver runtime class is the same as the static class of it. In that case a findVirtual would be sufficient. Well, if there are no meta class changes that affect this. But I see that as possible. Actually this might be an interesting thing to implement.

thurston said...

"If you take normal Java, then you wouldn't need such a dispatcher. You can there do everything you need to do in the bootstrap method already, solely depending on the static types"

But of course! In normal Java, there would be no bootstrap method, invoke[special|interface|virtual] work quite nicely thank you. (in fact, in 1.7 there is no Java source that can produce an invokedynamic bytecode--although I've heard that lambda (closures) will produce one).

As far as MethodHandle.invoke* vis a vis reflect.Method.invoke, I thought I saw some pretty compelling benchmarks somewhere (and that is certainly the advertisement). If I find the link, I'll send it to you

Jochen "blackdrag" Theodorou said...

Yes of course, for Java the normal ways of invoking a method do just fine. I did just mean if you wanted to use indy for that, then you wouldn't need to go beyond the bootstrap method. And it is the same for languages "like" Java, in which you have enough static information to give indy what it needs to handle the case in the bootstrap method already. Of course it is questionable if you would want to use indy, if you are just fine with using the normal ways ;)

Yes, lambda is going to make use of MethodHandles. As of to what extend, no idea, I am not part of that EG ;)

As for MethodHandle vs. reflection... there is a big difference between those in terms of permission handling. If you invoke a method reflective, then the permissions are more or less checked each time, you do the invocation. For MethodHandles this is done once you create the handle. So if you reuse the handle it will provide superior performance.