| Issue |
153431
|
| Summary |
Quadratic compile times with pack indexing that can be avoided
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
ilya-biryukov
|
See https://gcc.godbolt.org/z/de4srbec7
Clang (at head and released versions) will take quadratic time to compile the code below. E.g. the following bechmark clearly shows the trend:
```
$ hyperfine -L n "1000,2000,4000,8000" './bin/clang++ -std=c++26 -fsyntax-only large_expansions.cc -DELEMENTS_TO_CHECK={n}'
Benchmark 1: ./bin/clang++ -std=c++26 -fsyntax-only large_expansions.cc -DELEMENTS_TO_CHECK=1000
Time (mean ± σ): 394.8 ms ± 17.4 ms [User: 331.1 ms, System: 63.5 ms]
Range (min … max): 367.4 ms … 416.5 ms 10 runs
Benchmark 2: ./bin/clang++ -std=c++26 -fsyntax-only large_expansions.cc -DELEMENTS_TO_CHECK=2000
Time (mean ± σ): 1.180 s ± 0.024 s [User: 1.049 s, System: 0.131 s]
Range (min … max): 1.132 s … 1.221 s 10 runs
Benchmark 3: ./bin/clang++ -std=c++26 -fsyntax-only large_expansions.cc -DELEMENTS_TO_CHECK=4000
Time (mean ± σ): 4.288 s ± 0.156 s [User: 3.819 s, System: 0.468 s]
Range (min … max): 4.109 s … 4.633 s 10 runs
Benchmark 4: ./bin/clang++ -std=c++26 -fsyntax-only large_expansions.cc -DELEMENTS_TO_CHECK=8000
Time (mean ± σ): 16.062 s ± 0.410 s [User: 15.048 s, System: 1.011 s]
Range (min … max): 15.569 s … 17.037 s 10 runs
```
Code:
```cpp
#include <utility>
template <class... T>
struct Types {
template <int ...I>
struct Take {
using type = Types<T...[I]...>;
};
};
template <int I>
struct X {};
template <class T>
struct MakeXs;
template <int... I>
struct MakeXs<std::integer_sequence<int, I...>> {
using type = Types<X<I>...>;
};
template <int N>
struct CheckTake {
using Xs = MakeXs<std::make_integer_sequence<int, N>>::type;
static constexpr int check() {
[]<int... I>(std::integer_sequence<int, I...>) {
static_assert(std::is_same_v<typename Xs::template Take<I...>::type,
Types<X<I>...>>);
}(std::make_integer_sequence<int, N>());
return 1;
}
};
static_assert(1 == CheckTake<ELEMENTS_TO_CHECK>::check());
```
gcc seems to fare much better, but I do not have a gcc 15 version on my machine to confirm it is actually linear vs having smaller constant factors.
I believe Clang is quadratic because it proceeds as follows when instantiating `T...[I]...`:
- for each `I`
- create a list of substitutions corresponding to `T...`,
- pick i-th element from the list.
The complexity is linear in the size of `T`.
The standard, however, guarantees that `T` always refers to a pack, so we should be able to pick i-th element in `O(1)`, making the example above perform on `O(n)` rather than `O(n^2)`.
This improvement seems worthwhile as pack indexing is likely to be used in template-metaprogramming-heavy contexts and we should expect similar examples to pop up in the wild.
@mizvekov @cor3ntin any thoughts? Would it be useful to prototype a proof-of-concept that shows the compile-time goes to linear if we have that assumption?
![]()
_______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
