Procedure Types and Managed Execution (part 2)

Summary

This is part two of a short series on the implementation of procedure types and variables on top of the .NET framework, or the Java Virtual Machine.  In this part I consider alternative mechanisms for implementing procedure types on each platform.

The .NET Framework

On the .NET framework the delegate type appears to be the obvious choice.  After all, the construct was designed for exactly this job, and as the basis of the .NET event-handling model.  However, there is nothing to stop us from using a single-member base class or interface, just as we are (or rather were) forced to do on the JVM.  Which is better? 

The question of which mechanism is better is not one that may be answered on the basis of inclination or traditional prejudice.  What we need is some evidence, and to be sure evidence from a range of different usage patterns.  However, let us start with the simple case of simple procedure (static method) with a simple signature.

Here are three ways of calling the static method Hello, using three different mechanisms for representing procedure values. At line 23 we declare the StringToVoid delegate type, and at line 14 we create a instance of the delegate type that wraps the method Hello.

At line 26 an interface is declared with a single member "Invoke" of the string to void signature.  This interface is implemented by the IWrapHello class, that wraps the Hello method.  Essentially the same semantics are achieved by the abstract class S2V and its subclass WrapHello at line 31. The three "function values" are created at lines 14 .. 16, and are each called, in turn, in the following three lines.

So, a compiler could use any of these three mechanisms to represent types and values for static methods.  The amount of generated IL would be very similar each case, and the details of the naming of the wrapper types would be hidden in the implementation.  But what are the comparative overheads of these three mechanisms?

.NET timing for various procedure variable implementations (see text).

Four different ways of implementing procedure variables were tried, with two different micro benchmarks. The first test was very simple: the static method that was encapsulated in the variable took a string argument and returned its length.  This variable was called in a loop which repeated about 10^6 times.  Some idea was to make the body of the wrapped method so simple that small differences in the calling machinery would still be significant.  The results are shown in the left column of the table.

The results seem to indicate that the .NET delegate mechanism has a small time advantage over both the concrete sub-class overriding an abstract method in a single-member class, or a class implementing the single member of an interface.  The other thing to note is the overhead of reflective invocation.  About two orders of magnitude, for a simple method body.

Of course, with one must be a little careful with a JIT compiler, as it may do special magic on loops that repeat many, many times.  The second example is designed to be slightly more realistic. The code uses a rather unusual coding pattern for implementing a finite state automaton (FSA). The state variable is a procedure variable holding the "nextstate" function. The function is fed the next symbol, in this case a single bit and returns the nextstate function corresponding to the next state of the FSA.  The whole thing is attached to a pseudo-random binary sequence generator which repeats every (2^19 -1) steps.  The details of generators of this kind are given at Wikipedia Linear_feedback_shift_register. In this case a Galois implementation was used.   This generator produces a string of 18 zero bits only once every cycle, which is what the FSA searches for.  The state is updated at every step, in an apparently random fashion, in an attempt to defeat any clever prediction strategy of the JIT.  The results are shown in the right hand column of the table.  It may be seen that our three favored strategies have very comparable results.

The final column of the table, just for the record, lists the compatibility semantics of the procedure variable containers.  All three of our favored mechanisms enforce name-compatibility, which is not what we really want.  What we want is compatibility based on equality of Signatures of the encapsulated method. Reflective invocation of the MethodInfo value has the right semantics, but the loss of efficiency is overwhelming.

The JVM Framework

The MethodHandle Class, and JSR292

Meanwhile, in the Java world, Java SE Version-7 introduced a number of changes designed to benefit all those dynamically typed languages that have been implemented to run on top of the JVM.  The process of proposing and implementing the changes took several years, and anyone interested in the process should Google "JSR292" to see the history.

In essence, the JSR 292 changes introduced one new byte code instruction, invokedynamic, and a few new classes in the library.  MethodHandle and MethodType are the two new classes of interest here, and both belong to the package java.lang.invoke.  

I shall say nothing this time about invokedynamic, although it is an interesting topic for another day.  Despite the impetus for the new instruction having come from the dynamically-typed language community, it turns out to be an ideal method for the implementation of the Lambda Abstractions that will launch with Java SE Version-8.  However the two new classes are directly relevant to this discussion.

