[index] Fix performance regression with indexing macros

[benlangmuir]

Summary

When using FileIndexRecord with macros, symbol references can be seen out of source order, which was causing a regression to insert the symbols into a vector. Instead, we now lazily sort the vector. The impact is small on most code, but in very large files with many macro references (M) near the beginning of the file followed by many decl references (D) it was O(M*D). A particularly bad protobuf-generated header was observed with a 100% regression in practice.

rdar://78628133

[arphaman]

Thanks, LGTM!

[benlangmuir]

Pushed rG773ad55a393f

clang/lib/Index/FileIndexRecord.h

 namespace index {
 
 /// Stores the declaration occurrences seen in a particular source or header
 /// file of a translation unit
 class FileIndexRecord {
 private:
   FileID FID;
   bool IsSystem;
-  std::vector<DeclOccurrence> Decls;
+  mutable bool IsSorted = false;
+  mutable std::vector<DeclOccurrence> Decls;
 
 public:
   FileIndexRecord(FileID FID, bool IsSystem) : FID(FID), IsSystem(IsSystem) {}
 
-  ArrayRef<DeclOccurrence> getDeclOccurrencesSortedByOffset() const {
-    return Decls;
-  }
+  ArrayRef<DeclOccurrence> getDeclOccurrencesSortedByOffset() const;
 
   FileID getFileID() const { return FID; }
   bool isSystem() const { return IsSystem; }
 
   /// Adds an occurrence of the canonical declaration \c D at the supplied
   /// \c Offset
   ///
   /// \param Roles the roles the occurrence fulfills in this position.

clang/lib/Index/FileIndexRecord.cpp

 #include "clang/AST/DeclTemplate.h"
 #include "clang/Basic/SourceManager.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/Support/Path.h"
 
 using namespace clang;
 using namespace clang::index;
 
-static void addOccurrence(std::vector<DeclOccurrence> &Decls,
-                          DeclOccurrence Info) {
-  auto IsNextOccurence = [&]() -> bool {
-    if (Decls.empty())
-      return true;
-    auto &Last = Decls.back();
-    return Last.Offset < Info.Offset;
-  };
-
-  if (IsNextOccurence()) {
-    Decls.push_back(std::move(Info));
-    return;
-  }
-
-  // We keep Decls in order as we need to access them in this order in all cases.
-  auto It = llvm::upper_bound(Decls, Info);
-  Decls.insert(It, std::move(Info));
+ArrayRef<DeclOccurrence>
+FileIndexRecord::getDeclOccurrencesSortedByOffset() const {
+  if (!IsSorted) {
+    llvm::stable_sort(Decls,
+                      [](const DeclOccurrence &A, const DeclOccurrence &B) {
+                        return A.Offset < B.Offset;
+                      });
+    IsSorted = true;
+  }
+  return Decls;
 }
 
 void FileIndexRecord::addDeclOccurence(SymbolRoleSet Roles, unsigned Offset,
                                        const Decl *D,
                                        ArrayRef<SymbolRelation> Relations) {
   assert(D->isCanonicalDecl() &&
          "Occurrences should be associated with their canonical decl");
-  addOccurrence(Decls, DeclOccurrence(Roles, Offset, D, Relations));
+  IsSorted = false;
+  Decls.emplace_back(Roles, Offset, D, Relations);
 }
 
 void FileIndexRecord::addMacroOccurence(SymbolRoleSet Roles, unsigned Offset,
                                         const IdentifierInfo *Name,
                                         const MacroInfo *MI) {
-  addOccurrence(Decls, DeclOccurrence(Roles, Offset, Name, MI));
+  IsSorted = false;
+  Decls.emplace_back(Roles, Offset, Name, MI);
 }
 
 void FileIndexRecord::removeHeaderGuardMacros() {
   auto It =
       std::remove_if(Decls.begin(), Decls.end(), [](const DeclOccurrence &D) {
         if (const auto *MI = D.DeclOrMacro.dyn_cast<const MacroInfo *>())
           return MI->isUsedForHeaderGuard();
         return false;