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

    <tr>
        <th>Summary</th>
        <td>
            Fixing ParentMapContext.cpp to fix O(n^2) slowdown in hasParent() AST matchers
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          higher-performance
      </td>
    </tr>
</table>

<pre>
    AST matchers that reference parent nodes (e.g., `hasParent()`) can slow down **severely** (from O(seconds)/O(minutes) to O(hours)/timeouts) on large translation units, due to what appears to be a quadratic slowdown.

We have narrowed this down to the following lines, where it appears that the call to `llvm::is_contained(*Vector, ParentStack.back())` performs a linear search through a large vector, making parent lookups unusably slow.

https://github.com/llvm/llvm-project/blob/57b40b5f34383634949d1639e64a5c2acd0dc5f6/clang/lib/AST/ParentMapContext.cpp#L390-L398

Could this be fixed?

For what it's worth, at first glance, I thought that switching to binary search (and thus slowing down _insertions_ rather than lookups) would be a better trade-off that alleviates this concern, because insertions only happen once per element, whereas lookups can occur many times.

```
bool Found = ParentStack.back().getMemoizationData() && std::binary_search(Vector->begin(), Vector->end(), ParentStack.back());
if (!Found) {
  Vector->insert(std::upper_bound(Vector->begin(), Vector->end(), ParentStack.back()), ParentStack.back());
}
```

However, **I am unsure if this binary search would break**, due to the fact that `DynTypedNode` appears to lack comparability for some types (as written in the comment).
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJysVd9v2zYQ_mvol0MMmbRk-cEPblJhBdptQIvtMThRJ4kLRWokFcX76weSTuMOLbABAwIH4q_77rvvvkPv1WCITqx8x8qHDS5htO40qmEkdzeT662b0EjatLa7nM6fv8CEQY7kPIQRAzjqyZGRBDM6MgGM7cgD4zVthy3j98CqYkT_a9plvGb8yKqC8SNINOC1XaGzqwHGz4yfPT2TI33JX_GZ3tkJfmG89iSt6Xy8z5u4MCmzBIoLEGw6MtrFXQ8ENZFdQtq1BjS6gSA4NF5jUNbAYlTcvYduoXh_jdngPBPG1Cy0BAh_Ltg5DEomoBHnlhUPrDjn398JRnwmMOicXamDMCqf0wkWwkjQW63tqswAWhlK8daRHIG6CRYjx8MStY4XWVVo_TwxcWbirPyjtCagMtQl-s6_kQzWxacyqZ8Dyqdti_LpSm9iGK7F84ApNjrwhE6OEEZnl2GM64mV56_vTfgUoV4rqa19WmYPi1k8tvqSOPgm_zGE2UeYvGG8GVQYl3Yr7cR4kxLI_-5mZ_8gGRhvWm1bxpvy0O6LtuzFXtSiEvvj_tjtKnGkao-l5Ci7opNlXzHeSI1miA-pePH8-QvjTU77E8731gR6CVs5z4yLj-JY3H0Ux_oW4r1d9LUuLUGvXqhjork90ViXi68C4wcPq3VhjGxggF45H2DQsQPi0gcIY-Qu5KL5VQU5RsqiYJRBd3klmfEaTQy8-MRbPJSE8aiMJxcl6B_BYRjJxcfMK91RsGsCnRTYUgjxhMOO7mzf58CoNT0rDORzatIaSc5EiC1JXDzBWxiwRl9gjHIzYFOrkgPSNKWOvCoS_deCx8a0Ui4OJjQXiK3kv6l7bOD8lz5bazU0djEdMPHwA1VuBwqfaLLqr9R_DxgwbwDjFeMV-NBlxWciHzORjNdZ73dMvG9pUOZV5PfwtkGme1v-cVeIdxmw6iEt7hLohOFw3YKbVzOF0XpeoS3zTO6xzbf-R2D_CjU7PHyX_vz7k12jdybHTeb5AXCCxfgluk1_bYFvNHqVmSN8yldu7DCZF8qr0FlVPFzMl8tM3c-2o2gvN1apUT6BtNOMDlulVbhAbx14OxGEy5zHAXpYnQqBDCiT7c5OWYHH7aY7ie4ojrih0-6w25WHw4GXm_HUVkJQLfZCiF6Wou4r2dedrFspOJf7aqNOvOD7QvAD57uSl1sh-7rAspPHvez3tGP7giZUehutaGvdsFHeL3Sqq7rebTS2pH2afpwbWiFtMs7jMHSnZF_tMni2L7Tywb-9ElTQdGrUS-zs7zlSZKZXL2kwGVa-51Fnr2MkcvCPqQi3w3WzOH36z_aawHvGm5Tc3wEAAP__QGCJcg">