Performance profiling ways of invoking a method dynamically

For the SciJava Ops project—an iteration and generalization of ImageJ Ops—we have been researching ways to make it as easy as possible for programmers to code algorithm implementations such that they can be discovered and executed performantly at runtime.

One thing that would be very nice would be to let programmers write public static methods, which are easily usable normally, but which also possess key structural metadata, including which op is being implemented (e.g. filter.gauss), and names and types of parameters including generics.

Suppose we have the following utility method:

public final class Util {
	public static double sum(final double a, final double b, final int v) {
		return a + b + v;
	}
}

And the following functional interface:

public interface Function3<T, U, V, R> {
	R apply(T t, U u, V v);
}

We would like to have a Function3<Double, Double, Integer, Double> which, when executed via its apply method, invokes this Util.sum(double, double, int) method. Here are a few different ways to achieve this:

Subclassing

One can implement a class—typically an anonymous inner class—like so:

Function3<Double, Double, Integer, Double> sumFunction = new Function3<Double, Double, Integer, Double>() {
	@Override
	public Double apply(Double a, Double b, Integer v) {
		return Util.sum(a, b, v);
	}
};

Lambda expression

Starting with Java 8, the method can be converted to an implementation of the interface using a lambda expression:

Function3<Double, Double, Integer, Double> sumFunction =
	(a, b, v) -> Util.sum(a, b, v);

Or, using the more succinct double colon syntax:

Function3<Double, Double, Integer, Double> sumFunction = Util::sum;

Thanks to Java’s Just-in-Time (JIT) compiler, invoking the Util.sum method (Util.sum(3, 4, 5)) has very low overhead, often no overhead, compared to inlining the code directly. Similarly, invoking a lambda (sumFunction.apply(3, 4, 5)) also has very low overhead, often negligible.

Reflection API

What if you want to invoke a method dynamically? E.g., let the user type in the name of a method, then look it up and invoke it? Or more ambitiously: discover all the Op plugins dynamically so they can be invoked as appropriate? In older versions of Java, this was accomplished via the reflection (java.lang.reflect) API:

Method m = Util.class.getMethod("sum", double.class, double.class, int.class);
m.invoke(null, 3, 4, 5);

Unfortunately, Java reflection is very slow compared to normal method execution.

Invocation API

In more recent versions of Java, there is a newer invocation API in java.lang.invoke. First, we retrieve a MethodHandle:

MethodType methodType = MethodType.methodType(double.class, double.class, double.class, int.class);
MethodHandle handle = MethodHandles.lookup().findStatic(Util.class, "sum", methodType);

It is also possible to convert a Method object to a MethodHandle by calling:

MethodHandle handle = MethodHandles.lookup().unreflect(m);

The MethodHandle API also has its own invoke method:

handle.invoke(3, 4, 5);

But surprisingly, it is even slower than the reflection API.

Dynamic lambdas

Once we have the MethodHandle, we can convert it to a lambda dynamically:

MethodType function3MethodType = MethodType.methodType(Function3.class);
Function3<Double, Double, Integer, Double> sumFunction = (Function3<Double, Double, Integer, Double>)
	LambdaMetafactory.metafactory(MethodHandles.lookup(), "apply", function3MethodType,
		methodType.generic(), handle, methodType).getTarget().invokeExact();

Rather arcane, but it does the job, creating a lambda that is as performant as one created at compile time.

Dynamic proxy

As an aside, the java.lang.invoke API has another, much less performant way to convert a MethodHandle into an instance of a functional interface:

@SuppressWarnings("unchecked")
final Function3<Double, Double, Integer, Double> sumFunction =
	MethodHandleProxies.asInterfaceInstance(Function3.class, handle);

Nicer to read, but it unfortunately has high overhead to execute—almost as high as the reflection API.

Wrapped lambda

One downside of lambda expressions is that they know which raw interface they implement, but not the interface’s generic parameters, unlike true subclasses.

Here is a demonstration. Consider the output of the following code:

BiFunction<T, Supplier<String>, T> lambdaFunction = Objects::requireNonNull;
System.out.println(lambdaFunction.getClass().getGenericInterfaces()[0]);

class MyFunction implements BiFunction<T, Supplier<String>, T> {
	@Override
	public T apply(T t, Supplier<String> u) {
		return Objects.requireNonNull(t, u);
	}
}
System.out.println(MyFunction.class.getGenericInterfaces()[0]);

The output is:

interface java.util.function.BiFunction
java.util.function.BiFunction<T, java.util.function.Supplier<java.lang.String>, T>