MethodType is a descriptor for a method signature. The object factory for the class is passed arguments with the Class objects for the return type and the parameter types.  MethodHandle is wrapper for a method value.  Objects of the type may be created by a factory method that is passed a Class object, the name of a method within that class, and a MethodType object.  The returned handle encapsulates the matching method.  If the MethodInfo object of the target method is known, presumably by reflection, then the corresponding method handle is created by a call to the amusingly named "java.lang.invoke.unreflect".

Here are the corresponding results of the two test programs.

JVM timing for various procedure variable implementations (see text).

All of these measurements, for both frameworks, were performed on a four year old Intel E8400 processor running Windows-7 (32-bit).   You may note that the MethodHandle mechanism has low overheads, with similar per-call overhead to the previous implementation methods once the method bodies do any computation.  The rather lower overhead of reflective invocation of a java.lang.Class.method compared to that for a System.Reflection.MethodInfo is an interesting piece of trivia to store away in a spare neuron.

The Anonymous interface method row of the table is interesting, as this performs well on the example using the nextstate-function pattern.  The gain here is that there is one less method call in the chain.  In effect, the anonymous method "inlines" the body of the next-state function rather than calling the next-state function.

A simple table-lookup implementation of the FSA is included here, as a reality check.

So here is a tentative conclusion:  The MethodHandle mechanism has comparable overhead to the other implementations of procedure variables.  And, as a bonus, it has the sensible structural-compatibility semantics that we would expect procedure types to display.

About the Next Episode

In the final episode of this series I shall look a bit closer at the case of method values that encapsulate both a method, and a receiver ("this" value) to invoke the method on.  I shall also look at using lambda abstractions to realize similar coding patterns to the use of procedure/method variables.

Late-Breaking News

My MethodHandle-based FSA benchmark crashes the Hotspot(r) Compiler for Windows X64. It runs fine on the 32-bit X86 Hotspot compiler.   On X64 it runs fine with java -Xint, or if the run is too short for Hotspot to attempt heroic optimizations.  Watch this space for further developments.

Procedure Types and Managed Execution

Summary

This is the first part of a multi-post exploration of the ways in which procedure variables, function pointers (call them what you will) are implemented in managed execution systems such as .NET and the JVM.  Particular implementation details for both .NET and the JVM type systems place limitations on the implementation of this functionality.

This first post briefly reviews the idea behind procedure types, and the implementation mechanisms on the .NET and JVM platforms.

The second part looks at various ways to get the same semantics on the (pre-version 7) Java Virtual Machine.  This second part also discusses the limitations of both managed execution systems in implementing procedure types.

A final part will look specifically at how the new functionality in JDK v7 changes the landscape, removing one of the limitations.  This final part will also look at implementations based on use of lambda abstractions - available on the .NET platform currently, and coming soon in version-8 of the Java.

Background

Many programming languages have a construct that allows a variable to be declared as containing a value that denotes a particular procedure value.  The procedure denoted by the variable may be invoked by calling the procedure value.   Such procedure values may be created, by associating the new value with some named procedure, and values may be copied and assigned using the conventional syntax of the particular language.

Compilers implement these constructs, in the simplest case, by making the procedure value be of pointer size, and using the entry-point-address of the bound procedure as the value.  This implementation mechanism is explicit in ANSI C, where such values are called "function pointers". Languages that permit nested procedures to be used as procedure values are a little more complicated, since the called procedure needs to be given access to the stack frames of its enclosing procedures.  However, that circumstance is mainly of historical and theoretical interest nowadays.

Typical machine architectures have two distinct subroutine call instructions, call and calli, which respectively call a method by its symbolic name, and indirectly call the method that the entry point address of which has been loaded into some chosen register.

The calling sequence for a regular call goes something like this -

• load up the arguments to the call
• call the named procedure

or in the indirect, procedure variable case -

• load up the arguments to the call
• load the procedure variable value into the chosen register
• calli through the chosen register

Of course, for a statically typed language, the number and type of the the arguments must in each case match the formal parameters of the procedure ends up being invoked by the call.

Procedure variables are thus strongly typed, and programming languages that provide procedure variables may allow such procedure types to be named in the usual way.  In Component Pascal, the syntax looks like this -
  TYPE NoArgToInt = PROCEDURE( ) : INTEGER;
