Groovy invokedynamic caching problems

Hi all,

reminded by that mail from MG I decided it is best to forget about 
writing something formal or anywhere near detailed instructions and just 
write what I think should be done and what the current state is. And 
don't get me wrong... this is neither the first try nor the first 
version of the logic I am trying to show.

How things currently are working is that we do a double dispatch. First 
a java style call to the bootstrap method, that then calls another 
bootstrap method. Reason is the first call will have only static types, 
while the second call will have the real types and our dispatch depends 
on the real types. We then go into our cache, which is broken for static 
method calls btw, and if there is no fitting method we select another 
one with our method selection to then create a MethodHandle for this, 
which we then invoke ourselves. That is a super short version of what we 
do in hundreds of lines of code that is thanks to the MethodHandles API 
not very nice to read.

There are, besides bugs, 2 problems with this approach:
(1) we invoke the method in IndyInterface, which is not great when it 
comes to things like @CallerSensitive or the module system.
(2) we create a lot of MethodHandles on the first run. The later is 
especially a problem in bigger applications if they tend to visit a lot 
of code only a few times. Creating MethodTypes for MethodHandles is 
quite expensive, more so than a reflective call. Or our old call site 
caching. Yes, in the end MethodHandles are faster, but only once 
optimizations have run. And that takes thousands of iterations. MG for 
example has been hit by this.

Now what I think how things should be...
first of all, we need a proper slow path. That is where the invocation 
will not be the fastest, but otherwise cheap. Our method selection 
itself is not that slow.

So I think what should happen is method selection and then reflective 
information on the MetaMethod to get the Method and then not invoke, but 
set it as target or fall back to the invocation of the MetaMethod plus 
exception unwrapping. I call this SLOW_PATH_0 In pseudo code:

SLOW_PATH_0 = {
   metaMethod = selectMetaMethod(receiverAndarguments)
   if (metaMethod has Method) {
     continue with Method.invoke
   } else {
     continue with MetaMethod.invoke
   }
}

We can also add a counter to the callsite and say that if this slow path 
is called X times, we want to have something more specific.


callsite target = {
   if (counter < THRESHOLD) {
     increase counter for slow path
     continue with SLOW_PATH_0
   } else {
     reset counter for slow path
     install FAST_PATH[1] /* new callsite target */
     continue with SLOW_PATH_0
   }
}

That means the invocation would at first install the handle, but the new 
handle would be actually used only on the next call.

FAST_PATH[1] would basically consist of

if (receiverAndArguments fit FAST_PATH[1] unreflected Method) {
   continue with unreflected Method
} else {
   increase counter for slow path
   continue with SLOW_PATH_0
}

And "install FAST_PATH[X]" would basically get the MetaMethod und if it 
has a reflective Method we would unreflect that to create a handle and 
install the handle as FAST_PATH[X]

 From here on we could do different things. In this version we would end 
up with the slow path all the time if our fast path selection was not 
good. We can add more fast paths:

if (receiverAndArguments fit FAST_PATH[1] unreflected Method) {
   continue with unreflected Method
} else {
   if (receiverAndArguments fit FAST_PATH[2] unreflected Method) {
     continue with unreflected Method
   } else {
     if (receiverAndArguments fit FAST_PATH[3] unreflected Method) {
       continue with unreflected Method
     } else {
       reset counter for slow path
       install FAST_PATH[4] /* new callsite target */
       continue with SLOW_PATH_0
     }
   }
}

Above an example for 3 fast paths. As a note: I am using if-else this 
way here because that represents a guard check in form of a MethodHandle 
consisting of a handle to check the condition, one for the if-branch and 
another for the else-branch. Of course we should not let that overgrow 
or we will never get a chance to have this optimized. Let's say we limit 
this to 3 and we have them in an array on the callsite object, we can 
have something like this:

if (exists [1] and is fitting) {
   continue with unreflected Method 1
} else {
   if (exists [2] and is fitting) {
     continue with unreflected Method 2
   } else {
     if (exists [3] and is fitting) {
       continue with unreflected Method 3
     } else {
       increase counter for slow path
       if (counter > threshold) {
          install next FAST_PATH in callsite array
          continue with SLOW_PATH_0
       } else {
          continue with SLOW_PATH_0
       }
     }
   }
}

This could be even installed as ConstantCallsite, which is better for 
optimization. As I said, on the callsite we could have an array with 
elements of

class FastPath {
   Class[] receiverAndArguments
   MethodHandle unreflectedMethod
}

plus a

fastPaths = new FastPaths[3]
lastFastPath = 0

and "install next FAST_PATH" would be then:

if (lastFastPath<3) {
   callsite.fastPaths[callsite.lastFastPath++] = new FastPath(..)
}

or with a simple method of rotation:

callsite.fastPaths[2] = callsite.fastPaths[1]
callsite.fastPaths[1] = callsite.fastPaths[0]
callsite.fastPaths[0] = new FastPath(..)

or we add aging:

increase age
if (exists [1] and is fitting) {
   set age[1]
   continue with unreflected Method 1
} else {
   if (exists [2] and is fitting) {
     set age[2]
     continue with unreflected Method 2
   } else {
     if (exists [3] and is fitting) {
       set age[3]
       continue with unreflected Method 3
     } else {
       increase counter for slow path
       if (counter > threshold) {
          install next FAST_PATH in callsite array
          continue with SLOW_PATH_0
       } else {
          continue with SLOW_PATH_0
       }
     }
   }
}

and

class FastPath {
   Class[] receiverAndArguments
   MethodHandle unreflectedMethod
   long age
}

and "install next FAST_PATH" would be then:

sort callsite.fastPaths by age
rotate out oldest from callsite.fastPaths
callsite.fastPaths[0] = new FastPath(..)


Of course there is a lot more to consider... like avoiding that the 
Class-Objects in FastPath are hard referenced forever. There is also the 
switch for category methods to consider and a lot of details. But I 
first want to see if anybody can even follow this ;)

bye Jochen