Cache file IDs of symbols in emitStabs for faster sorting

[michaeleisel]

Summary

This reduces the time emitStabs() takes by about 275ms, or 3% of overall linking time for the project I'm on. Although the parent function is run in parallel, it's one of the slowest tasks in that concurrent batch (I have another optimization for another slow task as well).

This is my first LLVM revision, so any guidance on the process is appreciated.

[michaeleisel]

lld/MachO/SyntheticSections.cpp

924

We could also use bucket sort instead, but I just went with this. It reduces sorting time by ~75%

[thakis]

Nice!

I'd keep the name symbolsNeedingStabs though, that seems like a much better name than sortingPairs (?)

Do you have commit permissions, or should I land this for you? If so, what --author= should I use (ie preferred name and email)?

[michaeleisel]

Rename to symbolsNeedingStabs

[michaeleisel]

@thakis I don't have commit permissions, if you could land it that'd be great. My preferred name is "Michael Eisel", and preferred email is "[e-mail]". Thanks!

[MaskRay]

lld/MachO/SyntheticSections.cpp

894

use using

[thakis]

Landed in f5709066e3b0, thanks!

lld/MachO/SyntheticSections.cpp

894

Done.

[int3]

Awesome!

[thakis]

lld/MachO/SyntheticSections.cpp

922–923

Oh sorry, I missed that this is > 80 columns. LLVM uses 80 columns. Run git clang-format HEAD^ to make clang-format auto-format your code before sending out patches :)

Fixed this up in 815825f4426f91. Apologies again for missing it before committing.

[michaeleisel]

@thakis oops, will do in the future!

lld/MachO/SyntheticSections.cpp

 //===- SyntheticSections.cpp ---------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
if (config->omitDebugInfo)
     return;
 
   for (const std::string &s : config->astPaths) {
     StabsEntry astStab(N_AST);
     astStab.strx = stringTableSection.addString(s);
     stabs.emplace_back(std::move(astStab));
   }
 
-  std::vector<Defined *> symbolsNeedingStabs;
+  // Cache the file ID for each symbol in an std::pair for faster sorting
+  typedef std::pair<Defined *, int> SortingPair;
+  std::vector<SortingPair> sortingPairs;
   for (const SymtabEntry &entry :
        concat<SymtabEntry>(localSymbols, externalSymbols)) {
     Symbol *sym = entry.sym;
     assert(sym->isLive() &&
            "dead symbols should not be in localSymbols, externalSymbols");
     if (auto *defined = dyn_cast<Defined>(sym)) {
       // Excluded symbols should have been filtered out in finalizeContents().
       assert(defined->includeInSymtab);
 
       if (defined->isAbsolute())
         continue;
 
       // Constant-folded symbols go in the executable's symbol table, but don't
       // get a stabs entry.
       if (defined->wasIdenticalCodeFolded)
         continue;
 
       InputSection *isec = defined->isec;
       ObjFile *file = dyn_cast_or_null<ObjFile>(isec->getFile());
       if (!file || !file->compileUnit)
         continue;
 
-      symbolsNeedingStabs.push_back(defined);
+      sortingPairs.emplace_back(defined, defined->isec->getFile()->id);
     }
   }
 
-  llvm::stable_sort(symbolsNeedingStabs, [&](Defined *a, Defined *b) {
-    return a->isec->getFile()->id < b->isec->getFile()->id;
+  llvm::stable_sort(sortingPairs, [&](const SortingPair &a, const SortingPair &b) {
+    return a.second < b.second;
   });
 
   // Emit STABS symbols so that dsymutil and/or the debugger can map address
   // regions in the final binary to the source and object files from which they
   // originated.
   InputFile *lastFile = nullptr;
-  for (Defined *defined : symbolsNeedingStabs) {
+  for (SortingPair &pair : sortingPairs) {
+    Defined *defined = pair.first;
     InputSection *isec = defined->isec;
     ObjFile *file = cast<ObjFile>(isec->getFile());
 
     if (lastFile == nullptr || lastFile != file) {
       if (lastFile != nullptr)
         emitEndSourceStab();
       lastFile = file;