Remove a std::map and std::set that show up in LLD profiles

[rnk]

Summary

For GC roots, add a bit to SymbolBody to ensure that we don't add the
same root twice, and switch to a vector. This is an improvement, since
we iterate the GCRoot list later and it the order should be
deterministic.

For fixupExports, we can just use DenseMap. This is a simple string
uniquing task, and we don't iterate the map.

[ruiu]

Is Config->GCRoot that slow? If so, if you replace it with SetVector, is it still slow?

[rnk]

In D39609#915412, @ruiu wrote:

Is Config->GCRoot that slow? If so, if you replace it with SetVector, is it still slow?

We spend 350ms out of 52s in the GCRoot->insert call, so I guess 0.6%.

I suspect that the majority of this comes from this loop over exports:

// Windows specific -- Make sure we resolve all dllexported symbols.
for (Export &E : Config->Exports) {
  if (!E.ForwardTo.empty())
    continue;
  E.Sym = addUndefined(E.Name);
  if (!E.Directives)
    Symtab->mangleMaybe(E.Sym);
}

Consider that there are many duplicate /export: directives in each object file. Therefore, most calls to addUndefined will be for symbols that we already have. The code I'm changing does one lookup of the string (this is necessary) and then a set lookup of the SymbolBody pointer. That set lookup is completely unnecessary, though, if we add the GCRoot bit to SymbolBody.

I haven't tried SetVector, I don't think the performance difference will be measurable. My goal isn't to compare containers, it's to eliminate the pointer set lookup completely.

[ruiu]

If you can get a similar speedup using SetVector, you don't need to add a new member to Symbol, so I think it is worth a try.

[rnk]

In D39609#915677, @ruiu wrote:

If you can get a similar speedup using SetVector, you don't need to add a new member to Symbol, so I think it is worth a try.

I switched to SetVector, and profiling still shows 46 samples in DenseMap insertion. It's a big improvement over 391 samples in binary tree insertion, but I don't see any reason to leave these samples on the table when we can replace it with a simple bit. This will save a DenseMap of pointers to all the exported symbols, so it seems worth it to me, assuming that there are many exports. I attached screenshots of the profiles.

[ruiu]

LGTM

lld/trunk/COFF/Config.h

struct Configuration {
   bool Force = false;
   bool Debug = false;
   bool WriteSymtab = true;
   unsigned DebugTypes = static_cast<unsigned>(DebugType::None);
   llvm::SmallString<128> PDBPath;
   std::vector<llvm::StringRef> Argv;
 
   // Symbols in this set are considered as live by the garbage collector.
-  std::set<Symbol *> GCRoot;
+  std::vector<Symbol *> GCRoot;
 
   std::set<StringRef> NoDefaultLibs;
   bool NoDefaultLibAll = false;
 
   // True if we are creating a DLL.
   bool DLL = false;
   StringRef Implib;
   std::vector<Export> Exports;

lld/trunk/COFF/Driver.cpp

while (!Env.empty()) {
     StringRef Path;
     std::tie(Path, Env) = Env.split(';');
     SearchPaths.push_back(Path);
   }
 }
 
 Symbol *LinkerDriver::addUndefined(StringRef Name) {
   Symbol *B = Symtab->addUndefined(Name);
-  Config->GCRoot.insert(B);
+  if (!B->IsGCRoot) {
+    B->IsGCRoot = true;
+    Config->GCRoot.push_back(B);
+  }
   return B;
 }
 
 // Symbol names are mangled by appending "_" prefix on x86.
 StringRef LinkerDriver::mangle(StringRef Sym) {
   assert(Config->Machine != IMAGE_FILE_MACHINE_UNKNOWN);
   if (Config->Machine == I386)
     return Saver.save("_" + Sym);

lld/trunk/COFF/Symbols.h

public:
   // Indicates that this symbol will be included in the final image. Only valid
   // after calling markLive.
   bool isLive() const;
 
 protected:
   friend SymbolTable;
   explicit Symbol(Kind K, StringRef N = "")
       : SymbolKind(K), IsExternal(true), IsCOMDAT(false),
-        WrittenToSymtab(false), Name(N) {}
+        WrittenToSymtab(false), PendingArchiveLoad(false), IsGCRoot(false),
+        Name(N) {}
 
   const unsigned SymbolKind : 8;
   unsigned IsExternal : 1;
 
   // This bit is used by the \c DefinedRegular subclass.
   unsigned IsCOMDAT : 1;
 
 public:
   // This bit is used by Writer::createSymbolAndStringTable() to prevent
   // symbols from being written to the symbol table more than once.
   unsigned WrittenToSymtab : 1;
 
   // True if this symbol was referenced by a regular (non-bitcode) object.
   unsigned IsUsedInRegularObj : 1;
 
   // True if we've seen both a lazy and an undefined symbol with this symbol
   // name, which means that we have enqueued an archive member load and should
   // not load any more archive members to resolve the same symbol.
   unsigned PendingArchiveLoad : 1;
 
+  /// True if we've already added this symbol to the list of GC roots.
+  unsigned IsGCRoot : 1;
+
 protected:
   StringRef Name;
 };
 
 // The base class for any defined symbols, including absolute symbols,
 // etc.
 class Defined : public Symbol {
 public: