Faster Virtual Method Dispatch

[kris]

Dave wrote:
> 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

Yes, I recall seeing Walter write something along these lines somewhere 
in the D documentation: being able to compile the entire program, versus 
linking things in from a library, permits much more aggressive 
finalization of methods as you describe. That's definately a benefit.