Re: [boost] Overload resolution speed

Subject: Re: [boost] Overload resolution speed
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-09-23 19:30:29

on Fri Sep 23 2011, Sebastian Redl <sebastian.redl-AT-getdesigned.at> wrote:

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

I know this is a technicality, but...

The fact that an efficient algorithm for X exists does not mean every
author of code that does X has promised to use that algorithm.  It also
doesn't guarantee that factors not considered in the description of the
algorithm (name mangling, generation of debug info, etc.) won't make it
inefficient in practice.

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

I'm sure that even with Clang one can demonstrate metaprograms whose
compilation in principle ought to be linear but are slower than that in
practice.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com