Memoization with invokedynamic

Fibonacci.java

/*
 * Copyright (C) 2013 Julien Ponge
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
 * the Software, and to permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

package lazy;

public class Fibonacci {

  public static long compute(long n) {
    if (n < 2) {
      return n;
    } else {
      return compute(n - 1) + compute(n - 2);
    }
  }
}

LazyRuntime.java

/*
 * Copyright (C) 2013 Julien Ponge
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
 * the Software, and to permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

package lazy;

import java.lang.invoke.*;

public class LazyRuntime {

  private static final MethodHandle BOOT;

  static {
    MethodHandles.Lookup lookup = MethodHandles.lookup();
    try {
      BOOT = lookup.findStatic(LazyRuntime.class, "boot", MethodType.methodType(Object.class, MutableCallSite.class, MethodHandle.class, Object[].class));
    } catch (Throwable t) {
      throw new Error(t);
    }
  }

  public static CallSite bootstrap(MethodHandles.Lookup lookup, String name, MethodType type) throws Throwable {
    String[] split = name.split(":");
    Class<?> targetClass = Class.forName(split[0].replace("#", "."));
    String targetName = split[1];
    MethodHandle target = lookup.findStatic(targetClass, targetName, type);
    MutableCallSite callSite = new MutableCallSite(type);
    MethodHandle boot = MethodHandles.insertArguments(BOOT, 0, callSite, target)
        .asCollector(Object[].class, type.parameterCount())
        .asType(type);
    callSite.setTarget(boot);
    return callSite;
  }

  public static Object boot(MutableCallSite callSite, MethodHandle target, Object[] arguments) throws Throwable {
    Object evaluation = target.invokeWithArguments(arguments);
    MethodHandle constant = MethodHandles.dropArguments(
        MethodHandles.constant(callSite.type().returnType(), evaluation),
        0,
        callSite.type().parameterArray());
    callSite.setTarget(constant);
    return evaluation;
  }
}

Runner.java

/*
 * Copyright (C) 2013 Julien Ponge
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
 * the Software, and to permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

package lazy;

import java.lang.invoke.CallSite;
import java.lang.invoke.MethodHandle;
import java.lang.invoke.MethodHandles;
import java.lang.invoke.MethodType;

public class Runner {

  public static void main(String... args) throws Throwable {
    CallSite callSite = LazyRuntime.bootstrap(
        MethodHandles.publicLookup(),
        "lazy#Fibonacci:compute",
        MethodType.methodType(long.class, long.class));

    MethodHandle handle = callSite.dynamicInvoker();
    long start = 0L;
    for (int i = 0; i < 10; i++) {
      start = System.currentTimeMillis();
      System.out.println(handle.invoke(42L));
      System.out.println("   " + (System.currentTimeMillis() - start) + "ms");
    }
  }
}

Informal performance report:

$ java -cp out/production/lazy-indy lazy.Runner
267914296
   2740ms
267914296
   1ms
267914296
   0ms
267914296
   0ms
267914296
   0ms
267914296
   0ms
267914296
   1ms
267914296
   0ms
267914296
   0ms
267914296
   0ms
$

Not bad! 🍻