Calling Methods in Ŋ

Introduction

Ŋ is a fully dynamic programming language for the JVM. in Ŋ the behaviour of a class is not known until run time and its behaviour can be changed whist the program is running. In Java the behaviour of an object is determined by its Class object, in Ŋ the behaviour is determined by its MetaClass object. The MetaClass, unlike the Class, is mutable and so can be changed to change the behaviour of the object. The MetaClass must be consulted every time a method is called on the object, a field is referenced, the object is constructed or an operator is applied to the object. In general this is done by calling a method on the MetaClass and passing the object as a parameter. The MetaClass then ensures that the object exhibits the correct behaviour.

The behaviour of an object can be changed by Monkey Patching or via a Category. Both can add, remove or modify the behaviour of a method or an operator and can add, remove or modify fields and properties. If you change the behaviour of an object via Monkey Patching then all object of the same class will exhibit the new behaviour immediately throughout the JVM. If you change the behaviour of an object via a Category then the behaviour of all objects of the same class will be changed only in the thread in which the Category is applied.

Ŋ supports seamless integration with Java so an Ŋ class can subclass a Java class and a Java class can subclass a Ŋ class. Ŋ is optionally typed which helps this integration considerably.

It is very challenging to get fully dynamic languages to run quickly on the JVM. Ŋ aims to perform no more than 10 times slower than the equivalent Java program on the JVM. Method invocation is one of the crucial areas which need to be optimised if this goal is to be achieved.

In order to make life slightly more interesting for the implementers we do not allow ourselves to do dynamic code generation to assist in method dispatch. This is to allow us to run on platforms where dynamic code generation is impossible (either for security reasons or because we are running on Google's Android which does not execute normal bytecodes).

The ThreadContext

Before you understand about method calls you need to understand about the ThreadContext object. There is one instance of ThreadContext for every thread in an Ŋ program. The original use of ThreadContext was to hold information about any Categories in force in the thread. It turns out it's also useful for holding all manner of junk that the program needs. In general the compiler will not generated code which directly calls the MetaClass it will generate a call to the ThreadContext which will call the MetaClass passing the MetaClass information about any relevant Category in force in the thread. The ThreadContext for each thread is held in thread local storage so it's always possible to get it in a method. However it's a little expensive to keep retrieving it from thread local storage so we try to pass it into each method we call. That slightly complicates to code we generate when compiling Ŋ but the complexity is worth it.

Compiling a Method in an Ŋ Class

Every method on an Ŋ class is compiled to several methods in the resulting class file. Initially we are going to look at two of them:


The following Ŋ class


class C {

  public int foo(int bar) {

    // some statements here

  }

}


is compiled into the equivalent of this (nearly) Java class


class C extends BaseNgObject {

  public int foo(int bar) {

    // Get the ThreadContext and call foo(bar) via it

  }


  synthetic public static int C$foo(ThreadContext tc, C instance, int bar) {

    // some statements here

  }

}


The effect of this is that, from a Java perspective, the class has a single method int foo(int). Calling that method from Java will result in the body of foo being executed unless foo has been changed by Monkey Patching or a Category in which case the modified behaviour will be seen from Java.
When you call int foo(int) via the ThreadContext then int C$foo(int) is called rather than int foo(int).

There are three consequences of this:

    1. Java will see some of the dynamic behaviour of an Ŋ class when making method calls.
    2. The Java call to Ŋ will be slower than a Java call to Java (but we will see later that we can do something to minimise that).
    3. The Ŋ to Ŋ call will pass through the ThreadContext object so that it does not have to be reloaded from thread local storage are the start of every method.

You will see that C extends the class BaseNgObject. This means that it implements two interfaces - NgObject and CompiledNgObject . The CompiledNgObject interface is the one of interest to us at the moment.

CompiledNgObject looks like this:

public interface CompiledNgObject {
  Object ng$Call(ThreadContext tc, int methodNumber) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, boolean p1) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, char p1) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, byte p1) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, short p1) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, int p1) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, long p1) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, float p1) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, double p1) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, BigInteger p1) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, BigDecimal p1) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, Object params[]) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, Object p1) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, Object p1, Object p2) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, Object p1, Object p2, Object p3) throws Throwable;
  Object ng$Call(ThreadContext tc, int methodNumber, Object p1, Object p2, Object p3, Object p4) throws Throwable;
}

This interface is the way in which we do fast method dispatch from the MetaClass. Every method on an Ŋ has an identifying number. This number is made of two parts. The first is the subclass depth (java.lang.Object = 0, ng.runtime.BaseNgObject = 1, C = 2). The second is the index of the method in the class (int foo(int) = 0).
The compiler generates implementations for the appropriate versions of these methods to with a switch on the methodNumber where the case statements dispatch the call to the synthetic static method which contains the code for the method being called. In the example class C this would involve implementing the ng$call method which took a single int parameter (as well as ThreadContext and methodNumber parameters, of course).

