Direct References

The ultimate goal of constant pool resolution is to replace a symbolic reference with a direct reference. The form of symbolic references is well-defined in Chapter 6, "The Java Class File," but what form do direct references take? As you might expect, the form of direct references is yet another decision of the designers of individual Java virtual machine implementations. Nevertheless, there are some characteristics likely to be common among most implementations.

Direct references to types, class variables, and class methods are likely native pointers into the method area. A direct reference to a type can simply point to the implementation-specific data structure in the method area that holds the type data. A direct reference to a class variable can point to the class variable's value stored in the method area. A direct reference to a class method can point to a data structure in the method area that contains the data needed to invoke the method. For example, the data structure for a class method could include information such as whether or not the method is native. If the method is native, the data structure could include a function pointer to the dynamically linked native method implementation. If the method is not native, the data structure could include the method's bytecodes, max_stack, max_locals, and so on. If there is a just-in-time-compiled version of the method, the data structure could include a pointer to that just-in-time-compiled native code.

Direct references to instance variables and instance methods are offsets. A direct reference to an instance variable is likely the offset from the start of the object's image to the location of the instance variable. A direct reference to an instance method is likely an offset into a method table.

Using offsets to represent direct references to instance variables and instance methods depends on a predictable ordering of the fields in a class's object image and the methods in a class's method table. Although implementation designers may choose any way of placing instance variables into an object image or methods into a method table, they will almost certainly use the same way for all types. Therefore, in any one implementation, the ordering of fields in an object and methods in a method table is defined and predictable.

As an example, consider this hierarchy of three classes and one interface:

// On CD-ROM in file linking/ex4/Friendly.java
interface Friendly {

    void sayHello();
    void sayGoodbye();
}

// On CD-ROM in file linking/ex4/Dog.java
class Dog {

    // How many times this dog wags its tail when
    // saying hello.
    private int wagCount = ((int) (Math.random() * 5.0)) + 1;

    void sayHello() {

        System.out.print("Wag");
        for (int i = 0; i < wagCount; ++i) {
            System.out.print(", wag");
        }
        System.out.println(".");
    }

    public String toString() {

        return "Woof!";
    }
}

// On CD-ROM in file linking/ex4/CockerSpaniel.java
class CockerSpaniel extends Dog implements Friendly {

    // How many times this Cocker Spaniel woofs when saying hello.
    private int woofCount = ((int) (Math.random() * 4.0)) + 1;

    // How many times this Cocker Spaniel wimpers when saying
    // goodbye.
    private int wimperCount = ((int) (Math.random() * 3.0)) + 1;

    public void sayHello() {

        // Wag that tail a few times.
        super.sayHello();

        System.out.print("Woof");
        for (int i = 0; i < woofCount; ++i) {
            System.out.print(", woof");
        }
        System.out.println("!");
    }

    public void sayGoodbye() {

        System.out.print("Wimper");
        for (int i = 0; i < wimperCount; ++i) {
            System.out.print(", wimper");
        }
        System.out.println(".");
    }
}

// On CD-ROM in file linking/ex4/Cat.java
class Cat implements Friendly {


    public void eat() {

        System.out.println("Chomp, chomp, chomp.");
    }

    public void sayHello() {

        System.out.println("Rub, rub, rub.");
    }

    public void sayGoodbye() {

        System.out.println("Scamper.");
    }

    protected void finalize() {

        System.out.println("Meow!");
    }
}

Assume these types are loaded into a Java virtual machine that organizes objects by placing the instance variables declared in superclasses into the object image before those declared in subclasses, and by placing the instance variables for each individual class in their order of appearance in the class file. Assuming there are no instance variables in class Object, the object images for Dog, CockerSpaniel, and Cat would appear as shown in Figure 8-1.

Figure 8-1. Some object images.

In this figure, the object image for CockerSpaniel best illustrates this particular virtual machine's approach to laying out objects. The instance variable for Dog, the superclass, appears before the instance variables for CockerSpaniel, the subclass. The instance variables of CockerSpaniel appear in order of declaration: woofCount first, then wimperCount.

Note that the wagCount instance variable appears at offset one in both Dog and CockerSpaniel. In this implementation of the Java virtual machine, a symbolic reference to the wagCount field of class Dog would be resolved to direct reference that is an offset of one. Regardless of whether the actual object being referred to was a Dog, a CockerSpaniel, or any other subclass of Dog, the wagCount instance variable would always appear at offset one in the object image.

A similar pattern emerges in method tables. A method table entry is associated in some way with data structures in the method area that contain sufficient data to enable the virtual machine to invoke the method. Assume that in the Java virtual machine implementation being described here, method tables are arrays of native pointers into the method area. The data structures that the method table entries point to are similar to the data structures described above for class methods. Assume that the particular Java virtual machine implementation that loads these types organizes its method tables by placing methods for superclasses into the method table before those for subclasses, and by placing pointers for each class in the order the methods appear in the class file. The exception to the ordering is that methods overridden by a subclass appear in the slot where the overridden method first appears in a superclass.

The way this virtual machine would organize the method table for class Dog is shown in Figure 8-2. In this figure, the method table entries that point to methods defined in class Object are shown in dark gray. Entries that point to methods defined in Dog are shown in light gray.

Figure 8-2. The method table for class Dog.

