Lambda and JSR 292 method handle

[Rémi Forax]

I've seen lot of comments about relation between JSR 292 method handle 
and lambdas,
and I think it's time to make some clarifications.

In my opinion, there is two runtime models to implement lambda in Java :
The former is the 'class model', function types are interfaces and
lambdas are classes.
The later is the 'function model', function types are translated to one 
class
java.dyn.MethodHandle and lambdas are instance of that class.
A method handle is a decorated safe function pointer that is why you 
don't need
different subtypes to represent all lambdas.

The class model creates one class by lambda and one interface by 
function type.
To reduce the number of generated interfaces and ease subtyping between 
function types,
BGGA proposes to use generics and wildcard.

This model are severals weak points:
1) VMs are built to manage lot of instance of few classes, this model 
creates lot of classes
     with few instances. So this model doesn't fit very well with 
current VM implementations.
     You can already observe this effect in JRuby, current 
implementation creates
     lot of small class that acts as lambda and thus requires by example 
a big perm gen [1]


2) method that takes a function type (here an interface) creates 
megamorphic call sites
    and the VM is not able to inline it if the method is called by 
different method
    (see [3] and [4]).

    foreach(Collection<? extends T> c, #void(T) fun) {
      for(T t:c)
        fun(t);    // megamorphic !
    }


3) Who is in charge of creating interfaces representing function types ?
    Currently the BGGA compiler creates these interfaces when needed at 
compile time.
    This solution is not feasible if you have jars or modules,
    it generates double definitions and conflicts.
    I haven't seen any serious proposal to resolve that problem.


4) because function types are generic types, this model has the 
limitation of generics,
    no reification (cast unsafe, instanceof illegal, etc)


The function model creates one function by lambda.

class A {
   public static void main(String[] args) {
     #int(int) f = #(int x) (x+x);
     f(2);
   }
}

is translated to:

class A {
   public static void main(String[] args) {
     ldc static lambda$1(int)int               // (1)
     astore 1                                  // (2)
     aload 1
     aconst_2
     invokevirtual A.invokeLambda(int)int            // (3)
     pop
   }

   private static int lambda$1(int x) {
     return x+x;
   }
}

I've written the body of the main in bytecode because there is non 
equivalent in Java.
First, the JSR 292 define a new constant pool constant (see [2])
that allow to reference a function (here a static method) using opcode ldc.
So instantiating a lambda is just a ldc (1).
At runtime, this object is a java.dyn.MethodHandle, so it can be stored 
as an object (2).
To call the lambda, the VM allows to call a magic method (3) named 
invokeLambda (name may changed).
At runtime, the VM checks that the method handle type is compatible with 
the type of invokeLambda
and call the function pointer stored in the method handle.

Because a method handle knows its runtime type, it's possible to 
implement instanceof and
cast on a function type.
Function type that are parametrized have the same constraint that 
parameterized type, i.e
cast are unsafe.

If function type are translated to method handle, megamorphic call site 
problem can be solved because
JIT can recognize the pattern (a method that takes a method handle) and 
do an aggressive inlining of
such method.


In summary, JSR 292 method handles was introduced by JSR 292 expert 
group because it solves
common problems encounters when dealing with function pointer encoded 
using interfaces.
It will be stupid to don't eating our own dog food.

Rémi


[1] 
http://java.net/blog/eileeny/archive/2009/12/10/jruby-performance-glassfish-v3-part-1
[2] http://wiki.jvmlangsummit.com/DinnerAtPiatti (look for Constant Pool 
Constants)
[3] http://thread.gmane.org/gmane.comp.lang.scala.internals/865
[4] 
http://blog.juma.me.uk/2009/10/26/new-jvm-options-and-scala-iteration-performance/