TLDR;
I propose the new __type_list_dedup builtin that removes duplicates from a list of types passed to it in an efficient manner. It saves a significant fraction of compile time in certain cases, which is the main motivation for it.
The draft pull request: [Clang] Add __type_list_dedup builtin to deduplicate types in templat… by ilya-biryukov · Pull Request #106730 · llvm/llvm-project · GitHub
Motivating example
We have been looking through the -ftime-trace profiles of our code lately and have found a few places that use template metaprogramming to manipulate type lists and one particular operation stood up: removing duplicates from a list of types.
The code is something like this (see Compiler Explorer for a full example):
...
template <class TL> struct Dedup;
template <> struct Dedup<TypeList<>> {
using result = TypeList<>;
};
template <class T> struct Dedup<TypeList<T>> {
using result = TypeList<T>;
};
template <class T, class ...Ts> struct Dedup<TypeList<T, Ts...>> {
using tail = Dedup<TypeList<Ts...>>::result;
using result = If<Contains<tail, T>::result,
tail,
typename Prepend<tail, T>::result>::result;
};
This particular implementation requires O(N^2) template instantiations to deduplicate a list of N types, so the compile-time performance is abysmall for longer lists. A more sophisticated implementation is possible that relies on constexpr and std::sort, which is O(N * log N), but the constant factor is so high that on one of the particularly demanding files, we still end up spending 25% out of 3 minutes it takes to compile this file this list deduplication.
Proposal
In order to improve compile time in those situations and simplify writing this code, I propose to add a builtin template __type_list_dedup that deduplicates the types in the list in the compiler by using a hash map:
static_assert(__is_same(
__type_list_dedup<TypeList, int, int, double, int>,
TypeList<int, double>))
The concept of builtin templates is not new in Clang, the implementation is similar to the already existing __make_integer_seq and __type_pack_element .
I’ve implemented this builtin and measured that performance impact of list deduplication goes away almost entirely in the aforementioned example and reduce the compile time by 25% out of those 3 minutes.
The implementation creates a builtin template declaration with the following signature:
template <template<class...> class Template, class ...Types>
using __type_dedup_list = /*<builtin>*/;
and can be used with any templates or template aliases:
__type_dedup_list<std::tuple, int, int, double> x;
// same as std::tuple<int, double>
template <class ...Types> struct TypeList;
__type_dedup_list<TypeList, int, int, double> y;
// same as TypeList<int, double>
template <class ...Types>
using PairedWithInt = TypeList<std::pair<int, Types>...>;
__type_dedup_list<PairedWithInt, int, int, double> t;
// same as TypeList<pair<int, int>, pair<int, double>>
If any of the template arguments are dependent, the instantiation is postponed, similarly to __make_integer_seq and __type_pack_element.
Alternative considered: type trait
Another possibility would be to introduce a type trait that reinstiates the class passed to it:
template <class ...Types>
struct TypeList;
__dedup(TypeList<int, int, double>) x; //same as TypeList<int, double>.
The cons is that the implementation would be more complicated and require custom type checking:
__dedup(int) // not allowed, needs to be diagnosed.
and the semantics of type aliases is either unclear or even confusing:
template <class ...Types> using Twice = TypeList<Types..., Types...>;
__dedup(Twice<int, double, int>);
// easy to expect
// Twice<int, double> == TypeList<int, double, int double>;
// but type aliases must be expanded right away, so should be equivalent to
// __dedup(TypeList<int, double, int, int, double, int>)
// == TypeList<int, double>.
The pro was that it would be a little more ergonomic in some cases.
I don’t have strong feelings about the name and happy to explore other alternatives. I actually agree 