Faster Virtual Method Dispatch

[Hasan Aljudy]

I'm far from being an expert .. but I thought vtable lookups involve two 
  or three jump/call instructions at the assembly level; at least that's 
the impression I got from stepping through code in the VC++ debugger.

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 
> 
>