llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-llvm-support Author: Vitaly Buka (vitalybuka) <details> <summary>Changes</summary> This commit optimizes `SpecialCaseList` by using a `RadixTree` to filter glob patterns based on their prefixes. When matching a query, the `RadixTree` quickly identifies all glob patterns whose prefixes match the query's prefix. This significantly reduces the number of glob patterns that need to be fully evaluated, leading to performance improvements, especially when dealing with a large number of patterns. --- Full diff: https://github.com/llvm/llvm-project/pull/164531.diff 2 Files Affected: - (modified) llvm/include/llvm/Support/SpecialCaseList.h (+7) - (modified) llvm/lib/Support/SpecialCaseList.cpp (+17-3) ``````````diff diff --git a/llvm/include/llvm/Support/SpecialCaseList.h b/llvm/include/llvm/Support/SpecialCaseList.h index ead765562504d..16f309329a0b5 100644 --- a/llvm/include/llvm/Support/SpecialCaseList.h +++ b/llvm/include/llvm/Support/SpecialCaseList.h @@ -13,10 +13,13 @@ #define LLVM_SUPPORT_SPECIALCASELIST_H #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringMap.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/GlobPattern.h" +#include "llvm/Support/RadixTree.h" #include "llvm/Support/Regex.h" #include <memory> #include <string> @@ -162,6 +165,10 @@ class SpecialCaseList { }; std::vector<GlobMatcher::Glob> Globs; + + RadixTree<iterator_range<StringRef::const_iterator>, + SmallVector<const GlobMatcher::Glob *, 1>> + PrefixToGlob; }; /// Represents a set of patterns and their line numbers diff --git a/llvm/lib/Support/SpecialCaseList.cpp b/llvm/lib/Support/SpecialCaseList.cpp index f74e52a3a7fa9..2a86cc37b6000 100644 --- a/llvm/lib/Support/SpecialCaseList.cpp +++ b/llvm/lib/Support/SpecialCaseList.cpp @@ -89,14 +89,28 @@ void SpecialCaseList::GlobMatcher::preprocess(bool BySize) { return A.Name.size() < B.Name.size(); }); } + + for (auto &G : Globs) { + StringRef Prefix = G.Pattern.prefix(); + + auto &V = PrefixToGlob.emplace(Prefix).first->second; + V.emplace_back(&G); + } } void SpecialCaseList::GlobMatcher::match( StringRef Query, llvm::function_ref<void(StringRef Rule, unsigned LineNo)> Cb) const { - for (const auto &G : reverse(Globs)) - if (G.Pattern.match(Query)) - return Cb(G.Name, G.LineNo); + if (!PrefixToGlob.empty()) { + for (const auto &[_, V] : PrefixToGlob.find_prefixes(Query)) { + for (const auto *G : reverse(V)) { + if (G->Pattern.match(Query)) { + Cb(G->Name, G->LineNo); + break; + } + } + } + } } SpecialCaseList::Matcher::Matcher(bool UseGlobs, bool RemoveDotSlash) `````````` </details> https://github.com/llvm/llvm-project/pull/164531 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
