[clangd] Fix bugs with incorrect memory estimate report

[kbobyrev]

Summary

• With the current implementation, sizeof(std::vector<Chunk>) is added twice to the Dex memory estimate which is incorrect
• Dex logs memory usage estimation before BackingDataSize is set and hence the log report excludes size of the external SymbolSlab which is coupled with Dex instance

[ioeric]

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

251 ↗

(On Diff #166891)

Would InvertedIndex.getMemorySize() be a better estimate?

[kbobyrev]

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

251 ↗

(On Diff #166891)

IIUC this is only precise for the objects which do not make any allocations (e.g. std::vector and std::string memory estimate would not be "correct").

From the documentation

This is just the raw memory used by DenseMap. If entries are pointers to objects, the size of the referenced objects are not included.

I also have Bytes += InvertedIndex.getMemorySize(); above, so the purpose of this code would be to take into account the size of these "reference objects".

However, since PostingList::bytes() also returns underlying std::vector size, this code will probably add these std::vector objects size twice (the first one was in InvertedIndex.getMemorySize()). I should fix that.

[ioeric]

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

251 ↗

(On Diff #166891)

If entries are pointers to objects, the size of the referenced objects are not included.

This applies to *pointers* to objects, but the PostingLists in InvertedList are not pointerd? So it seems to me that InvertedIndex.getMemorySize() covers everything in the InvertedIndex. One way to verify is probably check the size calculated with loop against InvertedIndex.getMemorySize().

[kbobyrev]

• Prevent sizeof(std::vector<Chunk>) to be counted twice in the memory estimates
• Pull memory usage logging to the caller side: it is currently incorrect because Dex::BackingDataSize is not set by the time vlog(..., estimateMemoryUsage()) is called and hence the log only includes size of the index overhead

I will remove these changes from D52047 and hopefully make it easier to review.

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

251 ↗

(On Diff #166891)

As discussed offline, pointers and references are an example of objects which would be incorrectly measured by DesneMap::getMemorySize(), but std::vector and std::string are pointers in a way because they also just store a pointer to the underlying storage which is hidden from DenseMap::getMemorySize(); thus, it would be more precise to use the proposed scheme for memory estimation.

[kbobyrev]

As discussed offline, using std::string::size() would not be a precise estimate of std::string size, therefore I'm excluding Token::Data size estimate.

[ioeric]

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

251 ↗

(On Diff #166891)

I see. I was expecting DenseMap to maintain an arena which could provide memory usage of all owned data, but it seems to only consider sizeof(KV-Pair)...

If the posting lists (vectors) are not covered, shouldn't we also also add the size of tokens (string) here?

[kbobyrev]

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

251 ↗

(On Diff #166891)

Yes, I was also adding TokenToPostingList.first.Data.size() to the size estimate in the previous revision snapshot, but as @sammccall pointed out, there are multiple string implementations and one of them (IIUC this one is currently pushed in the C++ Standard) utilizes Small Object Optimization (i.e. it behaves like llvm::SmallVector rather than std::vector). Therefore, it does not perform external allocations before some limit is reached. I don't know whether it is possible to know whether the external allocation happened or not and the summary of our discussion with Sam was that we should just omit this.

clangd/index/Serialization.cpp

 //===-- Serialization.cpp - Binary serialization of index data ------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+
 #include "Serialization.h"
 #include "Index.h"
+#include "Logger.h"
 #include "RIFF.h"
 #include "Trace.h"
 #include "dex/Dex.h"
 #include "llvm/Support/Compression.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 
 using namespace llvm;
if (auto I = readIndexFile(Buffer->get()->getBuffer())) {
         Symbols = std::move(*I->Symbols);
     } else {
       llvm::errs() << "Bad Index: " << llvm::toString(I.takeError()) << "\n";
       return nullptr;
     }
   }
 
   trace::Span Tracer("BuildIndex");
-  return UseDex ? dex::Dex::build(std::move(Symbols), URISchemes)
+  auto Index = UseDex ? dex::Dex::build(std::move(Symbols), URISchemes)
                       : MemIndex::build(std::move(Symbols), std::move(Refs));
+  vlog("Loaded {0} from {1} with estimated memory usage {2}",
+       UseDex ? "Dex" : "MemIndex", SymbolFilename,
+       Index->estimateMemoryUsage());
+  return Index;
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/dex/Dex.cpp

for (DocID SymbolRank = 0; SymbolRank < Symbols.size(); ++SymbolRank) {
     for (const auto &Token : generateSearchTokens(*Sym))
       TempInvertedIndex[Token].push_back(SymbolRank);
   }
 
   // Convert lists of items to posting lists.
   for (const auto &TokenToPostingList : TempInvertedIndex)
     InvertedIndex.insert(
         {TokenToPostingList.first, PostingList(TokenToPostingList.second)});
-
-  vlog("Built Dex with estimated memory usage {0} bytes.",
-       estimateMemoryUsage());
 }
 
 /// Constructs iterators over tokens extracted from the query and exhausts it
 /// while applying Callback to each symbol in the order of decreasing quality
 /// of the matched symbols.
 bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
                     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
void Dex::refs(const RefsRequest &Req,
   log("refs is not implemented.");
 }
 
 size_t Dex::estimateMemoryUsage() const {
   size_t Bytes = Symbols.size() * sizeof(const Symbol *);
   Bytes += SymbolQuality.size() * sizeof(float);
   Bytes += LookupTable.getMemorySize();
   Bytes += InvertedIndex.getMemorySize();
-  for (const auto &P : InvertedIndex)
-    Bytes += P.second.bytes();
+  for (const auto &TokenToPostingList : InvertedIndex)
+    Bytes += TokenToPostingList.second.bytes();
   return Bytes + BackingDataSize;
 }
 
 std::vector<std::string> generateProximityURIs(llvm::StringRef URIPath) {
   std::vector<std::string> Result;
   auto ParsedURI = URI::parse(URIPath);
   assert(ParsedURI &&
          "Non-empty argument of generateProximityURIs() should be a valid "

clangd/index/dex/PostingList.h

 class PostingList {
 public:
   explicit PostingList(llvm::ArrayRef<DocID> Documents);
 
   /// Constructs DocumentIterator over given posting list. DocumentIterator will
   /// go through the chunks and decompress them on-the-fly when necessary.
   std::unique_ptr<Iterator> iterator() const;
 
-  /// Returns in-memory size.
-  size_t bytes() const {
-    return sizeof(Chunk) + Chunks.capacity() * sizeof(Chunk);
-  }
+  /// Returns in-memory size of external storage.
+  size_t bytes() const { return Chunks.capacity() * sizeof(Chunk); }
 
 private:
   const std::vector<Chunk> Chunks;
 };
 
 } // namespace dex
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_DEX_POSTINGLIST_H