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

    <tr>
        <th>Summary</th>
        <td>
            Quadratic compile times with pack indexing that can be avoided
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

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

    <tr>
      <th>Reporter</th>
      <td>
          ilya-biryukov
      </td>
    </tr>
</table>

<pre>
    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?
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy8V1-P4jry_TTulxKR44QQHnigadCv9bt3rnanVztvLccpiLcTO9d2oJlPvyoHuoGeGakfdhBSIHb9OadOnCrpvd4ZxAWb3rPpw50cQmPdQrdHOam0Ow4vdn9X2fq4-IoITQi9Z9mSiQ0Tm51Syc7WlW1DYt2Oic13JjY15t5VqGbA-HLVSrMDJkoZoEFZgzQ1OGxReqxhj85razwTczjotoUgXxD-HmTtZNAKgu4QggVlu163CKFBULZGqLC1hwTWyS6JN7e2be1Bmx1UqJpOuhdQLUrXHsE39uDjpuDQ1JQ8X7KCn758yUQOzbFHt9UGYfIHGGBCpJxzJlZivOTjpYwXAcDELGFiU2nDxEYRRibumbiHiQ81yx7U-FcUMNn6ownydWJNe4RWuh0-42svTQSeKAWTh_Uf6z_XX56-Pj_99bz6v_Xq_1n2wGb3hs0emJgxvrxHc0KVsmwJ_-PQETpfAjwR_UyUHUoDbCXYfQpstWFlxsScEqFPNs-TEjp_3gDpLMnpPwCw6f2_PDrammVpkkLnmVjB16MP2NHdIkumdHP6EAP-U5rdGFEbYGvBSs6WBXTy9S1gVpzcvy_naRG9UMSUgxuMp7Je0iZ-A23iU7RBmqQlh3faeMJFDre0pQnP53DDGk_SLIXPsEbRMgGXrEGaCJHCr1jLfgNr-edYyxNRllespdPiA2tZUqY_YC0vys-xlicpn1-zlidFlv2Stfw3sFZ-irW0SHghrljLU_5Ra9OE5-UtbWnC08-JLZ0m0-KatnSW8Gz2gbbLU5gvV7bGm-NZ9X08oTNtVDvUCCxbDUG3OhxZth7NAnZ9K0NcU630PkkSeBqXfXCDCvB07NEDm91HCACXJtoESJLkcTSg1bMRvYvebegzeHrFhGNPlg-jW5atnpIkYdP7RzZ9oF_ZmmVnKzrC45_3H9cZU_jHq2S_xaDn7R_Q3UD7U77gN_9xrzaBeHj84eZV1OGSZUttAu7QPXv8e0CjcLQkBTyeoawvSPgJAd9YtqJIl-h_BfjLVVarBtXLDdtjoG8-hvmYdidf8PnnuX8ZEx_3UrZvmYz1jc2FssYHfO0dUEqKkmCipFbkuuhjY3RDqSg_QeEHl-9ZPEvv0YUrf_7Zyw6f9yxbUe5Gdgjf_AnMmUnii1g_U_6GVKxuAv3y87MKruPTfEUDNSPlpyoQ2XxzdOHLYRicoWbm8jm51swtPylJgdTwJheWrX5wNp64uKjnewbX581OKfCInacWcysdQjeoBioMAR2BqIYAj1BbMDZAI_cIEsgonZ47V7AGuiN0UjXUPMZW1Wy160AH0B6kCoNs6WjXBqWDvSc_JG3fybZFN6pQmgBbqYJ1PmF8-Uj9rcY9wtg-a3_RE1eo5OCRAvTOKsTag_SnDtjDoUEDevSpZaBQrOA3J1TBx3N2AlvrAKVqaNPjyMwElEOSmIRW-wB2C36ofNBhCPRWAmWdQ99bU8fDwL4FKPiovgn0Wr2AnoQGsMUOCZ6zXezCySeBfIq9fNe3-KrDkTCeONIm7vP6O1Jscs4Know1IyvCVktXU4kae8D9WK3dIJ00AZG6fRnOhiDbgzx6cLhFF0stoZekjRV4CwekCWFoa6gQZNXGIn5Mn152Bf-LdEhyikihky-RgQYBXyVBAVnZPQINE9Z1pI6TlRmtwMnQoKMEL5amazEuj7xoD7rrnd2PoUeJHqwLzaGhKUj6CAC0qfFVj_po9Qu2R8q9QhhotiIaT4fFpMMge2d3TnadNrtJg3J_JOkFfA0-zmTvPOBrjyqA151upTsji8z1toehP1fooNv6VBaW805_3-OL3QPLubIuM0EbkOYIobHDrgmeZRv4d4ygwynL7dBGt84GG18qkn7b7cRuJ8oahX0Ya_k-xJ1GwUkcDXd2zOusnC3BiA9qtJLeD11PomXZ5q5eZPU8m8s7XKSz6ZTPy7yc3zWLWYrVvCrTtJb1tihLJYsZ58VcCVUW22p2pxeCiykv0yydilTME57xSqXbcopyhnJbsJxjJ3WbtO2-o0n4Tns_4CKdZnmW3rWywtbHAVsIgweIq0wImrfdgowm1bDzLOf0cPh3N0GHFhf_eHv23-Zg3aGHgw7NjRIibCVNFPPe6hrru8G1i5u5XYdmqBJlOyY2FOx0mfTO_gdVYGITU_RMbE4Y9gvx3wAAAP__z7LIcQ">