Faster Virtual Method Dispatch

[Dave]

Craig Black wrote:
> Most programmers do not realize the overhead involved with calling a method 
> virtually.  A virtual method call is an O(1) operation.  Just  a vtable 
> lookup and a invoking a function pointer.  However, we must also consider 
> that the CPU has no way of performing branch prediction with vtable lookups, 
> so the pipeline is trashed.  Thus, virtual method calls incur a large 
> performance pentalty.
> 
> Interestly, I found that one of the MSVC++ 2005 compiler's profile guided 
> optimizations is replacing the vtable lookup with if statements for the most 
> commonly called virtual methods followed by the vtable lookup, so that 
> branch prediction can be performed in the majority of cases.
> 
> I do not consider myself an expert in the area of compiler optimization, but 
> knowing the little that I do know I have come up with a simple approach that 
> may improve performance.  This approach is described below.
> 
> Performing a binary search using if statements, and then invoking the 
> methods directly rather than using fuction pointers would allow the method 
> dispatch to take advantage of pipelining.  Algorithmically, however, this is 
> no longer O(1), but O(log n), which is bad.  So I would assume that it would 
> only be faster if n (or the number of methods in the vtable) is lower than a 
> given threshold.  This threshold would be determined by testing and would 
> perhaps be different on different processors.  Thus, in order to ensure that 
> this approach is always faster, a relatively low number should be used.
> 
> Like I said I'm not an expert when it comes to low-level optimization 
> strategies.  I don't know how well such an algorithm would work in practice. 
> Comments are obviously welcome.
> 
> -Craig 
> 

This is a little OT because it involves removing the need for a lot of 
VMD altogether before the assembly code is even generated instead of a 
way to optimize the VMD.

But, I think it would be good to take a look at 'auto-finalization' 
where the compiler front-end determines that a virtual method is not 
needed so just does a direct call.

Not only can more direct calls be made, but potentially the vtable gets 
smaller, the lookups will be less frequent and there will be no need for 
any branch-prediction for direct calls, getting rid of much of the need 
for VMD optimizations for many programs in the first place.

Maybe the semantic processing differences of 'import' over #include 
would make this more straight-forward to do for D compilers over C++.

- Dave