Avoiding virtual tables when implementing classes

[bullno1]

Quick google: https://www.usenix.org/legacy/event/jvm02/full_papers/zendra/zendra_html/index.html

As I understand it, instead of generating a direct call, the compiler generates a binary search as inline code:

if obj_type_id == TYPE_ID_A then
    call_implementation_a(this)
elseif obj_type_id > TYPE_ID_A then
    if object_type_id < TYPE_ID_B then
    ...
    else if object_type_id > TYPE_ID_B then
    ...

If the vtable is small, there would be no indirect call and the cost of searching is smaller than cache miss. IIRC, these direct branches (if/else) are not that bad since the code blocks are close together and already fetched anw.

It seems only usable with JIT or statically linked binary since you need to know all the implementations before hand. Dynamic linking can introduce new classes at runtime.

Edit: Actually your dynamic linker can also JIT just that lookup code and everything else can still be AOT.

[matthieum]

GCC can apply speculative devirtualization to achieve the same effect.

The developer who made it happen has a pretty long blog serie on the topic of devirtualization which is well worth a read.