split vtables (example code in C++)

[John Rose]

I was talking to some of the GC guys in Stockholm about refactoring the oop-tracing code.
The long-standing problem is that each type heap node (InstanceKlass, ObjArrayKlass, etc.)
needs its own oop iteration algorithm.  For performance, each oop iteration must inline each
major leaf operation (OopClosure, etc.).  This requires devirtualization of the leaf operations,
which in turn requires making customized copies of each kind of loop, for each kind of leaf.
That is, the number of loop codes is MxN, where M is the number of loops and N the leaves.

This is what I call the "loop customization problem".  Solving it in the JVM (without quadratic
code explosion) gives a powerful boost to Java programs.  Solving it in C++, however, is very
difficult.  Basically, you need to have a "virtual template" member function for each Klass.
That's illegal, for good reason:  C++ is a static language, and variable-sized vtables are not
a static construct.  (The JVM needs to get better at such tricks also, as I said in my JFokus
talk.)  But, it is possible, with some careful work, to get an MxN dispatch in C++, by manually
"splitting" the loop methods, and their vtable slots, across the desired leaf operation classes.

I worked out a clean way to do this; please take a look if you are interested in this problem.

http://cr.openjdk.java.net/~jrose/draft/splitvtbl.cpp

Maybe this is written up in somebody's book of C++ patterns, but I've never seen it expressed
in this way before.  Visitors come close, but these are something more tightly coupled than the
visitor pattern, because the branches of the visitor-like dispatch are versions of the same template.

Enjoy,
— John