[clangd] Index symbols share storage within a slab.

[sammccall]

Summary

Symbols are not self-contained - it's only safe to hand them out if you
guarantee the lifetime of the underlying data.

Memory usage tests:
I loaded all LLVM project symbols into a single slab.
Using the old implementation, this was 55MB, plus some malloc overhead for out-of-line string allocations that I couldn't easily measure.
Using the new implementation, this was 27MB - we saved half.
(I switched SymbolSlab from DenseMap to vector for both halves of this test to make measurement easier - this is a change @ilya-biryukov suggested would make sense to do for real in a followup patch)

[sammccall]

Don't intern unless the symbol was actually inserted.

[ilya-biryukov]

clangd/index/Index.h

134

A comment on why we use BumpPtrAllocator here might be useful.
I.e., it uses more memory than malloc, but we're getting better data locality. (I hope that I got its intention right)

[hokein]

Nice, LGTM.

clangd/index/Index.h

106–107

Do you want to remove this FIXME now or later?

126

nit: worth a comment here.

[sammccall]

clangd/index/Index.h

134

It's strictly better than malloc for us I think:

• no malloc bookkeeping/padding memory overhead
• we make lots of tiny allocations, they're much cheaper in CPU
• the locality you mentioned

There's no extra memory usage: stringset doesn't use the allocator to allocate the hashtable, just the nodes.

Added a comment.

[sammccall]

Comment changes requiested in review.

