| Issue |
86881
|
| Summary |
Fixing ParentMapContext.cpp to fix O(n^2) slowdown in hasParent() AST matchers
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
higher-performance
|
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).
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