Which gives a name to a type of procedures that take no arguments, but return an integer.  We may now declare variables of this type -
  VAR p1, p2 : NoArgToInt;
which declares two variables of the named procedure type.  We could just have easily left the procedure type unnamed, and declared the variables as being of some anonymous procedure type -
  VAR p1, p2 : PROCEDURE( ) : INTEGER;
with the same effect.

When the compiler emits instructions to construct a new procedure value it will check that any named procedure that is being bound to a new value has the correct argument number and type and conforming return type.

Now, a little thought will convince the reader that although it may be convenient to have a name for a procedure type, but two procedure types should b e compatible provided that they have the same call signature.  Thus such languages have type compatibility rules for procedure values that implement structural compatibility, that is "two procedure types are the same type if they have the same argument number and type, and the same return value (or lack of return value)".

This observation, regarding structural compatibility, does not even arise in ANSI C.  Function pointer types are denoted by an "abstract declarator" that declares only the parameter types and the return type.  The abstract declarator for our NoArgToInt type would be -

int (*)( )

that is "pointer to function taking no arguments and returning int.

Implementing Procedure Types on .NET

Implementing procedure types on .NET is fairly straightforward.  The built-in delegate type of the framework is almost exactly what we need. Consider the following C#  progam fragment -

At line 20 a new delegate type is defined, with the "no args, returns int" signature. At line 23 a static method Foo is defined, with a compatible signature. A new instance of the delegate type is defined at line 26, taking Foo as its bound method value.  The method is invoked via the delegate value at line 27.

There are a couples of wrinkles about .NET delegates that I am ignoring for the moment.  Delegates may be bound to either a static method, as in this example, or bound to an instance method.  In the case of an instance method the "this" reference is supplied at delegate creation time.  A delegate may thus be thought of as encapsulating two data:  a pointer to the method entry point, and a copy of the receiver to which the method is to be applied.

Not exactly what we wanted

The only real defect of the .NET delegate, as a feature to implement procedure values, is the lack of structural compatibility.  Suppose an application depends on two existing libraries, both of which have API calls with parameters of delegate types, and use different names for (say) the NoArgToInt signature. Now the names of the delegate types are baked into the APIs, and although our method Foo is compatible with each, the delegate values are not assignment compatible.  This is extremely annoying, since it is clear that the same semantic analysis inside the compiler that decides that Foo is compatible with each of the two delegate types can also decide that values of the two types are compatible with each other.  (There was a proposal to move to structural compatibility for delegate types in V2 of the framework, but it didn't make it into the release.)

The .NET version of GPCP essentially produces the same machine code for Procedure Types as a C# compiler would for the equivalent delegate-based program.  The semantics are not exactly as described in the language report, because of the lack of structural compatability of values.

Implementing Procedure Types on the (pre-V7) JVM

On the JVM the starting point is even further back, as the JVM has nothing equivalent to a built-in delegate type.  Since the platform does not give us the primitive construct that we need, we must build it ourselves.  Here is the Java program that we need to construct to get semantics equivalent to the C# example above.

Each procedure type corresponds to an abstract base class, defining a single abstract method Invoke, with the signature that we wish to encapsulate.  Every value of this type has a separate derived class that implements the abstract method by calling the target method, in this case Foo.  This is in essence the translation formula that GPCP-JVM uses to implement procedure types and values.

 It may seem that if a program has many, many different procedure value instances that the namespace is going to become cluttered with lots of "single use" sub-classes, and that an anonymous class would be nicer.  This is true of course, but the namespace is still cluttered, it is just that the clutter is with names that the compiler chose for you.  And, yes, the names will be names that would be illegal in your Java program, so that these names will not clash with anything that the programmer might have named herself.

It would also be possible to define an interface base type, rather than an abstract type to hold procedure values, with similar results.

Notice that the Java mechanism has the same problem with compatibility of types as the .NET framework. Two variables are assignment compatible if they are derived from the same abstract base type.

Preview of part II.

In part two of this series, I shall look at alternative mechanisms for implementing procedure types.  In particular there are interface base types (rather than an abstract base class), there is the use of runtime reflection, and the new MethodHandle types that appeared in Java SE version 7.  I also will report a performance shoot-out, so that users may make informed choices between the various mechanisms.