IMT

IMT (Interface Method Table)

Method dispatch table for interface calls, optimized over vtable.

Overview

The IMT (Interface Method Table) is a fixed-size hash table embedded in the TIB (Type Information Block) that enables efficient interface method dispatch. Unlike the vtable which provides O(1) lookup for class inheritance calls, interface dispatch must find the correct implementation among all interfaces implemented by a class. The IMT solves this by using a precomputed hash of method name and signature (the "selector") to index into a fixed 64-element table (ObjectLayout.IMT_LENGTH).

Interface dispatch is fundamentally harder than virtual method dispatch because:

• A class can implement multiple interfaces, each with potentially overlapping method sets
• The set of interfaces is determined at compile time but resolved at runtime
• Finding the right method without a table would require walking the interface hierarchy

The IMT addresses this by computing index = selector % 64 at class preparation time. Each slot either holds a single method (no collision) or a collision list (chained linear search). The CompiledIMT layer further optimizes this into architecture-specific machine code for fast runtime dispatch.

Key Components

Class / File	Role
core/src/core/org/jnode/vm/classmgr/IMTBuilder.java	Builds the IMT with hash-based insertion and collision chaining
core/src/core/org/jnode/vm/classmgr/VmClassType.java	Implements prepareIMT() constructing IMT from all implemented interfaces
core/src/core/org/jnode/vm/classmgr/VmType.java	Coordinates IMT creation during class preparation, stores in TIB
core/src/core/org/jnode/vm/classmgr/ObjectLayout.java	Defines IMT_LENGTH = 64 as the hash table size
core/src/core/org/jnode/vm/classmgr/VmConstIMethodRef.java	Holds selector for interface method references
core/src/core/org/jnode/vm/compiler/IMTCompiler.java	Abstract base for architecture-specific IMT compilation
core/src/core/org/jnode/vm/compiler/CompiledIMT.java	Abstract result of IMT compilation, provides getIMTAddress()
core/src/core/org/jnode/vm/x86/compiler/X86CompiledIMT.java	x86-specific CompiledIMT holding bytecode array

How It Works

TIB Layout

The IMT lives in the TIB at fixed indices alongside the vtable:

TIB[index] Layout:
  [0] VmType reference
  [1] IMT (Interface Method Table) — Object[]
  [2] IMT collision flags — boolean[]
  [3] CompiledIMT — compiled dispatch code
  [4] Superclasses array
  [5..N] vtable (VmInstanceMethod references)

See Object-Layout for full TIB structure and Virtual-Methods for the complete picture.

Hash Table Structure

The IMT is a fixed 64-element array (ObjectLayout.IMT_LENGTH). Method lookup uses:

index = selector % IMT_LENGTH  // selector = hash(name + signature)

This gives a constant-time first probe. If the slot is occupied by a different method, a collision list is searched.

Construction with IMTBuilder

IMTBuilder constructs the IMT by iterating over all interface methods and inserting them:

public IMTBuilder() {
    final int length = ObjectLayout.IMT_LENGTH; // 64
    this.imt = new Object[length];
    this.imtCollisions = new boolean[length];
}

public void add(VmInstanceMethod method) {
    final int index = method.getSelector() % getLength();

    if (imt[index] == null) {
        // Empty slot — direct insert
        imt[index] = method;
    } else if (imtCollisions[index]) {
        // Already a collision list — extend it
        final Object[] oldList = (Object[]) imt[index];
        final Object[] newList = new Object[oldList.length + 1];
        System.arraycopy(oldList, 0, newList, 0, oldList.length);
        newList[oldList.length] = method;
        imt[index] = newList;
    } else {
        // First collision at this slot — create a list
        final Object[] collisionList = new Object[2];
        collisionList[0] = imt[index];      // Existing method
        collisionList[1] = method;           // New method
        imt[index] = collisionList;
        imtCollisions[index] = true;
        collectionCount++;
    }
}

IMT Construction in VmClassType

The IMT is built during class preparation by VmClassType.prepareIMT():

IMTBuilder imtBuilder = new IMTBuilder();
for (VmInterfaceClass intf : allInterfaces) {
    for (VmMethod intfMethod : intf.getType().getMethods()) {
        if (intfMethod.isPublic() && !intfMethod.isStatic()) {
            final VmInstanceMethod clsMethod = resolveInterfaceMethod(intfMethod);
            imtBuilder.add(clsMethod);
        }
    }
}
// Result stored in TIB at IMT_INDEX, collisions at IMTCOLLISIONS_INDEX
tib[TIBLayout.IMT_INDEX] = imtBuilder.getImt();
tib[TIBLayout.IMTCOLLISIONS_INDEX] = imtBuilder.getImtCollisions();

CompiledIMT Generation

For faster runtime dispatch, the IMT is compiled into architecture-specific machine code:

final CompiledIMT cimt = loader.compileIMT(imtBuilder);
tib[TIBLayout.COMPILED_IMT_INDEX] = cimt.getIMTAddress();

IMTCompiler is the abstract base; X86CompiledIMT holds the resulting bytecode array. The compiled form is a jump table that maps a selector hash directly to the method code entry, avoiding collision list traversal in the common (no-collision) case.

Interface Method Resolution

When an interface method is invoked on an object, the runtime resolves it via:

1. Load TIB reference from object header (offset -1)
2. Load IMT array from TIB[1]
3. Compute index = methodRef.getSelector() % 64
4. Lookup imt[index]
5. If single method, use it; if collision list, linear search by selector

Gotchas & Non-Obvious Behavior

• Fixed hash table size: The 64-element IMT is shared across all classes. As more interface methods are added to a class, the probability of collisions increases. The collision list mechanism handles this, but lookup is no longer pure O(1).
• Selector hashing: The selector is a precomputed hash of method name + signature, not a sequential index. Selector values are stable per method reference across the entire VM.
• Class-specific collision patterns: Two classes implementing the same interfaces may have different collision lists because method insertion order varies. The JIT cannot assume IMT slot contents are identical across classes.
• CompiledIMT as optimization: If CompiledIMT is null, the runtime falls back to Java-side IMT lookup with collision list traversal. The compiled form is preferred because it inlines the dispatch logic.
• JIT must understand IMT structure: Interface call compilation (visit_invokeinterface) cannot use simple indexed load like virtual calls (visit_invokevirtual). The JIT must emit the hash computation and conditional branch for collision handling, or use the CompiledIMT if available.
• Multiple interfaces with same method: If two interfaces declare the same method (name + signature), the IMT handles this correctly because both resolve to the same selector and thus the same IMT slot.

Related Pages

• Virtual-Methods — Overview of method dispatch including vtable and IMT relationship
• vtable — Virtual method table for class inheritance dispatch
• Object-Layout — TIB structure and object header layout
• Type-System-Internals — VmType hierarchy, class preparation, and TIB construction
• JIT-Compilers — How compilers use IMT for interface call compilation
• CompiledIMT — Architecture-specific compiled IMT (referenced from this page)