Re: [boost] Overload resolution speed

Subject: Re: [boost] Overload resolution speed
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2011-09-23 08:09:28

On 22/09/2011 11:25, Sebastian Redl wrote:
> On 21.09.2011 20:20, Mathias Gaunard wrote:
>> As part of the Boost.SIMD effort, another library was developed,
>> Boost.Dispatch, which relies heavily on overload resolution.
>>
>> Back to the benchmark, making the number of functions vary show an
>> apparent exponential increase in compile time. It's reasonably fast
>> for 100 functions, but not at all for 1,000.
> Overload resolution is supposed to be linear in the number of overloads.

O(1) or O(log n) even seems possible for certain cases but it doesn't 
seem compilers optimize for them.

Consider, for N unique different and unrelated types Ti, N overloads of 
the form
void f(Ti);

If I call f(T0()), it shouldn't need to test the N-1 other overloads.

And that kind of logic should apply to cull the set of viable overloads 
  when any of the arguments matches exactly.

If now I have, for each Ti,
template<class T> void f(Ti, foo0<T>);
template<class T> void f(Ti, foo1<T>);
template<class T> void f(Ti, foo2<T>);
template<class T> void f(Ti, foo3<T>);

if I call f(T0(), something) I should first reduce the set of possible 
overloads to 4 then find out what the best one is out of these.