Strawman for polymorphicInlineCache method handle

[Mark Roos]

During the JVM summit I found myself thinking about polymorphic inline 
caches and whether ti would be possible to describe one
in such way that was implementation and usage independent.  The goal would 
be to give the hotspot folks a chance to uber optimize
this form of method lookup.

Some analysis of my software shows that about 98% of all callsites have 
three receivers or less.  But some have all possible receivers.
Taking a close look at these shows that most of fhe larger callsites are 
not in time dependent paths.  So it seems like a cache that
was really fast for the first few and then fell back to a hash like lookup 
would be a good match to my usage at least.

Currently my GWT does its testing based on an instance variable of the top 
item on the stack.  This is due to Smalltalk pushing arguments
then then the receiver to match the message pattern.  Thinking some it 
seems that the test would generally be the java class of some
argument or like my situation some ivar in one of the arguments.  Of 
course one could envision a multi-methods dispatch that looked
at any or all of the args but I have no experience with that.

I modified the GWT spec to try and show a possibility and see if there is 
any interest from other implementers.  So feel free
to comment.  I plan to do some more profiling to  looks at frequency of 
calls for each depth and to further examine some sites
which are heavily used and have more than three receivers.  I believe that 
these are inside Array methods and so see many
reference types

regards
mark


p.s.  I could implement this from normal java code but would I lose 
performance over the current GWT implementation?


polymorphicCache

public static MethodHandle polymorphicCache(MethodHandle getTestObjectRef,
                         MethodHandle lookup)

Makes a method handle which encloses a polymorphic inline cache. 
getTestObjectRef is invoked with the arguments and returns an object 
reference to be used in searching for a cache hit.
Since most lookups are likely by a field in one of the arguments it may be 
more efficient to reference which argument
and which field to use as the objectReference. Argument would be by index, 
field could be a getter.

lookup is used if no hit and returns the methodHandle to pair with this 
object reference.

When this methodHandle is invoked the arguments are passed to 
getTestObjectRef which returns an object reference. 
This refererence is compared to prior objectReferences searching for a == 
match.  If no match is found then
the lookup method is invoked with the arguments returning a new target 
methodHandle to match with this reference. 
This objectReference methodHandle pair is then held fof future 
comparisons.
If a match occurs then the target is the methodHandle associated with that 
objectReference.

Then the target methodHandle is returned.
 
Here is pseudocode for the a possible adapter  with three fast paths:

        test := getTestObjectRef(args).
        if( entry1 == null){
                MH1 = lookup(args);
                entry1 = test;
                return MH1;}
        if test == entry1{
                return MH1;}
        if( entry2 == null){
                MH2 = lookup(args);
                entry2 = test;
                return MH2;}
        if test == entry2{
                return MH2;}
        if( entry3 == null){
                MH3 = lookup(args);
                entry3 = test;
                return MH3 ;}
        if (test == entry3){
                return MH3};
        if (hashMap == null){
                hashMap = some growable hash map like collection}
        target = hashMap at(test).
        if(target == null)
                target = lookup(args);
                hashMap insert(test, target)}
        return target
 

Note that the getTestObjectRef arguments cannot be modified, and so are 
passed unchanged from the caller to the target or lookup as appropriate.

Parameters:
getTestObjectReference - method handle used to extract the object to test 
from the arguments, must return an object reference
lookup - method handle to call if there is no match in the cache to the 
testObjectReference

Returns:
method handle which holds a polymorphic cache

Throws:
java.lang.NullPointerException - if any argument is null 
java.lang.IllegalArgumentException - if test does not return a reference, 
if the lookup returns a null or if all three method types do not match 
(with the return type of getTestObjectReference  changed to match that of 
the lookup).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/mlvm-dev/attachments/20120802/899d2d98/attachment.html