Skip to main content

Fixing The Inlining “Problem” - A prototype

Posted by forax on April 8, 2011 at 3:48 PM PDT

Today, I've found the time to code a prototype of the solution proposed by Cliff Click
for Fixing the inlining problem,
i.e. to solve the problem of the inability of the Hotspot JITs to inline lambda calls.

In the example below, I want to filter a list depending on a predicate which is specified
as a method handle (read a function pointer if you don't know the new java.lang.invoke API
that will be introduced in Java 7).

  private static List<String> filter(List<String> list, MethodHandle predicate) throws Throwable {
    ArrayList<String> filteredList = new ArrayList<String>();
    for(String element: list) {
      if ((boolean)predicate.invokeExact(element)) {
        filteredList.add(element);
      }
    }
    return filteredList;
  }

The problem is that apart if the method filter is always used with the same lambda,
the call predicate.invokeExact() will never be inlined because Hotspot doesn't trace calls
between several methods.


Cliff proposal is that the JIT should emit several specialized versions of filter; one by lambda;
with a dispatch table at the top of the method that will select the specialized code
depending on the lambda taken as parameter.

So I've created a Java Agent that detects this kind of method, installs a ConcurentHashMap as dispatch table
on top of the method and specializes the code if a new lambda is found.
The method handle invocations in the specialized code are transformed to plain old calls
that are later inlined by the JIT.

Detection: the agent looks for methods that use method handles as parameter, after it run a simple
control-flow analysis (thanks to ASM analysis framework) to crawle among the variable aliases
to find if the method handles are invoked.


Specialization: when a new lambda is discovered, the agent duplicate the bytecode of the function
and replace each method handle calls find by the control flow analysis run previously
to the corresponding direct/virtual call.

Now a small benchmark, with a list of 1 000 000 strings, with a stock 1.7 VM (b136) and
with the same VM plus the Java agent. The full source are available at the bottom of this entry.

  java -XX:+UnlockExperimentalVMOptions -XX:+EnableInvokeDynamic Speed
  elapsed 2260394574 ns

  java -XX:+UnlockExperimentalVMOptions -XX:+EnableInvokeDynamic -javaagent:lib/jsr335-lambda-optimizer.jar Speed
  elapsed 1244597693 ns

Ok, it's a micro benchmark but I think it clearly indicates that can be a really useful optimization.

cheers,

Rémi

* No, I have not modified the JIT itself, call me lazy if you want but I tend to avoid to touch a line of C++ if possible :)

AttachmentSize
lambda-optimizer.zip694.93 KB
Related Topics >>

Comments

<p>The result is somehow expected, isn't it? ;)</p> <p>Your ...

The result is somehow expected, isn't it? ;)
Your solution is a bit like "C++ templates on a usage base". Didn't read your source yet, but i suppose you've implemented a memory leak (imagine many, ok, really many, different function pointers getting in).
But a nice finger exercise.

<p>&gt; The result is somehow expected, isn't it? ...

> The result is somehow expected, isn't it? ;)

Until VMs implements something like that, yes.

> Your solution is a bit like "C++ templates on a usage base". Didn't read your source yet, but i suppose you've implemented a memory leak (imagine many, ok, really many, different function pointers getting in).

Yes, there is a big leak, the dispatch table is a concurrent hashmap with no eviction policy at all.

Let say this is left as an exercise for the reader :)

> But a nice finger exercise.

Thank you !

Rémi