forax's Blog

JSR 292 Goodness: Almost static final field.

Sometimes I want a express that a static field is unlikely to change, so the VM should consider it has a constant, but it may changed. And because we all live in a threaded world, if the static field is changed I want that all threads that want to read the field value to notice that the value has changed like a volatile field. Take by example the default Locale that you can obtain using Locale.getDefault(), it's unlikely that this value will change, but it may change, there is a Locale.setDefault().

The idea is that default Locale is mostly a constant, so when a code that call getDefault is JITed, the VM should consider it as a constant i.e. the JIT should replace the call to getDefault() by a direct reference to default Locale object. And if a code calls setDefault(), the VM should drop the JITed code and re-optimize it later.

Suppose that you have a magic class named AlmostFinalValue, a value wrapped in this class acts as a constant for the VM, so a code that call getDefault will be replaced by a constant by the VM. And if setValue() is called, the VM will deoptimize the code that use getDefault if the code was JITed and change the value of the default locale. If the code still use getDefault, it will be re-optimized by with the new constant.
Note that this deopt/reopt takes time so it's not a good idea to use an AlmostFinalValue for storing a value which changes frequently.

public class Locale {
  ...
  private static final AlmostFinalValue<Locale> DEFAULT_LOCALE =
      new AlmostFinalValue<Locale>() {
        @Override
        protected Locale initialValue() {
          return new Locale("default");
        }
      };
  private static final MethodHandle DEFAULT_LOCALE_GETTER =
      DEFAULT_LOCALE.createGetter();
  
  public static Locale getDefault() {
    try {
      return (Locale)(Object)DEFAULT_LOCALE_GETTER.invokeExact();
    } catch (Throwable e) {
      throw new AssertionError(e.getMessage(), e);
    }
  }
  
  public static void setDefault(Locale locale) {
    DEFAULT_LOCALE.setValue(locale);
  }
}

How AlmostFinalValue works ?

All modern VMs, V8-cranksaft (Javascript/Google), IonMonkey (Javascript/Mozilla), Hostspot (Java/Oracle), J9 (Java/IBM) are able to de-optimize a JITed code if an optimistic assumption doesn't hold anymore.
In Java, we go a little bit further, JSR 292, foolishly you may say, gives access to VM optimization/deoptimization to the mass* by providing a silver bullet named the SwitchPoint.

A SwitchPoint can be seen as a volatile boolean which is true by default and that can be switched off once. On a SwitchPoint, you can create a guard, an 'if' statement seen as a method handle** that takes two method handles as parameter and execute the former if the boolean is true or the later otherwise. The JIT optimizes a SwitchPoint by considering that the boolean value is unlinkely to change so it will remove the guard to always call the first method handle and if the SwitchPoint is switch off, the VM will deoptimize the JITed code. In fact, in Hotspot, this is done lazily the code is just marked as must be dropped when it will be called. So later, when code will be called again, the VM will call the second method handle. The second method is the slow path, the path which is infrequenly called when there is an update, it get the new value, see it as a constant method handle and protect it with a new SwitchPoint. Then this new method handle is installed as the new target of a mutable method handle (a MutableCallSite + a dynamic invoker in fact). So the new constant is installed and will be called when the DEFAULT_LOCAL_GETTER will be called. The method hande DEFAULT_LOCAL_GETTER is called using invokeExact which calls the method handle with no runtime conversion. As a game, I will offer a free beer at FOSDEM or Devoxx France to the first that will explain why you need the two casts in front of invokeExact ***.

The full code is here, and works well with latest jdk8 and jdk7u2. With jdk7, the SwitchPoint was not fully optimized so the VM will fail to transform the default local value to a constant.

* In fact, JSR 292 was intended to be used by developers of dynamic language runtime (Jython, JRuby, Groovy, etc) but when you provide a golden hammer, everybody will want to use it.
** A MethodHandle is runtime typed function pointers.
*** People that have written the JSR 292 spec can't participate, sorry John, Dan and Fredrik :)

Hotspot loves PHP.reboot

I've just compiled the hotspot (server 64bits) using the hotspot-comp workspace of hotspot express
  http://hg.openjdk.java.net/hsx/hotspot-comp/hotspot/

Here are the result (average of 8 best run on 10) when running PHP.reboot (my own toy language) on fibonacci function,
(-server is the server VM of jdk7, -hsx is server VM of upcoming jdk7 update)

Java:
java -server bigfibo        4.45 s
java -hsx bigfibo           4.44 s

PHP.reboot (no type annotation)
phpr.sh -server bigfibo    22.72 s
phpr.sh -hsx bigfibo       13.61 s

PHP.reboot (type specialization)
phpr.sh -server bigfibo    11.09 s
phpr.sh -hsx bigfibo        8.06 s

PHP.reboot (user defined type annotation)
phpr.sh -server bigfibo2    6.96 s
phpr.sh -hsx bigfibo2       4.21 s

PHP.reboot is an hybrid runtime, it starts with an interpreter that walks the AST (really slow) and then compile to bytecode.

The first test is with no type information provided by the user, so all variables are objects and invokedynamic is used for the operations, the comparison and for function calls. As you see, there is a huge speedup.

The second test enables a flag that ask the runtime to try to specialize the function at runtime. Because the algorithm used is a fast-forward typechecker, the parameter of fibo is san pecialized as int but the return type is still an object (because fibo is recursive). So basically here, invokedynamic is used for the function calls and the '+' between the results of the function calls. This '+' is a nasty one because the two parameters are objects, so it requires a double guards. You can see the speedup is nice too.

