Faster Virtual Method Dispatch

[Craig Black]

"BCS" <BCS_member at pathlink.com> wrote in message 
news:e2go6m$13u7$1 at digitaldaemon.com...
> 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.

Nope you are right.  Which vtable.  My bad.

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

Yes, like MSVC's profile guided optimization.  A more general optimization 
would be nice too, but you could probably be even faster and more efficient 
with a profile-guided one.  One real good thing about profile guided 
optimizations is that the compiler can spend more time on optimizing 
performance-critical code sections and less time on code that is not 
pertinent to performance.

-Craig