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);
}

Reply via email to