COFF: Parallelize InputFile::parse().

rui314 · rui314 · commit f4d05d7a8069 · 2015-09-19T01:48:26.000Z
InputFile::parse() can be called in parallel with other calls of
the same function. By doing that, time to self-link improves from
741 ms to 654 ms or 12% faster.

This is probably the last low hanging fruit in terms of parallelism.
Input file parsing and symbol table insertion takes 450 ms in total.
If we want to optimize further, we probably have to parallelize
symbol table insertion using concurrent hashmap or something.
That's doable, but that's not easy, especially if you want to keep
the exact same semantics and linking order. I'm not going to do that
at least soon.

Anyway, compared to r248019 (the change before the first attempt for
parallelism), we achieved 36% performance improvement from 1022 ms
to 654 ms. MSVC linker takes 3.3 seconds to link the same program.
MSVC's ICF feature is very slow for some reason, but even if we
disable the feature, it still takes about 1.2 seconds.
Our number is probably good enough.

llvm-svn: 248078
diff --git a/lld/COFF/SymbolTable.cpp b/lld/COFF/SymbolTable.cpp
@@ -12,6 +12,7 @@
 #include "Error.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
+#include "lld/Core/Parallel.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/LTO/LTOCodeGenerator.h"
 #include "llvm/Support/Debug.h"
@@ -56,13 +57,15 @@ void SymbolTable::readArchives() {
   if (ArchiveQueue.empty())
     return;
 
+  std::for_each(ArchiveQueue.begin(), ArchiveQueue.end(),
+                [](ArchiveFile *File) { File->parse(); });
+
   // Add lazy symbols to the symbol table. Lazy symbols that conflict
   // with existing undefined symbols are accumulated in LazySyms.
   std::vector<Symbol *> LazySyms;
   for (ArchiveFile *File : ArchiveQueue) {
     if (Config->Verbose)
       llvm::outs() << "Reading " << File->getShortName() << "\n";
-    File->parse();
     for (Lazy &Sym : File->getLazySymbols())
       addLazy(&Sym, &LazySyms);
   }
@@ -80,22 +83,25 @@ void SymbolTable::readObjects() {
 
   // Add defined and undefined symbols to the symbol table.
   std::vector<StringRef> Directives;
-  for (size_t I = 0; I < ObjectQueue.size(); ++I) {
-    InputFile *File = ObjectQueue[I];
-    if (Config->Verbose)
-      llvm::outs() << "Reading " << File->getShortName() << "\n";
-    File->parse();
-    // Adding symbols may add more files to ObjectQueue
-    // (but not to ArchiveQueue).
-    for (SymbolBody *Sym : File->getSymbols())
-      if (Sym->isExternal())
-        addSymbol(Sym);
-    StringRef S = File->getDirectives();
-    if (!S.empty()) {
-      Directives.push_back(S);
+  for (size_t I = 0; I < ObjectQueue.size();) {
+    std::for_each(ObjectQueue.begin() + I, ObjectQueue.end(),
+                  [](InputFile *File) { File->parse(); });
+    for (size_t E = ObjectQueue.size(); I != E; ++I) {
+      InputFile *File = ObjectQueue[I];
       if (Config->Verbose)
-        llvm::outs() << "Directives: " << File->getShortName()
-                     << ": " << S << "\n";
+        llvm::outs() << "Reading " << File->getShortName() << "\n";
+      // Adding symbols may add more files to ObjectQueue
+      // (but not to ArchiveQueue).
+      for (SymbolBody *Sym : File->getSymbols())
+        if (Sym->isExternal())
+          addSymbol(Sym);
+      StringRef S = File->getDirectives();
+      if (!S.empty()) {
+        Directives.push_back(S);
+        if (Config->Verbose)
+          llvm::outs() << "Directives: " << File->getShortName()
+                       << ": " << S << "\n";
+      }
     }
   }
   ObjectQueue.clear();
