Re: [boost] Overload resolution speed

Subject: Re: [boost] Overload resolution speed
From: Sebastian Redl (sebastian.redl_at_[hidden])
Date: 2011-09-23 07:51:20

On 22.09.2011 17:57, Dave Abrahams wrote:
> on Thu Sep 22 2011, Sebastian Redl<sebastian.redl-AT-getdesigned.at>  wrote:
>
>> Overload resolution is supposed to be linear in the number of
>> overloads.
> According to whom?
The C++ standard has a footnote that outlines a linear algorithm for 
overload resolution.
Clang follows this algorithm, and I suspect pretty much every other 
compiler does as well.
Therefore, if resolution is superlinear, it's a bug.
>> In general, all algorithms in a compiler should be linear, or worst
>> case n*log(n). Any quadratic or worse algorithm is pretty much a bug.
> I'd like to think so, too, but I'm not sure all implementors would agree
> with you.
I can't speak for any other compilers, but I'm pretty sure Ted and Doug 
would agree with me about the main compilation pass of Clang.
We make exceptions for emitting errors, and of course for the static 
analyzer, whose pass-sensitive checks are inherently exponential.

Sebastian