Research task: Examine strategies for optimizing vtable/itable dispatch in the closed world

[dmlloyd]

The initial dispatch algorithm will amount to using comparisons against the numerical class ID of the target object. This implementation is simple to implement, while also aggressively favoring devirtualization. However there are many cases which might be better served by a more sophisticated solution.

This task is to identify different likely dispatch cases and their characteristics, to research possible dispatch strategies, and to determine the best strategy to use for each case and the tradeoffs therein.

[DanHeidinga]

zulip discussion: https://quarkusio.zulipchat.com/#narrow/stream/237892-qcc/topic/vtables.20(or.20image.20data.20structure.20layout)

And the example from that discussion:

class Call {	// ID: 1

call_foo(A a) {
	a.foo();
	// gets compiled to A.dispatch(a), right?
}

}

class A {	// ID: 2
	void bar() { }
	void foo() { /* A */ }
	void baz() { }

	// ignoring the other methods like `bar` and `baz` which will need
	// their own dispatch methods or the method id to be checked here
	// as well
	static synthetic dispatch(A a) {
		id i = a.getID();
		if (i == 2) {
			foo();
		} else if (id == 3) {
			B.dispatch(a);
		} else if (id == 4) {
			C.dispatch(a);
		}
	}		
}

class B extends A { 	// ID: 3
	void baz() { }

	static synthetic dispatch(A a) {
		foo();	/* A */
	}

}

class C extends A {	// ID: 4
	void foo() { /* C */ }

	static synthetic dispatch(A a) {
		id i = a.getID();
		if (i == 4) {
			foo(); /* C */
		} else if (i == 5) {
			D.dispatch(a);
		}
	}
}

class D extends C {	// ID: 5
	void foo() { /* D */ }

	static synthetic dispatch(A a) {
		foo();  /* D */
	}
}


class Test {		// ID: 6

	void test() {
		call_foo(new A());	/* A */
		call_foo(new B());	/* A */
		call_foo(new C());	/* C */
		call_foo(new D());	/* D */
	}
}

[dmlloyd]

It sounds like the LLVM switch instruction may be optimized well in many cases using a variety of possible strategies - for example, it may lower into a jump table, binary search, or if tree, among other things - so it's possible that we won't have to have more than one strategy on the back end to cover the mono- vs megamorphic spectrum (though it is possible that we may end up wanting to provide metadata to guide the optimization strategy somewhat).

[dmlloyd]

This is handled in LLVM here:

• https://github.com/llvm/llvm-project/blob/master/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp#L10566-L10652
• https://github.com/llvm/llvm-project/blob/master/llvm/lib/CodeGen/SwitchLoweringUtils.cpp

[DanHeidinga]

In terms of debugging, I'd rather have a canonical vtable to look at rather than manually searching the dispatch methods. Obviously the front end should be devirtualizing and inlining as much as possible / reasonable

[dmlloyd]

What type of debugging are you thinking of where it might be a concern? Run time program debugging, or debugging the generated code itself?

From the latter perspective I imagine that having the dispatch methods physically together in the .ll file could be conceptually equivalent to having a single canonical vtable (in terms of being able to validate the correctness of the generated code), while still allowing the backend to optimize effectively (including potentially inlining the dispatch methods and thereby eliminating possible branches) based on the breadth of the table.

For run time program debugging, it seems like it would be less of a concern how dispatch is organized, but maybe there's a case that I should be thinking of but I'm not?

[DanHeidinga]

Debugging behaviour differences between the native image and the regular JVM. When default methods were added to interfaces back in JDK 8, I spent a lot of time debugging dispatch issues and being able to dump the vtables for different classes and compare them made it much clearer where the bugs where.

Tracing through multiple layers of dispatch methods would have been less pleasant.

For methods like Object#toString, which will have deep hierarchies and implementors in many different layers, we may end up with a higher footprint from generating the code for the dispatch routines (even if lowered to jump tables) per-callsite code than creating a vtable per class.

[dmlloyd]

My current plan for supporting a particular dispatch implementation is to introduce transformations during the lowering stage of compilation which removes all method invocations in favor of either inlining or function calls (through a table if needed). This should allow us to implement multiple independent strategies for dispatch and devirtualization which can work together or be switched out - in particular it should allow us to start off with something trivial and improve from there. Importantly, it removes the burden of implementing dispatch from the back end.

I'm seeing how it would look to have a separate FunctionElement element type along with function invocation node types to determine if this approach is feasible.