Polymorphism & Dispatch: vtables, Interfaces and Their Cost

"Polymorphism" covers four unrelated mechanisms that happen to share a Greek root. Keeping them apart matters because they are resolved at different times, and mistaking compile-time resolution for run-time resolution produces a specific family of bugs that look impossible from the call site.

Overloading is not dispatch #

This is the trap. Overload selection happens at compile time using declared types; overriding happens at run time using the object.

class Animal {} 
class Dog extends Animal {}

void feed(Animal a) { System.out.println("animal"); }
void feed(Dog d)    { System.out.println("dog"); }

Animal a = new Dog();
feed(a);            // prints "animal" — the static type decides

Nothing dynamic happens here at all. The same rule makes remove(int) and remove(Object) on List<Integer> two different methods, so list.remove(2) removes the element at index 2 while list.remove(Integer.valueOf(2)) removes the value 2 — a real and repeatedly-shipped bug. Do not overload on types related by subtyping, and prefer distinct names when the behaviours differ.

What a vtable is #

Single-inheritance virtual dispatch is a two-load-and-jump sequence. Each object carries a pointer to its class's table of function pointers; the table is laid out so that a given method sits at the same index for the base class and every subclass.

d: Dog ─────┐            Dog vtable
            │  vptr ──►  [0] speak  → Dog::speak
            │            [1] eat    → Animal::eat   (not overridden)
            └  fields…   [2] fetch  → Dog::fetch

mov  rax, [rdi]         ; load vptr from the object
call [rax + 8*index]    ; indirect call through the slot

The fixed index is why single inheritance is cheap and why interfaces are not: a class can implement many interfaces, so a given interface method has no single stable index across implementers. The JVM uses per-interface method tables (itables) with a search, HotSpot caches the result at the call site, and C++ multiple inheritance introduces thunks that adjust this before the call. Go stores an itab — a (interface type, concrete type) pair with the method pointers — inside the interface value itself, which is why a Go interface value is two words and why nil interface comparison behaves the way it does (nullability).

Rust's dyn Trait is the same idea made explicit: a trait object is a fat pointer, one word to the data and one to the vtable, which is why dyn Trait is unsized and always appears behind & or Box.

The cost, honestly #

The naive claim is "virtual calls are slow". The accurate claim is that virtual calls are cheap when the target is predictable and expensive when it is not — and that the real cost is usually the lost inlining, not the indirection.

• Monomorphic call site (one receiver type ever seen): the JIT or the branch predictor makes the indirect call essentially free, and HotSpot will typically devirtualize and inline it outright — using Class Hierarchy Analysis when only one implementation is loaded, with a guard and a deoptimization path if a second one appears later.
• Bimorphic (two types): still handled by an inline cache — a compare-and-branch on the receiver's class, with both targets inlinable.
• Megamorphic (many types): falls back to a real indirect call. A mispredicted indirect branch on a modern out-of-order x86 core costs on the order of 15–20 cycles, and — usually worse — the compiler cannot inline through it, which blocks constant folding, escape analysis and vectorization in the surrounding code.

Rust makes the choice explicit at the type level, which is the clearest model of the trade:

fn draw_static<T: Shape>(s: &T)   { s.draw() }   // monomorphized: one body per T, inlinable
fn draw_dynamic(s: &dyn Shape)    { s.draw() }   // one body, vtable call, no inlining

Dispatch on two types #

Virtual dispatch selects on one receiver. When behaviour depends on two runtime types — an intersection test between shape kinds, an operation over an AST node in a compiler pass — single dispatch is not enough. The options:

• Double dispatch / visitor — element.accept(visitor) then visitor.visitCircle(this). Two virtual calls select the pair. It makes adding operations cheap and adding types expensive, since every visitor must grow a method. That trade is the expression problem, and it is the whole reason to pick or reject visitor.
• Pattern matching on sealed types — switch (shape) { case Circle c -> …; case Square s -> …; }. Same selection, checked for exhaustiveness by the compiler, and it inverts the trade: adding a type breaks every switch (loudly, at compile time), adding an operation touches one place.
• A type-pair table — an explicit map from (type, type) to handler. Verbose, but the only option that stays open in both directions at run time.