Virtual methods

[Walter Bright]

bearophile wrote:
> This post is about few simple experiments I've done in D about
> virtual calls and how to improve their performance. So probably this
> can't be useful before D2 is out of alpha state. For people working
> at Sun this stuff is probably very old and very naive, but I think
> currently no D compilers are optimizing this, and if you are not
> interested please ignore this post.


Here's what's going on. The virtual function calls are the calls to 
Internal.walkSum() via an expression typed as Node.walkSum(). The Java 
JIT has access to the entire program, so it can do whole program 
analysis and determine that the *only* instances of Node that ever exist 
are actually instances Internal, therefore all virtual calls to 
Node.walkSum() can be replaced with direct calls to (and inlining of) 
Internal.walkSum(). This is called "direct call optimization".

I'm pretty sure that Java compilers did this optimization from the 
beginning. It is not advanced technology, nor even terribly clever. Even 
C++ compilers did it 10 years earlier (when the static type of the 
instance was known, i.e. it was a value type).

So why doesn't D do it? Because D's optimization runs when compiling a 
module. It does not have access to the whole program, therefore it 
cannot know that the only instances of Node are Internal, and cannot 
make the optimization. (The C++ style optimization can't be done because 
D classes are not value types.)

Making Internal final and Internal.walkSum() final does not help, 
because the types of left and right are Node, not Internal. Another 
module might import this one, have another class derived from Node, and 
store an instance to them in left and right. This would invalidate the 
direct call optimization.

However, if you change the types of left and right from Node to 
Internal, then the compiler knows that walkSum() is final (because 
Internal being final means there are no overrides of walkSum()), and 
hence the direct call optimization can be (and is) performed. You can 
easily verify this by running obj2asm on the output of the compiler.

You can also see it in the e2ir.c source of dmd:

if (!fd->isVirtual() ||
     directcall ||
     fd->isFinal()
    )
{
     // make static call
     ec = el_var(sfunc);
}
else
{
     // make virtual call
     elem *ev;
     unsigned vindex;

     assert(ethis);
     ev = el_same(&ethis);
     ev = el_una(OPind, TYnptr, ev);
     vindex = fd->vtblIndex;

     // Build *(ev + vindex * 4)
     ec = el_bin(OPadd,TYnptr,ev,el_long(TYint, vindex * 4));
     ec = el_una(OPind,TYnptr,ec);
     ec = el_una(OPind,tybasic(sfunc->Stype->Tty),ec);
}