The third test uses a function fibo that declares the parameter type and return type of fibo as int, so only the function calls are done using invokedynamic. You can also see the speedup and weirdly it's now faster than Java (not a lot if you compare the value but don't forget that PHP.reboot starts in interpreter mode) so it's clearly faster. I will take a look to the inlining tree to try to understand why, it's maybe because fibo is a recursive call or because using an invokedynamic which is resolved as an invokestatic enables more inlining than just an invokestatic.

John, Christian, Tom and all the others of the hotspot-comp team,
you make my day

cheers,
Rémi

Fixing The Inlining “Problem” - A prototype

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 :)

JSR 292 Goodness: Fast code coverage tool in less than 10k

JSR 292 introduces a new bytecode instruction invokedynamic but also several new kind of constant pool constants. Which means that most of the tools that parse bytecodes like ASM, BCEL, findbugs or EMMA will need to be updated to be java 7 compatible.
EMMA is a code coverage tool, a tool that helps developers to know if their tests cover all the code of the application. While it's not the only code coverage tool available in Java, it's the most popular from my personal experience.
In this blog entry, I would like to show how to write a simple code coverage tool indycov that use JSR 292 API to have a runtime overhead close to zero.

How a code coverage tool works ?

A code coverage tool records all paths taken when running the application and checks at the end if all lines of codes was recorded.
By example, if I run the code below with no argument, it will print "foo" and "bar" and the code coverage tool will say that the else branch that prints "baz" will be not covered.

public static void main(String[] args) {
    System.out.println("foo");
    if (args.length == 0) {
      System.out.println("bar");
    } else {
      System.out.println("baz");
    }
  }

To record if an instruction was executed or not, code coverage tools add a probe which is a small amount of bytecodes that will call the runtime of the tool to say: "I have visited this instruction".
In fact, tools, only add probes where necessary, at the begining of each basic block of the control flow. A basic block is a collection of instructions without any jump (return, thow, if, break etc).
By example, the code above has 4 basic blocks: the once printing "foo", the one printing "bar", the one printing "baz" and the one containing the return at the end of the method.

So a code coverge tool is a tool that find basic blocks and add probes at the begining of each one.

Using JSR 292 API to implement a code coverage tool.

Finding basic block is easy with bytecode that come from 1.6 or 1.7 compiler because the compiler is required to add stack maps
in the bytecode flow. Stack maps are used to verify the bytecode in linear time and are inserted at the join points of the control flow.
So finding basic block in a 1.7 compatible bytecode can be done in one pass thanks to the stack maps info inserted by the compiler.

All existing code coverage tools have an impact on the performance of the application because the code of the probe is executed each time you call a basic block even if it should be executed once.
If you are a regular reader of this blog, you already know how to create a probe that will be executed once. The trick is use use invokedynamic, to record the visit in the bootstrap method and
to use a target method handle that is equivalent to no-op. So subsequent call will not execute any code.

main([Ljava/lang/String;)V
    INVOKEDYNAMIC probe ()V [fr/umlv/indycov/RT#bsm, 1]
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    LDC "foo"
    INVOKEVIRTUAL java/io/PrintStream.println (Ljava/lang/String;)V
    ALOAD 0
    ARRAYLENGTH
    IFNE L0
    INVOKEDYNAMIC probe ()V [fr/umlv/indycov/RT#bsm, 2]
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    LDC "bar"
    INVOKEVIRTUAL java/io/PrintStream.println (Ljava/lang/String;)V
    GOTO L1
    L0
    FRAME SAME
    INVOKEDYNAMIC probe ()V [fr/umlv/indycov/RT#bsm, 3]
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    LDC "baz"
    INVOKEVIRTUAL java/io/PrintStream.println (Ljava/lang/String;)V
    L1
    FRAME SAME
    INVOKEDYNAMIC probe ()V [fr/umlv/indycov/RT#bsm, 4]
    RETURN

A no-op, is a method handle that takes nothing and return void. This method handle can be retrieved with Methodhandles.identity(void.class).
So the bootstrap method is the following. The first line records that the basic block with number 'index' is visited.

  public static CallSite bsm(Lookup lookup, String name, MethodType type, Object index) {
    classValue.get(lookup.lookupClass()).cover((Integer)index);
    return new ConstantCallSite(MethodHandles.identity(void.class));
  }

The code of the prototype is freely available (as attachment of this blog)  and works like an agent.
It relies on ASM 4 (still in beta) to do the bytecode transformation.

Side note: This prototype doesn't handle runtime exception correctly. By example, if a NPE is thrown, it will escape from the basic block without ending it.
How to modify the prototype to take care of exception is let to interrested readers.

Running the code with one argument "foo"

  java -XX:+UnlockExperimentalVMOptions -XX:+EnableInvokeDynamic -javaagent:lib/indycov.jar -cp test-classes/ TestCoverage foo

will print

  foo
  baz
  TestCoverage: no coverage for line(s) 2 to 2
  TestCoverage: no coverage for line(s) 5 to 6

line 2 is the declaration of the class, it's because javac adds a default constructor which is not used.
lines 5 to 6 are the ones that print "bar".

If you want to play with it don't forget to compile your sources with the debug flag on. Otherwise, the generated bytecodes will not contain mapping information between opcodes and line numbers.

Cheers,
Rémi