That is: the lambda remembers only that it implements BiFunction (raw), whereas the MyFunction subclass retains generics-related information, because class definitions store this information in the bytecode.

If we want the convenience of lambdas while retaining generics-related information at runtime, one way around this problem is to wrap the lambda object in another object that knows the generics:

public interface GenericTyped {
	Type getType();
}
public class GenericFunction3<T, U, V, R> implements Function3<T, U, V, R>, GenericTyped {

	private Function3<T, U, V, R> f;
	private Type type;

	public GenericFunction3(Function3<T, U, V> f, Type type) {
		this.f = f;
		this.type = type;
	}
	@Override
	public Type getType() {
		return type;
	}
	@Override
	public R apply(T t, U u, V v) {
		return f.apply(t, u, v);
	}
}

And then we can wrap up our lambdas:

GenericFunction3<Double, Double, Integer, Double> wrappedLambda = new GenericFunction3<>(lambda, genericType(methodType));

Where Type genericType(MethodType) is a method for extracting the generic java.lang.reflect.Type from a java.lang.invoke.MethodType (outside the scope of this article).

But this is getting complicated. What are the performance implications of wrapping the lambda in another class like this? Let’s do some benchmarking!

Performance

I benchmarked these different ways of wrapping and invoking methods, averaged over 500 million iterations each:

method total milliseconds
inline code 168-172
direct method invocation 166-168
subclass 269-270
dynamic lambda 269-283-336
lambda 275-288-330
wrapped dynamic lambda 264-1503-1575-1637-1690
wrapped lambda 1568-1613-1674
dynamic proxy 8855-8893
wrapped dynamic proxy 9457-9659
reflection 10975-11877

Note that table above does not include the new invocation API’s MethodHandle.invoke approach—but it is slow (see below).

Conclusions:

  • Lambdas, including dynamically generated lambdas, are about as fast as subclasses. :+1:
  • Wrapping a function to retain its generic type has a huge performance hit. :-1:
  • Both dynamic proxies and the old reflection API are very slow.

However, these results are misleading, because the sum method defined above uses primitive double arguments and a double return value, whereas the wrapped Function implementations must use boxed Double. So for many of these approaches, a lot of boxing and unboxing is going on under the hood.

I was curious about the performance in cases where no boxing, unboxing or new object creation would take place—a more common scenario for Ops implementations. So I reran these benchmarks using another method that avoids the boxing issue:

public static void accumulate(final List<?> l, final String s, final long[] result) {
	result[0] += l.size() + s.length();
}

And corresponding functional interface:

public interface Consumer3<T, U, V> {
	void accept(T t, U u, V v);
}

Here are the results:

method total milliseconds
inline code 259-259-292
wrapped lambda 259-262-265
direct method invocation 259-264-270
lambda 264-268-284
subclass 256-302-336
dynamic lambda ?
wrapped dynamic lambda ?
reflection 1027-1027-1045
invocation 2276-2281-2418
wrapped dynamic proxy 5757-5796-5884
dynamic proxy 5683-6081-6898

Unfortunately, the dynamic lambda values are not included here because I hit a roadblock using the LambdaMetafactory with functional interfaces that return void:

Exception in thread "main" java.lang.invoke.LambdaConversionException: Type mismatch for lambda expected return: void is not convertible to class java.lang.Object
	at java.lang.invoke.AbstractValidatingLambdaMetafactory.validateMetafactoryArgs(AbstractValidatingLambdaMetafactory.java:286)
	at java.lang.invoke.LambdaMetafactory.metafactory(LambdaMetafactory.java:303)

More research needed to overcome that issue.

Conclusions:

  • In this case, there is no significant difference between inline code, direct method calls, and lambdas, even wrapped lambdas. :100:
  • Reflection, invocation and proxies are slow, as expected.

Finally, here is the source code I used for the benchmarks. Caveat emptor: it is messy.

Source code
import java.lang.invoke.LambdaMetafactory;
import java.lang.invoke.MethodHandle;
import java.lang.invoke.MethodHandleProxies;
import java.lang.invoke.MethodHandles;
import java.lang.invoke.MethodType;
import java.lang.reflect.Method;
import java.lang.reflect.Type;
import java.util.Arrays;
import java.util.List;

public class FastMethodInvocation {

	public static void accumulate(final List<?> l, final String s, final long[] result) {
		result[0] += l.size() + s.length();
	}

	public interface Consumer3<T, U, V> {
		void accept(T t, U u, V v);
	}
	public interface GenericTyped {
		Type getType();
	}
	public static class GenericConsumer3<T, U, V> implements Consumer3<T, U, V>, GenericTyped {

