Faster Virtual Method Dispatch

BCS BCS_member at pathlink.com
Sun Apr 23 13:31:19 PDT 2006


In article <e2ggdq$lat$1 at digitaldaemon.com>, Craig Black says...
>
>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 

IIRC what is being searched for isn't which entry in this vtbl, but which vtbl
to use. Or maybe I am miss understanding you.

>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 


Maybe some sort of run-and-review optimization could be done. This would entail
having the compiler build a heavily instrumented version of the program and then
run it a bunch to find out which classes are most commonly used at a given call
and then on the next build let the compiler optimize each call based on the
measured data. 

If this is class ABC 
call ABC.foo
else if XYZ 
call XYZ.foo
else
use the vtbl





More information about the Digitalmars-d mailing list