| Issue |
128795
|
| Summary |
[clang] conversion function lookup is unnecessarily slow with many conversion functions and no conversion function templates
|
| Labels |
clang
|
| Assignees |
|
| Reporter |
zygoloid
|
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.
![]()
_______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
