njames93 created this revision.
njames93 added a reviewer: klimek.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
A simple optimization to avoid unnecessary copies of BoundNodesTreeBuilders
when querying the cache for memoized matchers.
This hasn't been benchmarked as I'm unsure how the memoized matchers were first
benchmarked so it shouldn't be merged unless there is a performance improvement.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D80202
Files:
clang/lib/ASTMatchers/ASTMatchFinder.cpp
Index: clang/lib/ASTMatchers/ASTMatchFinder.cpp
===================================================================
--- clang/lib/ASTMatchers/ASTMatchFinder.cpp
+++ clang/lib/ASTMatchers/ASTMatchFinder.cpp
@@ -68,6 +68,30 @@
}
};
+/// Performance optimization for querying the memoized map without the expensive
+/// copy of the \c BoundNodesTreeBuilder and to a lesser extent the \c
+/// DynTypedNode.
+struct MatchKeyRef {
+ const DynTypedMatcher::MatcherIDType MatcherID;
+ const DynTypedNode &Node;
+ const BoundNodesTreeBuilder &BoundNodes;
+ const TraversalKind Traversal;
+
+ MatchKey toKey() const {
+ return MatchKey{MatcherID, Node, BoundNodes, Traversal};
+ }
+};
+
+bool operator<(const MatchKey &LHS, const MatchKeyRef &RHS) {
+ return std::tie(LHS.Traversal, LHS.MatcherID, LHS.Node, LHS.BoundNodes) <
+ std::tie(RHS.Traversal, RHS.MatcherID, RHS.Node, RHS.BoundNodes);
+}
+
+bool operator<(const MatchKeyRef &LHS, const MatchKey &RHS) {
+ return std::tie(LHS.Traversal, LHS.MatcherID, LHS.Node, LHS.BoundNodes) <
+ std::tie(RHS.Traversal, RHS.MatcherID, RHS.Node, RHS.BoundNodes);
+}
+
// Used to store the result of a match and possibly bound nodes.
struct MemoizedMatchResult {
bool ResultOfMatch;
@@ -450,14 +474,11 @@
return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal,
Bind);
- MatchKey Key;
- Key.MatcherID = Matcher.getID();
- Key.Node = Node;
// Note that we key on the bindings *before* the match.
- Key.BoundNodes = *Builder;
- Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
+ MatchKeyRef KeyRef = {Matcher.getID(), Node, *Builder,
+ Ctx.getParentMapContext().getTraversalKind()};
- MemoizationMap::iterator I = ResultCache.find(Key);
+ MemoizationMap::iterator I = ResultCache.find(KeyRef);
if (I != ResultCache.end()) {
*Builder = I->second.Nodes;
return I->second.ResultOfMatch;
@@ -468,11 +489,10 @@
Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes,
MaxDepth, Traversal, Bind);
- MemoizedMatchResult &CachedResult = ResultCache[Key];
- CachedResult = std::move(Result);
-
- *Builder = CachedResult.Nodes;
- return CachedResult.ResultOfMatch;
+ auto Cached = ResultCache.emplace(KeyRef.toKey(), std::move(Result));
+ assert(Cached.second && "Emplace should succeed");
+ *Builder = Cached.first->second.Nodes;
+ return Cached.first->second.ResultOfMatch;
}
// Matches children or descendants of 'Node' with 'BaseMatcher'.
@@ -697,15 +717,13 @@
return matchesAncestorOfRecursively(Node, Ctx, Matcher, Builder,
MatchMode);
- MatchKey Key;
- Key.MatcherID = Matcher.getID();
- Key.Node = Node;
- Key.BoundNodes = *Builder;
- Key.Traversal = Ctx.getParentMapContext().getTraversalKind();
+ // Note that we key on the bindings *before* the match.
+ MatchKeyRef KeyRef = {Matcher.getID(), Node, *Builder,
+ Ctx.getParentMapContext().getTraversalKind()};
// Note that we cannot use insert and reuse the iterator, as recursive
// calls to match might invalidate the result cache iterators.
- MemoizationMap::iterator I = ResultCache.find(Key);
+ MemoizationMap::iterator I = ResultCache.find(KeyRef);
if (I != ResultCache.end()) {
*Builder = I->second.Nodes;
return I->second.ResultOfMatch;
@@ -716,11 +734,10 @@
Result.ResultOfMatch = matchesAncestorOfRecursively(
Node, Ctx, Matcher, &Result.Nodes, MatchMode);
- MemoizedMatchResult &CachedResult = ResultCache[Key];
- CachedResult = std::move(Result);
-
- *Builder = CachedResult.Nodes;
- return CachedResult.ResultOfMatch;
+ auto Cached = ResultCache.emplace(KeyRef.toKey(), std::move(Result));
+ assert(Cached.second && "Emplace should succeed");
+ *Builder = Cached.first->second.Nodes;
+ return Cached.first->second.ResultOfMatch;
}
bool matchesAncestorOfRecursively(const DynTypedNode &Node, ASTContext &Ctx,
@@ -869,7 +886,7 @@
CompatibleAliases;
// Maps (matcher, node) -> the match result for memoization.
- typedef std::map<MatchKey, MemoizedMatchResult> MemoizationMap;
+ typedef std::map<MatchKey, MemoizedMatchResult, std::less<>> MemoizationMap;
MemoizationMap ResultCache;
};
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