Note that only non-private instance methods appear in this method table. Class methods, which are invoked via the invokestatic instruction, need not appear here, because they are statically bound and don't need the extra indirection of a method table. Private methods and instance initialization methods need not appear here because they are invoked via the invokespecial instruction and are therefore statically bound. Only methods that are invoked with invokevirtual or invokeinterface appear in this method table. See Chapter 19, "Method Invocation and Return," for a discussion of the different invocation instructions.

By looking at the source code, you can see that Dog overrides the toString() method defined in class Object. In Dog's method table, the toString() method appears only once, in the same slot (offset seven) in which it appears in the method table for Object. The pointer residing at offset seven in Dog's method table points to the data for Dog's implementation of toString(). In this implementation of the Java virtual machine, the pointer to the method data for toString() will appear at offset seven for every method table of every class. (Actually, you could write your own version of java.lang.Object and load it in through a user-defined class loader. In this manner you could create a namespace in which the pointer to toString() occupies a method table offset other than seven in the same Java virtual machine implementation.)

Below the methods declared in Object, which appear first in this method table, come the methods declared in Dog that don't override any method in Object. There is only one such method, sayHello(), which has the method table offset 11. All of Dog's subclasses will either inherit or override this implementation of sayHello(), and some version of sayHello() will always appear at offset 11 of any subclass of Dog.

Figure 8-3 shows the method table for CockerSpaniel. Note that because CockerSpaniel declares sayHello() and sayGoodbye(), the pointers for those methods point to the data for CockerSpaniel's implementation of those methods. Because CockerSpaniel inherits Dog's implementation of toString(), the pointer for that method (which is still at offset seven) points the data for Dog's implementation of that method. CockerSpaniel inherits all other methods from Object, so the pointers for those methods point directly into Object's type data. Note also that sayHello() is sitting at offset eleven, the same offset it has in Dog's method table.

Figure 8-3. The method table for class CockerSpaniel.

When the virtual machine resolves a symbolic reference (a CONSTANT_Methodref_info entry) to the toString() method of any class, the direct reference is method table offset seven. When the virtual machine resolves a symbolic reference to the sayHello() method of Dog or any of its subclasses, the direct reference is method table offset eleven. When the virtual machine resolves a symbolic reference to the sayGoodbye() method of CockerSpaniel or any of its subclasses, the direct reference is the method table offset twelve.

Once a symbolic reference to an instance method is resolved to a method table offset, the virtual machine must still actually invoke the method. To invoke an instance method, the virtual machine goes through the object to get at the method table for the object's class. As mentioned in Chapter 5, "The Java Virtual Machine," given a reference to an object, every virtual machine implementation must have some way to get at the type data for that object's class. In addition, given a reference to an object, the method table (a part of the type data for the object's class) is usually very quickly accessible. (One potential scheme is shown in Figure 5-7.) Once the virtual machine has the method table for the object's class, it uses the offset to find the actual method to invoke. Voila!

The virtual machine can always depend on method table offsets when it has a reference of a class type (a CONSTANT_Methodref_info entry). If the sayHello() method appears in offset seven in class Dog, it will appear in offset seven in any subclass of Dog. The same is not true, however, if the reference is of an interface type (a CONSTANT_InterfaceMethodref_info entry). With direct references to instance methods accessed through an interface reference there is no guaranteed method table offset. Consider the method table for class Cat, shown in Figure 8-4.

Figure 8-4. The method table for class Cat.

Note that both Cat and CockerSpaniel implement the Friendly interface. A variable of type Friendly could hold a reference to a Cat object or a CockerSpaniel object. With that reference, your program could invoke sayHello() or sayGoodbye() on a Cat, a CockerSpaniel, or any other object whose class implements the Friendly interface. The Example4 application demonstrates this:

// On CD-ROM in file linking/ex4/Example4.java
class Example4 {

    public static void main(String[] args) {

        Dog dog = new CockerSpaniel();

        dog.sayHello();

        Friendly fr = (Friendly) dog;

        // Invoke sayGoodbye() on a CockerSpaniel object through a
        // reference of type Friendly.
        fr.sayGoodbye();

        fr = new Cat();

        // Invoke sayGoodbye() on a Cat object through a reference
        // of type Friendly.
        fr.sayGoodbye();
    }
}

In Example4, local variable fr invokes sayGoodbye() on both a CockerSpaniel object and a Cat object. The same constant pool entry, a CONSTANT_InterfaceMethodref_info entry, is used to invoke this method on both objects. But when the virtual machine resolves the symbolic reference to sayHello(), it can't just save a method table offset and expect that offset to always work in future uses of the constant pool entry.

The trouble is that classes that implement the Friendly interface aren't guaranteed to have a common superclass that also implements Friendly. As a result, the methods declared in Friendly aren't guaranteed to be in the same place in all method tables. If you compare the method table for CockerSpaniel against the method table for Cat, for example, you'll see that in CockerSpaniel, sayHello()'s pointer occupies offset 11. But in Cat, sayHello() occupies offset 12. Likewise, CockerSpaniel's sayGoodbye() method pointer resides in offset 12, but Cat's sayGoodbye() method pointer resides at offset 13.

Thus, whenever the Java virtual machine invokes a method from an interface reference, it must search the method table of the object's class until it finds the appropriate method. This is why invoking instance methods on interface references can be significantly slower than invoking instance methods on class references. Virtual machine implementations can attempt to be smart, of course, about how they search through a method table. For example, an implementation could save the last index at which they found the method and try there first the next time. Or an implementation could build data structures during preparation that help them search through method tables given an interface reference. Nevertheless, invoking a method given an interface reference will likely be to some extent slower than invoking a method given a class reference.