[clang] Reduce memory usage in AST parent map generation by partially reverting quadratic slowdown mitigation (PR #129934)
https://github.com/higher-performance edited https://github.com/llvm/llvm-project/pull/129934 ___ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] Reduce memory usage in AST parent map generation by partially reverting quadratic slowdown mitigation (PR #129934)
https://github.com/higher-performance updated
https://github.com/llvm/llvm-project/pull/129934
>From 9f12c5856691268177e748d2a98de24ee30bdfd1 Mon Sep 17 00:00:00 2001
From: higher-performance
Date: Wed, 5 Mar 2025 15:49:06 -0500
Subject: [PATCH] Reduce memory usage in AST parent map generation by lazily
checking if nodes have been seen
---
clang/lib/AST/ParentMapContext.cpp | 50 --
1 file changed, 47 insertions(+), 3 deletions(-)
diff --git a/clang/lib/AST/ParentMapContext.cpp
b/clang/lib/AST/ParentMapContext.cpp
index e9387ec79c373..b7156b892b01a 100644
--- a/clang/lib/AST/ParentMapContext.cpp
+++ b/clang/lib/AST/ParentMapContext.cpp
@@ -60,6 +60,29 @@ class ParentMapContext::ParentMap {
template friend struct ::MatchParents;
+ template struct IndirectDenseMapInfo {
+using Ptr = T *;
+using Base = llvm::DenseMapInfo>;
+static inline Ptr getEmptyKey() {
+ return static_cast(llvm::DenseMapInfo::getEmptyKey());
+}
+static inline Ptr getTombstoneKey() {
+ return static_cast(llvm::DenseMapInfo::getTombstoneKey());
+}
+static unsigned getHashValue(Ptr Val) {
+ return Val == getEmptyKey() || Val == getTombstoneKey()
+ ? 0
+ : Base::getHashValue(*Val);
+}
+static bool isEqual(Ptr LHS, Ptr RHS) {
+ if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
+ RHS == getEmptyKey() || RHS == getTombstoneKey()) {
+return LHS == RHS;
+ }
+ return Base::isEqual(*LHS, *RHS);
+}
+ };
+
/// Contains parents of a node.
class ParentVector {
public:
@@ -70,16 +93,37 @@ class ParentMapContext::ParentMap {
push_back(Value);
}
bool contains(const DynTypedNode &Value) {
- return Seen.contains(Value);
+ assert(Value.getMemoizationData());
+ bool found = FragileLazySeenCache.contains(&Value);
+ while (!found && ItemsProcessed < Items.size()) {
+found |= FragileLazySeenCache.insert(&Items[ItemsProcessed]).second;
+++ItemsProcessed;
+ }
+ return found;
}
void push_back(const DynTypedNode &Value) {
- if (!Value.getMemoizationData() || Seen.insert(Value).second)
+ if (!Value.getMemoizationData() || !contains(Value)) {
+const size_t OldCapacity = Items.capacity();
Items.push_back(Value);
+if (OldCapacity != Items.capacity()) {
+ // Pointers are invalidated; remove them.
+ ItemsProcessed = 0;
+ // Free memory to avoid doubling peak memory usage during rehashing
+ FragileLazySeenCache.clear();
+}
+ }
}
llvm::ArrayRef view() const { return Items; }
private:
+// BE CAREFUL. Pointers into this container are stored in the cache.
llvm::SmallVector Items;
-llvm::SmallDenseSet Seen;
+// This cache is fragile because it contains pointers that are invalidated
+// when the vector capacity changes.
+llvm::SmallDenseSet>
+FragileLazySeenCache;
+// Lazily tracks which items have been processed for the cache.
+size_t ItemsProcessed = 0;
};
/// Maps from a node to its parents. This is used for nodes that have
___
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] Reduce memory usage in AST parent map generation by partially reverting quadratic slowdown mitigation (PR #129934)
https://github.com/higher-performance edited https://github.com/llvm/llvm-project/pull/129934 ___ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] Reduce memory usage in AST parent map generation by partially reverting quadratic slowdown mitigation (PR #129934)
https://github.com/higher-performance ready_for_review https://github.com/llvm/llvm-project/pull/129934 ___ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] Reduce memory usage in AST parent map generation by partially reverting quadratic slowdown mitigation (PR #129934)
https://github.com/higher-performance edited https://github.com/llvm/llvm-project/pull/129934 ___ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] Reduce memory usage in AST parent map generation by partially reverting quadratic slowdown mitigation (PR #129934)
https://github.com/higher-performance updated
https://github.com/llvm/llvm-project/pull/129934
>From e99bb267a950f75ea4fc23454762a7422c776bca Mon Sep 17 00:00:00 2001
From: higher-performance
Date: Wed, 5 Mar 2025 15:49:06 -0500
Subject: [PATCH] Reduce memory usage in AST parent map generation by partially
reverting quadratic slowdown mitigation
The use of parent maps (hasParent(), hasAncestor(), etc.) in Clang AST matchers
is no longer guaranteed to avoid quadratic slowdown, but will only do so in
pathological cases.
---
clang/lib/AST/ParentMapContext.cpp | 50 --
1 file changed, 47 insertions(+), 3 deletions(-)
diff --git a/clang/lib/AST/ParentMapContext.cpp
b/clang/lib/AST/ParentMapContext.cpp
index e9387ec79c373..b7156b892b01a 100644
--- a/clang/lib/AST/ParentMapContext.cpp
+++ b/clang/lib/AST/ParentMapContext.cpp
@@ -60,6 +60,29 @@ class ParentMapContext::ParentMap {
template friend struct ::MatchParents;
+ template struct IndirectDenseMapInfo {
+using Ptr = T *;
+using Base = llvm::DenseMapInfo>;
+static inline Ptr getEmptyKey() {
+ return static_cast(llvm::DenseMapInfo::getEmptyKey());
+}
+static inline Ptr getTombstoneKey() {
+ return static_cast(llvm::DenseMapInfo::getTombstoneKey());
+}
+static unsigned getHashValue(Ptr Val) {
+ return Val == getEmptyKey() || Val == getTombstoneKey()
+ ? 0
+ : Base::getHashValue(*Val);
+}
+static bool isEqual(Ptr LHS, Ptr RHS) {
+ if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
+ RHS == getEmptyKey() || RHS == getTombstoneKey()) {
+return LHS == RHS;
+ }
+ return Base::isEqual(*LHS, *RHS);
+}
+ };
+
/// Contains parents of a node.
class ParentVector {
public:
@@ -70,16 +93,37 @@ class ParentMapContext::ParentMap {
push_back(Value);
}
bool contains(const DynTypedNode &Value) {
- return Seen.contains(Value);
+ assert(Value.getMemoizationData());
+ bool found = FragileLazySeenCache.contains(&Value);
+ while (!found && ItemsProcessed < Items.size()) {
+found |= FragileLazySeenCache.insert(&Items[ItemsProcessed]).second;
+++ItemsProcessed;
+ }
+ return found;
}
void push_back(const DynTypedNode &Value) {
- if (!Value.getMemoizationData() || Seen.insert(Value).second)
+ if (!Value.getMemoizationData() || !contains(Value)) {
+const size_t OldCapacity = Items.capacity();
Items.push_back(Value);
+if (OldCapacity != Items.capacity()) {
+ // Pointers are invalidated; remove them.
+ ItemsProcessed = 0;
+ // Free memory to avoid doubling peak memory usage during rehashing
+ FragileLazySeenCache.clear();
+}
+ }
}
llvm::ArrayRef view() const { return Items; }
private:
+// BE CAREFUL. Pointers into this container are stored in the cache.
llvm::SmallVector Items;
-llvm::SmallDenseSet Seen;
+// This cache is fragile because it contains pointers that are invalidated
+// when the vector capacity changes.
+llvm::SmallDenseSet>
+FragileLazySeenCache;
+// Lazily tracks which items have been processed for the cache.
+size_t ItemsProcessed = 0;
};
/// Maps from a node to its parents. This is used for nodes that have
___
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] Reduce memory usage in AST parent map generation by partially reverting quadratic slowdown mitigation (PR #129934)
https://github.com/higher-performance edited https://github.com/llvm/llvm-project/pull/129934 ___ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] Reduce memory usage in AST parent map generation by partially reverting quadratic slowdown mitigation (PR #129934)
https://github.com/higher-performance converted_to_draft https://github.com/llvm/llvm-project/pull/129934 ___ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] Reduce memory usage in AST parent map generation by partially reverting quadratic slowdown mitigation (PR #129934)
llvmbot wrote:
@llvm/pr-subscribers-clang
Author: None (higher-performance)
Changes
This is a regression in #87824.
With this change, the use of parent maps (`hasParent()`, `hasAncestor()`, etc.)
in Clang AST matchers is no longer _guaranteed_ to avoid quadratic slowdown,
but in practice it should do so more frequently. I tested against a translation
unit that had been slow in the past, and it worked fine on that. If we hit
those pathological cases in the future, we can evaluate other approaches.
Fixes #129808
---
Full diff: https://github.com/llvm/llvm-project/pull/129934.diff
1 Files Affected:
- (modified) clang/lib/AST/ParentMapContext.cpp (+65-8)
``diff
diff --git a/clang/lib/AST/ParentMapContext.cpp
b/clang/lib/AST/ParentMapContext.cpp
index e9387ec79c373..03e5236eeb1db 100644
--- a/clang/lib/AST/ParentMapContext.cpp
+++ b/clang/lib/AST/ParentMapContext.cpp
@@ -65,21 +65,78 @@ class ParentMapContext::ParentMap {
public:
ParentVector() = default;
explicit ParentVector(size_t N, const DynTypedNode &Value) {
- Items.reserve(N);
+ SortedAndUnsortedItems.reserve(N);
for (; N > 0; --N)
push_back(Value);
}
bool contains(const DynTypedNode &Value) {
- return Seen.contains(Value);
+ const auto SortBoundary = SortedAndUnsortedItems.begin() + NumSorted;
+ bool Found = std::binary_search(SortedAndUnsortedItems.begin(),
+ SortBoundary, Value);
+ Budget += llvm::bit_width(
+ static_cast(SortBoundary - SortedAndUnsortedItems.begin()));
+ if (!Found) {
+auto FoundIt =
+std::find(SortBoundary, SortedAndUnsortedItems.end(), Value);
+Budget += FoundIt - SortBoundary;
+Found |= FoundIt != SortedAndUnsortedItems.end();
+ }
+ SortIfWorthwhile();
+ return Found;
}
void push_back(const DynTypedNode &Value) {
- if (!Value.getMemoizationData() || Seen.insert(Value).second)
-Items.push_back(Value);
+ ++Budget;
+ if (!Value.getMemoizationData() || !contains(Value)) {
+SortedAndUnsortedItems.push_back(Value);
+if (SortedAndUnsortedItems.back() < SortedAndUnsortedItems[NumSorted])
{
+ // Keep the minimum element in the middle to quickly tell us if
+ // merging will be necessary
+ using std::swap;
+ swap(SortedAndUnsortedItems.back(),
+ SortedAndUnsortedItems[NumSorted]);
+}
+ }
+ VerifyInvariant();
}
-llvm::ArrayRef view() const { return Items; }
+llvm::ArrayRef view() {
+ ++Budget;
+ return SortedAndUnsortedItems;
+}
+
private:
-llvm::SmallVector Items;
-llvm::SmallDenseSet Seen;
+void SortIfWorthwhile() {
+ VerifyInvariant();
+ auto SortBoundary = SortedAndUnsortedItems.begin() + NumSorted;
+ if (SortBoundary != SortedAndUnsortedItems.end()) {
+const size_t NumUnsorted = SortedAndUnsortedItems.end() - SortBoundary;
+const size_t SortingCost = NumUnsorted * llvm::bit_width(NumUnsorted);
+const bool NeedMerge = SortBoundary != SortedAndUnsortedItems.begin();
+// Assume that the naive implementation would copy these elements.
+// This is just an estimate; it's OK if it's wrong.
+const size_t MergeCost = SortedAndUnsortedItems.size() + NumUnsorted;
+if (Budget >= (NeedMerge ? MergeCost : 0) + SortingCost) {
+ std::sort(SortBoundary, SortedAndUnsortedItems.end());
+ if (NeedMerge) {
+std::inplace_merge(SortedAndUnsortedItems.begin(), SortBoundary,
+ SortedAndUnsortedItems.end());
+ }
+ Budget = 0;
+ NumSorted = SortedAndUnsortedItems.size();
+}
+ }
+}
+
+void VerifyInvariant() const {
+ assert(
+ !(NumSorted < SortedAndUnsortedItems.size() &&
+SortedAndUnsortedItems.back() <
+SortedAndUnsortedItems[NumSorted]) &&
+ "the boundary item must always be the minimum of the unsorted
items");
+}
+
+llvm::SmallVector SortedAndUnsortedItems;
+size_t NumSorted = 0;
+int64_t Budget = 0;
};
/// Maps from a node to its parents. This is used for nodes that have
@@ -117,7 +174,7 @@ class ParentMapContext::ParentMap {
if (I == Map.end()) {
return llvm::ArrayRef();
}
-if (const auto *V = dyn_cast(I->second)) {
+if (auto *V = dyn_cast(I->second)) {
return V->view();
}
return getSingleDynTypedNodeFromParentMap(I->second);
``
https://github.com/llvm/llvm-project/pull/129934
___
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] Reduce memory usage in AST parent map generation by partially reverting quadratic slowdown mitigation (PR #129934)
https://github.com/higher-performance created
https://github.com/llvm/llvm-project/pull/129934
This is a regression in #87824.
With this change, the use of parent maps (`hasParent()`, `hasAncestor()`, etc.)
in Clang AST matchers is no longer _guaranteed_ to avoid quadratic slowdown,
but in practice it should do so more frequently. I tested against a translation
unit that had been slow in the past, and it worked fine on that. If we hit
those pathological cases in the future, we can evaluate other approaches.
Fixes #129808
>From 0e3c685cabf0911f9be952aa95def7255baebb28 Mon Sep 17 00:00:00 2001
From: higher-performance
Date: Wed, 5 Mar 2025 15:49:06 -0500
Subject: [PATCH] Reduce memory usage in AST parent map generation by partially
reverting quadratic slowdown mitigation
The use of parent maps (hasParent(), hasAncestor(), etc.) in Clang AST matchers
is no longer guaranteed to avoid quadratic slowdown, but will only do so in
pathological cases.
---
clang/lib/AST/ParentMapContext.cpp | 73 ++
1 file changed, 65 insertions(+), 8 deletions(-)
diff --git a/clang/lib/AST/ParentMapContext.cpp
b/clang/lib/AST/ParentMapContext.cpp
index e9387ec79c373..03e5236eeb1db 100644
--- a/clang/lib/AST/ParentMapContext.cpp
+++ b/clang/lib/AST/ParentMapContext.cpp
@@ -65,21 +65,78 @@ class ParentMapContext::ParentMap {
public:
ParentVector() = default;
explicit ParentVector(size_t N, const DynTypedNode &Value) {
- Items.reserve(N);
+ SortedAndUnsortedItems.reserve(N);
for (; N > 0; --N)
push_back(Value);
}
bool contains(const DynTypedNode &Value) {
- return Seen.contains(Value);
+ const auto SortBoundary = SortedAndUnsortedItems.begin() + NumSorted;
+ bool Found = std::binary_search(SortedAndUnsortedItems.begin(),
+ SortBoundary, Value);
+ Budget += llvm::bit_width(
+ static_cast(SortBoundary - SortedAndUnsortedItems.begin()));
+ if (!Found) {
+auto FoundIt =
+std::find(SortBoundary, SortedAndUnsortedItems.end(), Value);
+Budget += FoundIt - SortBoundary;
+Found |= FoundIt != SortedAndUnsortedItems.end();
+ }
+ SortIfWorthwhile();
+ return Found;
}
void push_back(const DynTypedNode &Value) {
- if (!Value.getMemoizationData() || Seen.insert(Value).second)
-Items.push_back(Value);
+ ++Budget;
+ if (!Value.getMemoizationData() || !contains(Value)) {
+SortedAndUnsortedItems.push_back(Value);
+if (SortedAndUnsortedItems.back() < SortedAndUnsortedItems[NumSorted])
{
+ // Keep the minimum element in the middle to quickly tell us if
+ // merging will be necessary
+ using std::swap;
+ swap(SortedAndUnsortedItems.back(),
+ SortedAndUnsortedItems[NumSorted]);
+}
+ }
+ VerifyInvariant();
}
-llvm::ArrayRef view() const { return Items; }
+llvm::ArrayRef view() {
+ ++Budget;
+ return SortedAndUnsortedItems;
+}
+
private:
-llvm::SmallVector Items;
-llvm::SmallDenseSet Seen;
+void SortIfWorthwhile() {
+ VerifyInvariant();
+ auto SortBoundary = SortedAndUnsortedItems.begin() + NumSorted;
+ if (SortBoundary != SortedAndUnsortedItems.end()) {
+const size_t NumUnsorted = SortedAndUnsortedItems.end() - SortBoundary;
+const size_t SortingCost = NumUnsorted * llvm::bit_width(NumUnsorted);
+const bool NeedMerge = SortBoundary != SortedAndUnsortedItems.begin();
+// Assume that the naive implementation would copy these elements.
+// This is just an estimate; it's OK if it's wrong.
+const size_t MergeCost = SortedAndUnsortedItems.size() + NumUnsorted;
+if (Budget >= (NeedMerge ? MergeCost : 0) + SortingCost) {
+ std::sort(SortBoundary, SortedAndUnsortedItems.end());
+ if (NeedMerge) {
+std::inplace_merge(SortedAndUnsortedItems.begin(), SortBoundary,
+ SortedAndUnsortedItems.end());
+ }
+ Budget = 0;
+ NumSorted = SortedAndUnsortedItems.size();
+}
+ }
+}
+
+void VerifyInvariant() const {
+ assert(
+ !(NumSorted < SortedAndUnsortedItems.size() &&
+SortedAndUnsortedItems.back() <
+SortedAndUnsortedItems[NumSorted]) &&
+ "the boundary item must always be the minimum of the unsorted
items");
+}
+
+llvm::SmallVector SortedAndUnsortedItems;
+size_t NumSorted = 0;
+int64_t Budget = 0;
};
/// Maps from a node to its parents. This is used for nodes that have
@@ -117,7 +174,7 @@ class ParentMapContext::ParentMap {
if (I == Map.end()) {
return llvm::ArrayRef();
}
-if (const auto *V = dyn_cast(I->second)) {
+if (auto *V = dyn_cast(I->second)) {
return V->view();
}
return getSingleDynTypedNodeFromParentMap(I-
