[clangd] Log memory usage of DexIndex and MemIndex

[kbobyrev]

Summary

This patch prints information about built index size estimation to verbose logs. This is useful for optimizing memory usage of DexIndex and comparisons with MemIndex.

[sammccall]

clang-tools-extra/clangd/index/MemIndex.cpp

105 ↗

(On Diff #162141)

access to Index needs to be guarded by mutex

105 ↗

(On Diff #162141)

Index.getMemorySize() is a better estimate.

clang-tools-extra/clangd/index/MemIndex.h

43 ↗

(On Diff #162141)

Can you return bytes here, and do lossy conversions at display time instead?

(Not sure the conversions are even worth it. e.g. it's may be interesting to compare even <1mb indexes)

44 ↗

(On Diff #162141)

I'd suggest making this part of the public interface, and implementing it for all (the implementations should be trivial).

This is useful e.g. for monitoring. We may want vim's :YcmDebugInfo to return this, etc.

clang-tools-extra/clangd/index/dex/DexIndex.cpp

178 ↗

(On Diff #162141)

again, LookupTable.getMemorySize() and others.

180 ↗

(On Diff #162141)

I think you're not counting the size of the actual symbols.
This is difficult to do precisely, but avoiding it seems misleading (we have "shared ownership" but it's basically exclusive). What's the plan here?

182 ↗

(On Diff #162141)

why is only the InvertedIndex access guarded by the mutex?

[kbobyrev]

Address a bunch of comments.

[kbobyrev]

clang-tools-extra/clangd/index/dex/DexIndex.cpp

180 ↗

(On Diff #162141)

As discussed offline: I should put a FIXME and leave it for later.

[ilya-biryukov]

Some drive-by NITS.

clang-tools-extra/clangd/index/MemIndex.cpp

109 ↗

(On Diff #162146)

Why not simply return Index.getMemorySize() under a lock?

clang-tools-extra/clangd/index/dex/DexIndex.cpp

180 ↗

(On Diff #162146)

Maybe put a lock over all of the function and remove the unneeded compound statement?

[kbobyrev]

Slightly simplify the code.

[ioeric]

Do we plan to expose an API in ClangdServer to allow C++ API users to track index memory usages?

clang-tools-extra/clangd/index/FileIndex.cpp

123 ↗

(On Diff #162184)

I think the URI scheme names should be negligible.

clang-tools-extra/clangd/index/dex/DexIndex.cpp

180 ↗

(On Diff #162141)

SymbolSlab provides a pretty good estimation of memory usage, and I think we should try to use if possible (as Sam suggested, it could be misleading without the size of index corpus). IIUC, the challenge here is that SymbolSlabs can be hiden behind shared_ptr, and index might not have access to the underlying slabs. If that's the case, I think it would be reasonable to ask callers of build to also pass in an estimated size of the hidden slabs?

[sammccall]

clang-tools-extra/clangd/index/FileIndex.cpp

123 ↗

(On Diff #162184)

yeah, just drop this I think.

clang-tools-extra/clangd/index/Index.h

391 ↗

(On Diff #162184)

it might be useful --> we should include both :-)

[kbobyrev]

Address few concerns.

[kbobyrev]

In D51154#1211376, @ioeric wrote:

Do we plan to expose an API in ClangdServer to allow C++ API users to track index memory usages?

I think we do, IIUC the conclusion of the offline discussion was that it might be useful for the clients. However, that would require SymbolSlab estimation, too (which is probably out of scope of this patch).

clang-tools-extra/trunk/clangd/index/FileIndex.h

public:
 
   void lookup(const LookupRequest &Req,
               llvm::function_ref<void(const Symbol &)> Callback) const override;
 
 
   void findOccurrences(const OccurrencesRequest &Req,
                        llvm::function_ref<void(const SymbolOccurrence &)>
                            Callback) const override;
+
+  size_t estimateMemoryUsage() const override;
+
 private:
   FileSymbols FSymbols;
   MemIndex Index;
   std::vector<std::string> URISchemes;
 };
 
 /// Retrieves namespace and class level symbols in \p AST.
 /// Exposed to assist in unit tests.

clang-tools-extra/trunk/clangd/index/FileIndex.cpp

 }
 
 void FileIndex::findOccurrences(
     const OccurrencesRequest &Req,
     llvm::function_ref<void(const SymbolOccurrence &)> Callback) const {
   log("findOccurrences is not implemented.");
 }
 
+size_t FileIndex::estimateMemoryUsage() const {
+  return Index.estimateMemoryUsage();
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/index/Index.h

public:
   /// declarations, definitions) and applies \p Callback on each result.
   ///
   /// Resutls are returned in arbitrary order.
   ///
   /// The returned result must be deep-copied if it's used outside Callback.
   virtual void findOccurrences(
       const OccurrencesRequest &Req,
       llvm::function_ref<void(const SymbolOccurrence &)> Callback) const = 0;
+
+  /// Returns estimated size of index (in bytes).
+  // FIXME(kbobyrev): Currently, this only returns the size of index itself
+  // excluding the size of actual symbol slab index refers to. We should include
+  // both.
+  virtual size_t estimateMemoryUsage() const = 0;
 };
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_INDEX_H

clang-tools-extra/trunk/clangd/index/MemIndex.h

public:
   void
   lookup(const LookupRequest &Req,
          llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   void findOccurrences(const OccurrencesRequest &Req,
                        llvm::function_ref<void(const SymbolOccurrence &)>
                            Callback) const override;
 
+  size_t estimateMemoryUsage() const override;
+
 private:
+
   std::shared_ptr<std::vector<const Symbol *>> Symbols;
   // Index is a set of symbols that are deduplicated by symbol IDs.
   // FIXME: build smarter index structure.
   llvm::DenseMap<SymbolID, const Symbol *> Index;
   mutable std::mutex Mutex;
 };
 
 // Returns pointers to the symbols in given slab and bundles slab lifetime with
 // returned symbol pointers so that the pointers are never invalid.
 std::shared_ptr<std::vector<const Symbol *>>
 getSymbolsFromSlab(SymbolSlab Slab);
 
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_MEMINDEX_H

clang-tools-extra/trunk/clangd/index/MemIndex.cpp

for (const Symbol *Sym : *Syms)
     TempIndex[Sym->ID] = Sym;
 
   // Swap out the old symbols and index.
   {
     std::lock_guard<std::mutex> Lock(Mutex);
     Index = std::move(TempIndex);
     Symbols = std::move(Syms); // Relase old symbols.
   }
+
+  vlog("Built MemIndex with estimated memory usage {0} bytes.",
+       estimateMemoryUsage());
 }
 
 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab) {
   auto Idx = llvm::make_unique<MemIndex>();
   Idx->build(getSymbolsFromSlab(std::move(Slab)));
   return std::move(Idx);
 }
 
getSymbolsFromSlab(SymbolSlab Slab) {
   auto Snap = std::make_shared<Snapshot>();
   Snap->Slab = std::move(Slab);
   for (auto &Sym : Snap->Slab)
     Snap->Pointers.push_back(&Sym);
   return std::shared_ptr<std::vector<const Symbol *>>(std::move(Snap),
                                                       &Snap->Pointers);
 }
 
+size_t MemIndex::estimateMemoryUsage() const {
+  std::lock_guard<std::mutex> Lock(Mutex);
+  return Index.getMemorySize();
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/clangd/index/Merge.cpp

public:
   }
 
   void findOccurrences(const OccurrencesRequest &Req,
                        llvm::function_ref<void(const SymbolOccurrence &)>
                            Callback) const override {
     log("findOccurrences is not implemented.");
   }
 
+  size_t estimateMemoryUsage() const override {
+    return Dynamic->estimateMemoryUsage() + Static->estimateMemoryUsage();
+  }
+
 private:
   const SymbolIndex *Dynamic, *Static;
 };
 } // namespace
 
 Symbol
 mergeSymbol(const Symbol &L, const Symbol &R, Symbol::Details *Scratch) {
   assert(L.ID == R.ID);

clang-tools-extra/trunk/clangd/index/dex/DexIndex.h

public:
 
   void lookup(const LookupRequest &Req,
               llvm::function_ref<void(const Symbol &)> Callback) const override;
 
   void findOccurrences(const OccurrencesRequest &Req,
                        llvm::function_ref<void(const SymbolOccurrence &)>
                            Callback) const override;
 
+  size_t estimateMemoryUsage() const override;
+
 private:
+
   mutable std::mutex Mutex;
 
   std::shared_ptr<std::vector<const Symbol *>> Symbols /*GUARDED_BY(Mutex)*/;
   llvm::DenseMap<SymbolID, const Symbol *> LookupTable /*GUARDED_BY(Mutex)*/;
   llvm::DenseMap<const Symbol *, float> SymbolQuality /*GUARDED_BY(Mutex)*/;
   // Inverted index is a mapping from the search token to the posting list,
   // which contains all items which can be characterized by such search token.
   // For example, if the search token is scope "std::", the corresponding

clang-tools-extra/trunk/clangd/index/dex/DexIndex.cpp

for (DocID SymbolRank = 0; SymbolRank < Syms->size(); ++SymbolRank) {
     std::lock_guard<std::mutex> Lock(Mutex);
 
     // Replace outdated index with the new one.
     LookupTable = std::move(TempLookupTable);
     Symbols = std::move(Syms);
     InvertedIndex = std::move(TempInvertedIndex);
     SymbolQuality = std::move(TempSymbolQuality);
   }
+
+  vlog("Built DexIndex with estimated memory usage {0} bytes.",
+       estimateMemoryUsage());
 }
 
 std::unique_ptr<SymbolIndex> DexIndex::build(SymbolSlab Slab) {
   auto Idx = llvm::make_unique<DexIndex>();
   Idx->build(getSymbolsFromSlab(std::move(Slab)));
   return std::move(Idx);
 }
 

 }
 
 void DexIndex::findOccurrences(
     const OccurrencesRequest &Req,
     llvm::function_ref<void(const SymbolOccurrence &)> Callback) const {
   log("findOccurrences is not implemented.");
 }
 
+size_t DexIndex::estimateMemoryUsage() const {
+  std::lock_guard<std::mutex> Lock(Mutex);
+
+  size_t Bytes =
+      LookupTable.size() * sizeof(std::pair<SymbolID, const Symbol *>);
+  Bytes += SymbolQuality.size() * sizeof(std::pair<const Symbol *, float>);
+  Bytes += InvertedIndex.size() * sizeof(Token);
+
+  for (const auto &P : InvertedIndex) {
+    Bytes += P.second.size() * sizeof(DocID);
+  }
+  return Bytes;
+}
+
 } // namespace dex
 } // namespace clangd
 } // namespace clang

clang-tools-extra/trunk/unittests/clangd/CodeCompleteTests.cpp

public:
 
   void lookup(const LookupRequest &,
               llvm::function_ref<void(const Symbol &)>) const override {}
 
   void findOccurrences(const OccurrencesRequest &Req,
                        llvm::function_ref<void(const SymbolOccurrence &)>
                            Callback) const override {}
 
+  // This is incorrect, but IndexRequestCollector is not an actual index and it
+  // isn't used in production code.
+  size_t estimateMemoryUsage() const override { return 0; }
+
   const std::vector<FuzzyFindRequest> allRequests() const { return Requests; }
 
 private:
   mutable std::vector<FuzzyFindRequest> Requests;
 };
 
 std::vector<FuzzyFindRequest> captureIndexRequests(llvm::StringRef Code) {
   clangd::CodeCompleteOptions Opts;