[llvm-objcopy] Improve performance of long pattern lists

[MaskRay]

Summary

Some users use a long list of patterns (PR50404) and O(|patterns|*|symbols|) can
be too slow. Such usage typically does not use --regex or --wildcard, we can use
a DenseSet<CachedHashStringRef> to optimize name lookups.

[jhenderson]

LGTM! Out of interest, what sort of performance difference does this make?

[MaskRay]

@bcain , could you check whether this addresses the performance issue for you?

[MaskRay]

In D105218#2854082, @MaskRay wrote:

@bcain , could you check whether this addresses the performance issue for you?

@bcain Ping?

[justincady]

I am not @bcain, but I tested this patch locally and can confirm it addressed the performance issue (of using a large list of symbols) for me.

I will update the bug. I think this patch solves the issue.

[bcain]

In D105218#2867598, @MaskRay wrote:

In D105218#2854082, @MaskRay wrote:

@bcain , could you check whether this addresses the performance issue for you?

@bcain Ping?

Yes, it does. Thank you very much!

llvm/tools/llvm-objcopy/CommonConfig.h

 //===- CommonConfig.h -------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_OBJCOPY_COMMONCONFIG_H
 #define LLVM_TOOLS_LLVM_OBJCOPY_COMMONCONFIG_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Object/ELFTypes.h"
 #include "llvm/Support/GlobPattern.h"
 #include "llvm/Support/Regex.h"

 public:
   // ErrorCallback is used to handle recoverable errors. An Error returned
   // by the callback aborts the parsing and is then returned by this function.
   static Expected<NameOrPattern>
   create(StringRef Pattern, MatchStyle MS,
          llvm::function_ref<Error(Error)> ErrorCallback);
 
   bool isPositiveMatch() const { return IsPositiveMatch; }
+  Optional<StringRef> getName() const {
+    if (!R && !G)
+      return Name;
+    return None;
+  }
   bool operator==(StringRef S) const {
     return R ? R->match(S) : G ? G->match(S) : Name == S;
   }
   bool operator!=(StringRef S) const { return !operator==(S); }
 };
 
 // Matcher that checks symbol or section names against the command line flags
 // provided for that option.
 class NameMatcher {
-  std::vector<NameOrPattern> PosMatchers;
+  DenseSet<CachedHashStringRef> PosNames;
+  std::vector<NameOrPattern> PosPatterns;
   std::vector<NameOrPattern> NegMatchers;
 
 public:
   Error addMatcher(Expected<NameOrPattern> Matcher) {
     if (!Matcher)
       return Matcher.takeError();
-    if (Matcher->isPositiveMatch())
-      PosMatchers.push_back(std::move(*Matcher));
+    if (Matcher->isPositiveMatch()) {
+      if (Optional<StringRef> MaybeName = Matcher->getName())
+        PosNames.insert(CachedHashStringRef(*MaybeName));
       else
+        PosPatterns.push_back(std::move(*Matcher));
+    } else {
       NegMatchers.push_back(std::move(*Matcher));
+    }
     return Error::success();
   }
   bool matches(StringRef S) const {
-    return is_contained(PosMatchers, S) && !is_contained(NegMatchers, S);
+    return (PosNames.contains(CachedHashStringRef(S)) ||
+            is_contained(PosPatterns, S)) &&
+           !is_contained(NegMatchers, S);
+  }
+  bool empty() const {
+    return PosNames.empty() && PosPatterns.empty() && NegMatchers.empty();
   }
-  bool empty() const { return PosMatchers.empty() && NegMatchers.empty(); }
 };
 
 enum class SymbolFlag {
   Global,
   Local,
   Weak,
   Default,
   Hidden,