The MetaClass performs two steps when performing a method call - method selection and method dispatch.

Method Selection

The MetaClass is given the instance of the object on which the call is made, the name of the method and the actual parameters. Its first job is to find which method best matches this set of data. The candidate set is the non synthetic methods declared on the object as modified by any Monkey Patching and Category. This set is reduced to those methods which match by name and number of parameters. In many cases this results in a single candidate. In the cases where more than one candidate is left the one with the best match for the types of the actual parameters is chosen (this is a simple explanation of a complex and sometimes expensive process. It is explained in detail in a later document).

Method Dispatch

Methods are represented inside the MetaClass as callable objects. The method selection process results in the identification of one of these objects as the one to use to call the method. When the target object implements CompiledNgObject the method dispatch logic for a.foo(1) inside the callable object looks like this:

public Object doCall(ThreadContext tc, Object instance, int p1) {
  return ((CompiledNgObject)instance).ng$Call(tc, this.methodNumber, p1);
}

in the case of foo, methodNumber would be 0X02000000 + 0X00000000 (zeroth method in the 2nd class from Object).

Optimising Method Selection

We have seen that method dispatch can be made quite cheap if we compile helper methods into the class. Method selection remains complex and costly. There are situations in which we can use our partial knowledge about the type of the object we are making the call on to improve this performance.
We know, for instance that in C this is an instance of C or a subtype of C. As Ŋ allows optional typing then the programmer can tell the compiler something about the type of the object. Finally, it is possible to infer the type of the object in some circumstances.
We generate a third method for foo on C. This is a synthetic instance method called shadow$foo.

class C {

  public int foo(int bar) {

    // some statements here

  }

}


is now compiled into the equivalent of this (nearly) Java class


class C extends BaseNgObject {

  public Object ng$Call(ThreadContext tc, int methodNumber, int p1) throws Throwable {

    if (methodNumber == 0X02000000) return tc.wrap(C$foo(tc, this, p1)); // return boxed int

    return super(tc, methodNumber, p1);

  }


  public int foo(int bar) {

    ThreadContext tc = ThreadContext.getThreadContext();

    try {

      return shadow$foo(tc, bar);

    } catch(ObjectResultException e) {

        // get the result from e

        // if it can be coerced into an int return that

        // if not throw an exception

    }

  }



  synthetic public static int C$foo(ThreadContext tc, C instance, int bar) {

    // some statements here

  }


  synthetic public int shadow$foo(ThreadContext tc, int bar) throws ObjectResultException {

    if (some checks are OK) return C$foo(tc, this, bar);

    // call via the ThreadContext and return the result by throwing the ObjectResultException

  }

}


The Ŋ compiler will generate a direct call to shadow$foo if it knows that the object is an instance of C and that the types of the actual parameter exactly match the types of the formal parameter (i.e. is an int). It can't generate a call to foo directly because it is not 100% sure that this is the right target. shadow$foo has to check that foo is actually the right call target. It does this by asking the ThreadContext if the call can go ahead.

How does ThreadContext know if the call is safe?

The call in ThreadContext looks like tc.canICall(0X02000000, this.getMetaClass()). If the object is not a subclass of C and there has been no Monkey Patching or Category which has messed with foo then the call can go ahead immediately. The ThreadContext knows about Categories and the MetaClass knows about Monkey Patching and also knows which class it represents. This check can be carried out very quickly (basically it's three compares). When the object is a subclass of C we have to look at all the MetaClasses representing all its subclasses until we get to the one for C. This is slightly slower but lots faster than doing the full selection in the MetaClass.

What do we do if it is not safe?

We make the call via the ThreadContext in the normal way. However that returns an Object not an int. We deal with this by wrapping the object in an Exception and then throwing the exception. This is not expensive as the Exception is pre-allocated (one per thread and held in the ThreadContext object).

What does the generated code look like?

C o = new C()
...
def x = o.foo(1)

compiles to:

try {
  x = tc.wrap(o.shadow$foo(1));
} catch (ObjectResultException e) {
  x = e.getResult();
}

Possible Future Optimisations

It is possible to add yet another synthetic method which is called when the actual parameter types are unknown or don't match foo's parameter types exactly. This would probably only be generated when there was only one static target which had the same name and number of parameters.

Note that it would be possible to do away with shadow$foo and just generate the code inline. I'm not sure this is a good idea. It bloats the class file and HotSpot should inline the call as needed.