<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/128795>128795</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [clang] conversion function lookup is unnecessarily slow with many conversion functions and no conversion function templates
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            clang
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          zygoloid
      </td>
    </tr>
</table>

<pre>
    Here's a technique for doing K member lookups in a type list of N elements in O(N+K) time (note that most techniques require O(NK) time):

```c++
template <typename ...T>
struct TypeList;

struct MembershipTesterBaseA {
 template<typename T> operator T();
};
struct MembershipTesterBaseB {
 template<typename T> operator T();
};
template <typename ...T>
struct MembershipTester : MembershipTesterBaseA, MembershipTesterBaseB {
  using MembershipTesterBaseA::operator T...;
};

template <typename T, typename U>
using Contains = std::bool_constant<requires { &T::MT::operator U; }>;

template <typename ...T> struct TypeList {
  using MT = MembershipTester<T...>;
};
```

The idea is that `MembershipTester<T...>::operator U` is ambiguous if `U` is not in `T...` and is valid otherwise.

With Clang, this ends up still being O(NK), because [name lookup for a conversion function does an unnecessary linear scan through all conversion functions declared in the class](https://github.com/llvm/llvm-project/blob/c8b40867d144395ad3c306a3cf87f970e0f97f07/clang/lib/Sema/SemaLookup.cpp#L1162).

Suggestion: When building the class's list of conversions, reorder the conversions to put all the template conversions before all the non-template conversions. Then terminate this loop in name lookup when we reach a non-template conversion.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJykVU2P4jgQ_TXmUprI2CSBA4cGBq00H3sYRnNcOU4l8a5jZ1xOt9hfv3ICTQsxrV2tZIkQV71677nKUUSmdYhblu9YflioMXY-bP8-t956Uy8qX5-3v2FAJkoCBRF158zPEaHxAWpvXAufoMe-wgDW-7_GgcC4FHkeEKyhCL6Br4AWe3Rx2vydifVXJnafmNhAND0CE2vnI0LsVITeU7wVIgj4czQB57TXHCY2TD4xPq2Cz0szsUuLP0XsB6siApP7RMWpHiHLshOTHxl_ohhGHeF0HvCzocjkbka6vP8yCaLODCekiGGnCJ-AlSkKrtBvkRMs-AGDij7AiYn1xG9CLQ_zwzvYu_-L_e_k3pcGJp8ea2Vi_z5RGCmd_eNkmdaNcZZld3R_xfiU6r7--z6TnyvtvYvKOAImD0CxnotU3ts_tHcUlYtM7i-9QokmMFGc5rAvpztO35lMUg6pwruMLh7CXcPc23CaaN27weR-Fv_xXv-1YefKpw7B1KjA0DwCrODvYd1JKXhKVH1l2tGPBKZJANf3zsc0dKzgU37BQbk6bTwra2rwscPwYgizmcsPEzvYW-Xa6Sw6Q4CuJhgHoGishQqT4tdhTFEVajUSAst3k2nzRTBdEQq0d88YyHgHzeh0TA-1RwLlYHQONRKpcAZrHKoApJWD2AU_th0oax_lE9SorQpYJ2WxQ9BWEbH8wMS6i3Gg5JE4MnFsTezGKtO-Z-Jo7fP158MQ_J-oIxPHyvqKiaNeVyu-Lsp6uVrJTa5qqSUvlNTNumw2JUfebMqGlyl0tudoTUr8hr26_HyehGd6GJiQn5fLQjCxuRj7bWxbpEQ_Td2PDh1Uo7F1cvMmIV2z11vzppySywF9qDHMwbctiB6GMU5epa3XNn4bU2HjA77GOO8-PIrL4JR4RQy9cWq6kA2l4xyS0W_P9iXFvSAEVLoD9SvEbFFvZb2RG7XA7bJc8VyKTVEsum2jS141fLmsaq3yap1XRS5QLBuUeYlSLsxWcJFzIQq-FGJVZPlqteZVKUVTVLoWK7bi2Ctjs3SemQ_twhCNuF2KdbnJF1ZVaGn6sAlxOTGRvnFhOzVANbbEVjyZTTeIaKKdvoZzRn542L8XEwy96WBjz0DWv8BLmqBeufPj1k3T5_xD2KuBtBiD3f7nRp7kExPHiwPPW_FPAAAA__-Z85XC">