[Bug c++/50495] New: Optimize exact matches in overload resolution

["mathias at gaunard dot com" <gcc-bugzilla at gcc dot gnu dot org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50495

             Bug #: 50495
           Summary: Optimize exact matches in overload resolution
    Classification: Unclassified
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: c++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: mathias@gaunard.com


Overload resolution in GCC (and in C++ in general) is quite slow, and I would
like to suggest the following enhancement: look-up (in constant or logarithmic
time) for exact matches first, then perform regular overload resolution if
necessary.

The idea is that

    struct id_0 {};
    void f(id_0);

    struct id_1;
    void f(id_1) {};

    ...

and then calling

    f(id_x());

should be as fast as

    void f_0();
    void f_1();
    ...

and then calling

    f_x();

Now if this could be made to work for things like

    struct h0 {};
    struct h1 : h0 {};

    struct id_0 {};
    template<class T> void f(id_0, h0<T>);
    template<class T> void f(id_0, h1<T>);

to reduce the set of possible overloads to 2 early (templates inserted to make
it non-absolutely orderable), that would be perfect.

According to my benchmarks, resolving a function with an exact match on the
first argument among 1,000 tags with 10 overloads each takes 30s, while with
1,000 differently named functions of 10 overloads each it takes 100ms.