[clangd] Deduplicate Refs on the fly.

[hokein]

Summary

Currently, we only do deduplication when we flush final results. We may
have huge duplications (refs from headers) during the indexing period (running
clangd-indexer on Chromium).

With this change, clangd-indexer can index the whole chromium projects
(48 threads, 40 GB peak memory usage).

[kadircet]

clangd/index/Ref.cpp

44

Can you add a comment saying that references will be ordered?

clangd/indexer/IndexerMain.cpp

59

instead of just deleting let's mention that it de-duplicates during insertion.

[hokein]

Add comments.

clangd/index/Ref.h

 
 #include "SymbolID.h"
 #include "SymbolLocation.h"
 #include "clang/Index/IndexSymbol.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/StringSaver.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cstdint>
+#include <set>
 #include <utility>
 
 namespace clang {
 namespace clangd {
 
 /// Describes the kind of a cross-reference.
 ///
 /// This is a bitfield which can be combined from different kinds.

 }
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Ref &);
 
 /// An efficient structure of storing large set of symbol references in memory.
 /// Filenames are deduplicated.
 class RefSlab {
 public:
+  // Refs are stored in order.
   using value_type = std::pair<SymbolID, llvm::ArrayRef<Ref>>;
   using const_iterator = std::vector<value_type>::const_iterator;
   using iterator = const_iterator;
 
   RefSlab() = default;
   RefSlab(RefSlab &&Slab) = default;
   RefSlab &operator=(RefSlab &&RHS) = default;
 
public:
     /// Adds a ref to the slab. Deep copy: Strings will be owned by the slab.
     void insert(const SymbolID &ID, const Ref &S);
     /// Consumes the builder to finalize the slab.
     RefSlab build() &&;
 
   private:
     llvm::BumpPtrAllocator Arena;
     llvm::UniqueStringSaver UniqueStrings; // Contents on the arena.
-    llvm::DenseMap<SymbolID, std::vector<Ref>> Refs;
+    llvm::DenseMap<SymbolID, std::set<Ref>> Refs;
   };
 
 private:
   RefSlab(std::vector<value_type> Refs, llvm::BumpPtrAllocator Arena,
           size_t NumRefs)
       : Arena(std::move(Arena)), Refs(std::move(Refs)), NumRefs(NumRefs) {}
 
   llvm::BumpPtrAllocator Arena;

clangd/index/Ref.cpp

 }
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Ref &R) {
   return OS << R.Location << ":" << R.Kind;
 }
 
 void RefSlab::Builder::insert(const SymbolID &ID, const Ref &S) {
   auto &M = Refs[ID];
-  M.push_back(S);
-  M.back().Location.FileURI =
-      UniqueStrings.save(M.back().Location.FileURI).data();
+  if (M.count(S))
+    return;
+  Ref R = S;
+  R.Location.FileURI =
+      UniqueStrings.save(R.Location.FileURI).data();
+  M.insert(std::move(R));
 }
 
 RefSlab RefSlab::Builder::build() && {
   // We can reuse the arena, as it only has unique strings and we need them all.
   // Reallocate refs on the arena to reduce waste and indirections when reading.
   std::vector<std::pair<SymbolID, llvm::ArrayRef<Ref>>> Result;
   Result.reserve(Refs.size());
   size_t NumRefs = 0;
   for (auto &Sym : Refs) {
-    auto &SymRefs = Sym.second;
-    llvm::sort(SymRefs);
-    // FIXME: do we really need to dedup?
-    SymRefs.erase(std::unique(SymRefs.begin(), SymRefs.end()), SymRefs.end());
-
+    std::vector<Ref> SymRefs(Sym.second.begin(), Sym.second.end());
     NumRefs += SymRefs.size();
     Result.emplace_back(Sym.first, llvm::ArrayRef<Ref>(SymRefs).copy(Arena));
   }
   return RefSlab(std::move(Result), std::move(Arena), NumRefs);
 }
 
 } // namespace clangd
 } // namespace clang

clangd/indexer/IndexerMain.cpp

return createStaticIndexingAction(
                      Symbols.insert(mergeSymbol(*Existing, Sym));
                    else
                      Symbols.insert(Sym);
                  }
                },
                [&](RefSlab S) {
                  std::lock_guard<std::mutex> Lock(SymbolsMu);
                  for (const auto &Sym : S) {
-                   // No need to merge as currently all Refs are from main file.
+                   // Deduplication happens during insertion.
                    for (const auto &Ref : Sym.second)
                      Refs.insert(Sym.first, Ref);
                  }
                },
                /*IncludeGraphCallback=*/nullptr)
         .release();
   }