Faster Virtual Method Dispatch

[Craig Black]

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