clangd/index/Index.h

 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H
 
 #include "../Context.h"
 #include "clang/Index/IndexSymbol.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/StringSet.h"
 #include <array>
 #include <string>
 
 namespace clang {
 namespace clangd {
 
 struct SymbolLocation {
   // The absolute path of the source file where a symbol occurs.
-  std::string FilePath;
+  llvm::StringRef FilePath;
   // The 0-based offset to the first character of the symbol from the beginning
   // of the source file.
   unsigned StartOffset;
   // The 0-based offset to the last character of the symbol from the beginning
   // of the source file.
   unsigned EndOffset;
 };
 

 
 // Construct SymbolID from a hex string.
 // The HexStr is required to be a 40-bytes hex string, which is encoded from the
 // "<<" operator.
 void operator>>(llvm::StringRef HexStr, SymbolID &ID);
 
 // The class presents a C++ symbol, e.g. class, function.
 //
-// FIXME: instead of having own copy fields for each symbol, we can share
-// storage from SymbolSlab.
+// WARNING: Symbols do not own much of their underlying data - typically strings
+// are owned by a SymbolSlab. They should be treated as non-owning references.
+// Copies are shallow.
+// When adding new unowned data fields to Symbol, remember to update
+// SymbolSlab::insert to copy them to the slab's storage.
 struct Symbol {
   // The ID of the symbol.
   SymbolID ID;
   // The unqualified name of the symbol, e.g. "bar" (for "n1::n2::bar").
-  std::string Name;
+  llvm::StringRef Name;
   // The scope (e.g. namespace) of the symbol, e.g. "n1::n2" (for
   // "n1::n2::bar").
-  std::string Scope;
+  llvm::StringRef Scope;
   // The symbol information, like symbol kind.
   index::SymbolInfo SymInfo;
   // The location of the canonical declaration of the symbol.
   //
   // A C++ symbol could have multiple declarations and one definition (e.g.
   // a function is declared in ".h" file, and is defined in ".cc" file).
   //   * For classes, the canonical declaration is usually definition.
   //   * For non-inline functions, the canonical declaration is a declaration
   //     (not a definition), which is usually declared in ".h" file.
   SymbolLocation CanonicalDeclaration;
 
   // FIXME: add definition location of the symbol.
   // FIXME: add all occurrences support.
   // FIXME: add extra fields for index scoring signals.
   // FIXME: add code completion information.
 };
 
 // A symbol container that stores a set of symbols. The container will maintain
 // the lifetime of the symbols.
-//
-// FIXME: Use a space-efficient implementation, a lot of Symbol fields could
-// share the same storage.
 class SymbolSlab {
 public:
   using const_iterator = llvm::DenseMap<SymbolID, Symbol>::const_iterator;
 
   SymbolSlab() = default;
 
   const_iterator begin() const;
   const_iterator end() const;
   const_iterator find(const SymbolID &SymID) const;
 
   // Once called, no more symbols would be added to the SymbolSlab. This
   // operation is irreversible.
   void freeze();
 
-  void insert(Symbol S);
+  // Adds the symbol to this slab.
+  // This is a deep copy: underlying strings will be owned by the slab.
+  void insert(const Symbol& S);
 
 private:
+  // Replaces S with a reference to the same string, owned by this slab.
+  void intern(llvm::StringRef &S) {
+    S = S.empty() ? llvm::StringRef() : Strings.insert(S).first->getKey();
+  }
+
   bool Frozen = false;
 
+  // Intern table for strings. Not StringPool as we don't refcount, just insert.
+  // We use BumpPtrAllocator to avoid lots of tiny allocations for nodes.
+  llvm::StringSet<llvm::BumpPtrAllocator> Strings;
   llvm::DenseMap<SymbolID, Symbol> Symbols;
 };
 
 struct FuzzyFindRequest {
   /// \brief A query string for the fuzzy find. This is matched against symbols'
   /// un-qualified identifiers and should not contain qualifiers like "::".
   std::string Query;
   /// \brief If this is non-empty, symbols must be in at least one of the scopes

clangd/index/Index.cpp

 SymbolSlab::const_iterator SymbolSlab::end() const { return Symbols.end(); }
 
 SymbolSlab::const_iterator SymbolSlab::find(const SymbolID &SymID) const {
   return Symbols.find(SymID);
 }
 
 void SymbolSlab::freeze() { Frozen = true; }
 
-void SymbolSlab::insert(Symbol S) {
+void SymbolSlab::insert(const Symbol &S) {
   assert(!Frozen && "Can't insert a symbol after the slab has been frozen!");
-  Symbols[S.ID] = std::move(S);
+  auto ItInserted = Symbols.try_emplace(S.ID, S);
+  if (!ItInserted.second)
+    return;
+  auto &Sym = ItInserted.first->second;
+
+  // We inserted a new symbol, so copy the underlying data.
+  intern(Sym.Name);
+  intern(Sym.Scope);
+  intern(Sym.CanonicalDeclaration.FilePath);
 }
 
 } // namespace clangd
 } // namespace clang

unittests/clangd/FileIndexTests.cpp

TEST(FileSymbolsTest, SnapshotAliveAfterRemove) {
   EXPECT_THAT(getSymbolNames(*Symbols), UnorderedElementsAre("1", "2", "3"));
 }
 
 std::vector<std::string> match(const SymbolIndex &I,
                                const FuzzyFindRequest &Req) {
   std::vector<std::string> Matches;
   auto Ctx = Context::empty();
   I.fuzzyFind(Ctx, Req, [&](const Symbol &Sym) {
-    Matches.push_back(Sym.Scope + (Sym.Scope.empty() ? "" : "::") + Sym.Name);
+    Matches.push_back(
+        (Sym.Scope + (Sym.Scope.empty() ? "" : "::") + Sym.Name).str());
   });
   return Matches;
 }
 
 /// Create an ParsedAST for \p Code. Returns None if \p Code is empty.
 llvm::Optional<ParsedAST> build(std::string Path, llvm::StringRef Code) {
   Context Ctx = Context::empty();
   if (Code.empty())

unittests/clangd/IndexTests.cpp

generateNumSymbols(int Begin, int End,
   return generateSymbols(Names, WeakSymbols);
 }
 
 std::vector<std::string> match(const SymbolIndex &I,
                                const FuzzyFindRequest &Req) {
   std::vector<std::string> Matches;
   auto Ctx = Context::empty();
   I.fuzzyFind(Ctx, Req, [&](const Symbol &Sym) {
-    Matches.push_back(Sym.Scope + (Sym.Scope.empty() ? "" : "::") + Sym.Name);
+    Matches.push_back(
+        (Sym.Scope + (Sym.Scope.empty() ? "" : "::") + Sym.Name).str());
   });
   return Matches;
 }
 
 TEST(MemIndexTest, MemIndexSymbolsRecycled) {
   MemIndex I;
   std::weak_ptr<SlabAndPointers> Symbols;
   I.build(generateNumSymbols(0, 10, &Symbols));

unittests/clangd/SymbolCollectorTests.cpp

 
 using testing::Eq;
 using testing::Field;
 using testing::UnorderedElementsAre;
 
 // GMock helpers for matching Symbol.
 MATCHER_P(QName, Name, "") {
   return (arg.second.Scope + (arg.second.Scope.empty() ? "" : "::") +
-          arg.second.Name) == Name;
+          arg.second.Name).str() == Name;
 }
 
 namespace clang {
 namespace clangd {
 
 namespace {
 class SymbolIndexActionFactory : public tooling::FrontendActionFactory {
 public: