<table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Issue</th>
<td>
<a href=https://github.com/llvm/llvm-project/issues/106432>106432</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>
[clangd] [regression] n^2 runtime when processing code that builds a TypeList-like template
</td>
</tr>
<tr>
<th>Labels</th>
<td>
new issue
</td>
</tr>
<tr>
<th>Assignees</th>
<td>
</td>
</tr>
<tr>
<th>Reporter</th>
<td>
joelhock
</td>
</tr>
</table>
<pre>
clangd 19.1.0-rc3 (and main as of 14ff99) exhibits n^2 slowdown as more and more fields are added in the following code example. clangd version 18 did not; it could `--check` this code in less than 100 milliseconds.
```cpp
#define FOR_ALL_FIELDS(X) \
X(Field1) \
X(Field2) \
X(Field3) \
X(Field4) \
X(Field5) \
X(Field6) \
X(Field7) \
X(Field8) \
X(Field9) \
X(Field10) \
X(Field11) \
X(Field12) \
X(Field13) \
X(Field14) \
X(Field15) \
X(Field16) \
X(Field17) \
X(Field18) \
X(Field19) \
X(Field20) \
X(Field21) \
X(Field22) /* 3 seconds */ \
X(Field23) /* 7 seconds */ \
X(Field24) /* 14 seconds */ \
X(Field25) /* 28 seconds */ \
X(Field26) /* 56 seconds */
#define X(FieldT) class FieldT;
FOR_ALL_FIELDS(X)
#undef X
template <typename... Ts> struct TypeList {
template <typename T> using add = TypeList<Ts..., T>;
};
using MyFields = TypeList<>
#define X(FieldT) ::add<FieldT>
FOR_ALL_FIELDS(X)
#undef X
;
```
running `clangd --check` on this code:
```
$ time clangd.linux --check=slow.cpp
I[13:24:00.685] clangd version 19.1.0-rc3 (https://github.com/llvm/llvm-project.git 437434df21d839becb453f6821564662e9824f02)
I[13:24:00.686] Features: linux+grpc
I[13:24:00.686] PID: 106865
I[13:24:00.686] Working directory: /tmp
I[13:24:00.686] argv[0]: clangd.linux
I[13:24:00.686] argv[1]: --check=slow.cpp
I[13:24:00.686] Entering check mode (no LSP server)
I[13:24:00.686] Testing on source file /tmp/slow.cpp
I[13:24:00.686] Loading compilation database...
I[13:24:00.689] Failed to find compilation database for /tmp/slow.cpp
I[13:24:00.689] Generic fallback command is: [/tmp] /usr/bin/clang -resource-dir=lib/clang/19 -- /tmp/slow.cpp
I[13:24:00.690] Parsing command...
I[13:24:00.691] internal (cc1) args are: -cc1 -triple x86_64-unknown-linux-gnu -fsyntax-only -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name slow.cpp -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/tmp -fcoverage-compilation-dir=/tmp -resource-dir lib/clang/19 -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/13/../../../../include/c++/13 -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/13/../../../../include/x86_64-linux-gnu/c++/13 -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/13/../../../../include/c++/13/backward -internal-isystem lib/clang/19/include -internal-isystem /usr/local/include -internal-isystem /usr/bin/../lib/gcc/x86_64-linux-gnu/13/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fdeprecated-macro -ferror-limit 19 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -fcxx-exceptions -fexceptions -no-round-trip-args -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -x c++ /tmp/slow.cpp
I[13:24:00.691] Building preamble...
I[13:24:00.698] Built preamble of size 240672 for file /tmp/slow.cpp version null in 0.01 seconds
I[13:24:00.698] Indexing headers...
I[13:24:00.699] Building AST...
I[13:24:19.097] Indexing AST...
I[13:24:20.084] Building inlay hints
I[13:24:21.062] Building semantic highlighting
I[13:24:22.991] Testing features at each token (may be slow in large files)
I[13:24:22.993] Found definition heuristically in index for Field1
I[13:24:22.993] Found definition heuristically in index for Field1
I[13:24:22.993] Found definition heuristically in index for Field2
I[13:24:22.993] Found definition heuristically in index for Field2
I[13:24:22.993] Found definition heuristically in index for Field3
I[13:24:22.993] Found definition heuristically in index for Field3
... snip ...
I[13:24:22.998] Found definition heuristically in index for Field26
I[13:24:22.998] Found definition heuristically in index for Field26
I[13:24:55.764] Found definition heuristically in index for add
I[13:24:55.765] Found definition heuristically in index for add
I[13:24:57.736] All checks completed, 0 errors
real 0m57.085s
user 0m56.632s
```
two parts of processing the code are slow:
- `Building AST...` takes about 30% of the time; perf reports:
```
10.17% libc-2.31.so [.] malloc
9.75% libc-2.31.so [.] _int_free
6.54% clangd.linux [.] std::_Rb_tree<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, clang::DynTypedNode>, std::_Select1st<std::pair<s
5.58% clangd.linux [.] std::_Rb_tree<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const, clang::DynTypedNode>, std::_Select1st<std::pair<s
4.82% clangd.linux [.] clang::ast_matchers::internal::DynTypedMatcher::matches
4.78% clangd.linux [.] clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::MatchVisitor::visitMatch
4.11% clangd.linux [.] clang::ast_matchers::internal::(anonymous namespace)::MatchASTVisitor::match<clang::NestedNameSpecifier>
```
- `Found definition heuristically in index for add` takes about 60% of the time; perf reports:
```
39.59% clangd.linux [.] clang::RecursiveASTVisitor<(anonymous namespace)::TypeIndexer>::TraverseType
16.66% clangd.linux [.] clang::RecursiveASTVisitor<(anonymous namespace)::TypeIndexer>::TraverseNestedNameSpecifier
11.89% clangd.linux [.] clang::RecursiveASTVisitor<(anonymous namespace)::TypeIndexer>::TraverseTemplateSpecializationType
9.12% clangd.linux [.] clang::RecursiveASTVisitor<(anonymous namespace)::TypeIndexer>::TraverseType
4.69% clangd.linux [.] clang::RecursiveASTVisitor<(anonymous namespace)::TypeIndexer>::TraverseTemplateArgument
2.34% clangd.linux [.] clang::RecursiveASTVisitor<(anonymous namespace)::TypeIndexer>::TraverseElaboratedType
2.29% clangd.linux [.] clang::RecursiveASTVisitor<(anonymous namespace)::TypeIndexer>::TraverseNestedNameSpecifier
0.95% libc-2.31.so [.] _int_free
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsWk9v4zbT_zTMZUBBoixZPuTgxHHfBbZ9i03Q9mbQ1MhmQ5ECSSVxP_0DUrZjZ213U-yz6eFZBF6LnBkOfzOcP5S5c3KlEa9JcUOK2RXv_drY6z8NqrURj1dLU2-uheJ6VUM2SbIkpVbkQFjFdQ0tlxq4A9NANmqayYSwCeDLWi6ld6BJccfAKfNcm-dI1xqLEBnDl0aiqh3wMFbXWIPU4NcIjVHKPEu9AmFqBHzhbacwAdjq8YTWSaMhq6CWNWjjSX4D0oMwvaqBlCmlYo3ikZQp-LV0gxypQaFz4NdcQ5am0EqlpENhdO0Sks5IOt1-lunwJ7puO8LyGhupEeb__2Ux_fx5Mf9093l2T1j1R9gzKW4HQgCAPwir5mFv2fkpdn4qP57aj4_OsxTnp8rzU-PzU9X5qcmF_aYX5i6AkV1AIzsHR3YBj-wCINkFRLILkGQXMMkugMIugMIuecgACpsTNoUctn4KQNiUsDm8898JAFl-sMD4qwXOaDU6YMpGe67LTMUBE6u-kak8YCrKN0xHx3V_OPfMD4FXKO4cbJ_zm4H45Pndy-l1jQ38cSjdY9sp7hFIfus3HWreYpIk8OBIfgfO2154eNh0-Fk6D2R887qXU6zwENh6F8Ibr2sg-WzPTfLbB5ckCWG3kWyvNBnPXr_Hz0HAz5v5EEPfSAm8F6Eh-ZTkU17XJL_dAXT3qnj49w6g4FW5XeQcHm2vddAzhNIhdh9EZqNfg3PQ55QAwkbgZYvb0J8oqfuXvZB8FpJLso_Sn0hxk-Ukn7IRyadpmpRVQYrZV3njKI-tve9cWD942nwl_bpfJsK0hM2Vetr9Rztr_kThk5X0MMrHo3xUNyyrq3yyRLEcFXlTViwrylFZMpxUbNSkbA_YCcXKoNgcue8thuUhbo2wm5XtxGWuXz_NAkOWllVZXCb93djHYIBaWhTe2E1gJGzu2_OQRUZuV0-kuElJEdc6hP-bGLMt4ztMFdnvtEcbU39ggzYkbsIqbeDz_a_g0D6h_VtYH9D5IMNocKa3IpQaCnf7ZvNvU-Wz4fVQhLSdVNwH16m550vuQgA4yzyJluVSYQ3eQCN1fVIGNMa-Q6co9ifUaKWAhiu15OIxCG5DQSWjD4UibhBYzILo3lnC5kupCZtHEwK1OEBCa2lJPlNyuZsjbJ5NgNJv12mSRnfk1m1xCqpcgGYSvAJkMLHmKthViJgBuV3FOjB6jBAZUG9lpxBeqnJRjmivH7V51jT6H13pHmjjNtrzF2q02gCtpeNLhbSxiECFQm4pd54usTEWaYAKdf1KF4_0E1rZSLRxWHBb0yeueqQhTDugobilwXHiAOzAANpaVEZEY9LgoAo6KYB2UlCFT6iADQ_S0U4i0LaxvEXambhzks-4UkCblvs1RWu1Ado0HRVGe8uFJ_nMaKCNNtSaXgcfpIEWaCuMHhKOsZQryV3Qs-n1s9Q19WFnjuQzBtRzu0JPRdcHCGk5Aup7jXFgtfUhWuOyX63QhimpVySfreol0CaO0wOX3frK4BdAG2Ge0PIVXqA5dDP42sl2PkCl2ziP7VtnDTlwPrCthCBsvnWEvQMEOfmO8M2H1EL1NYYlCbuJf_Ms_2GLnuD6ED0OFw2yuXh85rY-sf5b-7yKuaRsOAPq20i_w75O0H69ML6EL-JrBc5b5zL3-5eI56ezKLjHmrZc2HC80VpjqZKt9BD8v1npXtBtQULy2ShhSRaC2qPsqKntkDWp1HTVNuHEvbxQfBHYhaMWzvzhwy5QxKBJYyylDa9r6-QK6Gyx-On2dvF_09_uFrPfp1_mbHE7_7SY3v9M8lkG9AW2jvKOuB_j-E0vVUyQnUXeLtWlpDipdhx-Tw6mASf_QmCjtByzmA5P5-l95aZ7pUIfnyZptmsILi_5Sdf4EpRcI6_Ruks6To52Nb1_OEOcTZJ0Mj6Sfp6YpUlajY4kS634BtZS-5PKsyxJS3bE4bDl2ksBa7laK7lah_LmJC9LJoN1djVQsy0xgXtALtbgzSPqkHtbvoHlkNfi3UhIGdEA7kyBFYXnsboJ7gaxs5Cxplljb6XzUnClNkGaDMhEk25vQv7d8ti_XF7-35EX-linZQfnnDesUP0zBMofIrAoknE5eq_A0PieE1Z8L2HjZJzHRmKq1NDOuNgHKPRYhxY_hZgW3GFfb5ErSNtinKRV4Xa9PtrQkadtUSZlztzJVtk_G-i49fE2trNGoItluV_jcP_J7XDY97020NCYvw14ZQqeP4aAsTS9hzwlrAgig5zQipP8Bjq0DVjsjPXuXOsOkKVJNg7cocAQlCV5ljhzcCV1kwR4Wq6UEfvLh0kyLgLTRZ6F1H4Riv09W5kUo7jW0U3BWz7n6-HqY_FlufCBP799HVuIl5csGx6W3EmxcN7GyvhWrLkNNtsTh4GFt1wGBIbp_O6IIm6Le2Nf5-EtTcdD1fyjVYDYRwTKoeaLtLONfth0WP8Sr2OO5SzuUaHwWbxc-kr5vQ2KpKj-Z4OPtcEoqdjf2-BgTe78ouVerNG6YWRX6x7r9PNAMwwODIerjqPlv9ei8f2S0ZvW9A5iP95xgaEuidNRl-n9w2_SyYjsfvBo5Ck8xOEDRbPsoxWN8oI3vC7zCzqP9S-8xfsORbyVeL3DPY6rMWi_Nz-9CerlPw_q-SQpJu9ysC8oeuvkEx7icPs3wAWXi9X1AMQwZnloBDDM7XNMmZTlx6pzynY77bKkmrzH3b4_VttXEFE1ruRf8bLmEEGYJBn7WB0PtRkl5Ue71xayqV31LWq_V40l-YkS40eodKf40ljusT7CiiXsBFYf7POQJpN3F3D7MHNVX-f1JJ_wK7zOxmxUjdO8mFytr8dlkbFxuRyzbJzXTVVVo3xZY9oU6ZLnVX0lr1nKRmnFqqzKJ9kkaXImRNawmjUVH-cVGaXYcqkSpZ7axNjVlXSux-ssLUc5u1J8icrF30EwpvEZ4ixhoRO_stfxxnjZrxwZpUo6717FeOlV_AHFYIZ4917cWFzZUIIbHQaG30LYXse3Wc9r1Ic1eqzP_Zp7WIZq3AHfv82jSj7i_k3iVW_V9fveWBE2jztxhM23W326Zv8JAAD__4VPDdU">