		private Consumer3<T, U, V> c;
		private Type type;

		public GenericConsumer3(Consumer3<T, U, V> c, Type type) {
			this.c = c;
			this.type = type;
		}
		@Override
		public Type getType() {
			return type;
		}

		@Override
		public void accept(T t, U u, V v) {
			c.accept(t, u, v);
		}
	}

	public static void main(final String... args) throws Throwable {
		// Simple lambda.
		Consumer3<List<?>, String, long[]> lambda = FastMethodInvocation::accumulate;
		
		// Old-school reflection.
		Method m = FastMethodInvocation.class.getMethod("accumulate", List.class, String.class, long[].class);

		// Get the MethodHandle for accumulate method.
		MethodType methodType = MethodType.methodType(void.class, List.class, String.class, long[].class);
		MethodHandles.Lookup lookup = MethodHandles.lookup();
		MethodHandle handle = lookup.findStatic(FastMethodInvocation.class, "accumulate", methodType);

		// OR:
//		handle = lookup.unreflect(m);

		// First method of converting MethodHandle to Consumer3.
		MethodType consumer3MethodType = MethodType.methodType(Consumer3.class);
		Consumer3<List<?>, String, long[]> dynamicLambda =
			(Consumer3<List<?>, String, long[]>) //
			LambdaMetafactory.metafactory(lookup, "accept", //
				consumer3MethodType, methodType.generic(), handle,
				methodType).getTarget().invokeExact();

		// Second method of converting MethodHandle to Consumer3.
		@SuppressWarnings("unchecked")
		final Consumer3<List<?>, String, long[]> dynamicProxy = //
			MethodHandleProxies.asInterfaceInstance(Consumer3.class, handle);

		GenericConsumer3<List<?>, String, long[]> wrappedLambda = new GenericConsumer3<>(lambda, null);
		GenericConsumer3<List<?>, String, long[]> wrappedDynamicLambda = new GenericConsumer3<>(dynamicLambda, null);
		GenericConsumer3<List<?>, String, long[]> wrappedDynamicProxy = new GenericConsumer3<>(dynamicProxy, null);

		System.out.println(Arrays.toString(dynamicLambda.getClass().getGenericInterfaces()));
		System.out.println(Arrays.toString(dynamicProxy.getClass().getGenericInterfaces()));

		Consumer3<List<?>, String, long[]> inner =
			new Consumer3<List<?>, String, long[]>()
			{
				@Override
				public void accept(final List<?> l, final String s, final long[] result) {
					FastMethodInvocation.accumulate(l, s, result);
				}
			};

		// NB: Naive attempt to avoid inlining of constant values.
		final List<?> l = Arrays.asList(1, 2, 3, 4, 5, System.currentTimeMillis());
		final String s = "Hello " + System.currentTimeMillis();
		final long[] result = {0};

		final long iters = 500_000_000;
		final long start = System.currentTimeMillis();
		for (int i=0; i<iters; i++) {
//			result[0] += l.size() + s.length();
//			accumulate(l, s, result);
//			inner.accept(l, s, result);
//			lambda.accept(l, s, result);
//			wrappedDynamicLambda.accept(l, s, result);
//			wrappedLambda.accept(l, s, result);
			dynamicLambda.accept(l, s, result);
//			m.invoke(null, l, s, result);
//			handle.invoke(l, s, result);
//			dynamicProxy.accept(l, s, result);
//			wrappedDynamicProxy.accept(l, s, result);
		}
		final long end = System.currentTimeMillis();
		System.out.println(end - start);
	}
}

CC @gselzer @MarcelWiedenmann @tpietzsch

6 Likes

This seems to be a problem with the way you are generating the argument samMethodType in the call to LambdaMetafactory.metafactory().

Currently it is the result of methodType.generic(), which erases all parameters (including the output void) to Object. It is error-free (at least in this scenario) to change the methodType.generic() to MethodType.methodType(void.class, methodType.generic().parameterList()), thus preventing the output void from being erased to Object.

As such the Consumer3 dynamicLambda is generated as:

Consumer3<List<?>, String, long[]> dynamicLambda =
	(Consumer3<List<?>, String, long[]>) //
	LambdaMetafactory.metafactory(lookup, "accept", //
		consumer3MethodType, MethodType.methodType(void.class, methodType
			.generic().parameterList()), handle, methodType).getTarget()
		.invokeExact();

Using this I got the following times (just including inline for reference):

method total milliseconds
inline 280-279-281
dynamic lambda 283-280-282
wrapped dynamic lambda 306-282-281
2 Likes