[clangd][NFC] Reduce memory usage while building dex

[kadircet]

Summary

Posting lists were copied into the final inverted index rather than
being moved. Also we weren't shrinking the vectors. This patch should help with
both peak memory usage while building dex (preamble/background-index) and it's
idle memory usage (unclear if copy constructor of vector preserves the capacity
or not).

[kadircet]

Get rid of shrink_to_fit as PostingList representation doesn't really make a copy of the vector, but rather build a new representation.

[sammccall]

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

112

the move here does nothing, we're passing as ArrayRef

did you want to clear the map values (vectors) as you went, too?

(this gets a bit verbose, but you could pull out a function template since all 4 cases are so regular)

[kadircet]

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

112

did you want to clear the map values (vectors) as you went, too?

yes that's the idea. would you prefer an explicit destructor call?

(this gets a bit verbose, but you could pull out a function template since all 4 cases are so regular)

the problem is 1 of these is a densemap, other three is a stringmap, and onther is a vector. densemap and the stringmap doesn't really go together because there's no common method to get the key (densemap has first as a field, or getFirst() as a method. stringmap has first() or getKey() as methods :/).
happy to move out just the three of them into a helper like:

buildPostingList(StringMap<..>, TokenKind, Out);

if you think that's still helpful (that way we can also get rid of the calls to clear since we can just move the maps into the function arguments).

[sammccall]

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

112

yes that's the idea. would you prefer an explicit destructor call?

I mean e.second.clear() in the loop.
As it stands, you're only destroying them a whole map at a time, and trigrams is (i think) >50% of the total

the problem is 1 of these is a densemap, other three is a stringmap, and onther is a vector.

Sounds too complicated, nevermind!

[kadircet]

Copy-assign to empty containers rather than clear.

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

 //===--- Dex.cpp - Dex Symbol Index Implementation --------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "Dex.h"
 #include "FileDistance.h"
 #include "FuzzyMatch.h"
 #include "Quality.h"
 #include "URI.h"
 #include "index/Index.h"
 #include "index/dex/Iterator.h"
+#include "index/dex/Token.h"
 #include "index/dex/Trigram.h"
 #include "support/Logger.h"
 #include "support/Trace.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/ScopedPrinter.h"
 #include <algorithm>
 #include <queue>
+#include <utility>
+#include <vector>
 
 namespace clang {
 namespace clangd {
 namespace dex {
 
 std::unique_ptr<SymbolIndex> Dex::build(SymbolSlab Symbols, RefSlab Refs,
                                         RelationSlab Rels) {
   auto Size = Symbols.bytes() + Refs.bytes();
if (!llvm::StringRef(Sym.CanonicalDeclaration.FileURI).empty())
         ProximityDocs[ProximityURI].push_back(D);
     if (Sym.Flags & Symbol::IndexedForCodeCompletion)
       RestrictedCCDocs.push_back(D);
     if (!Sym.Type.empty())
       TypeDocs[Sym.Type].push_back(D);
   }
 
   // Assemble the final compressed posting lists for the added symbols.
-  llvm::DenseMap<Token, PostingList> build() {
+  llvm::DenseMap<Token, PostingList> build() && {
     llvm::DenseMap<Token, PostingList> Result(/*InitialReserve=*/
                                               TrigramDocs.size() +
                                               RestrictedCCDocs.size() +
                                               TypeDocs.size() +
                                               ScopeDocs.size() +
                                               ProximityDocs.size());
-    for (const auto &E : TrigramDocs)
+    // Tear down intermediate structs as we go to reduce memory usage.
+    // Since we're trying to get rid of underlying allocations, clearing the
+    // containers is not enough.
+    auto CreatePostingList =
+        [&Result](Token::Kind TK, llvm::StringMap<std::vector<DocID>> &Docs) {
+          for (auto &E : Docs) {
+            Result.try_emplace(Token(TK, E.first()), E.second);
+            E.second = {};
+          }
+          Docs = {};
+        };
+    CreatePostingList(Token::Kind::Type, TypeDocs);
+    CreatePostingList(Token::Kind::Scope, ScopeDocs);
+    CreatePostingList(Token::Kind::ProximityURI, ProximityDocs);
+
+    // TrigramDocs are stored in a DenseMap and RestrictedCCDocs is not even a
+    // map, treat them specially.
+    for (auto &E : TrigramDocs) {
       Result.try_emplace(Token(Token::Kind::Trigram, E.first.str()), E.second);
-    for (const auto &E : TypeDocs)
-      Result.try_emplace(Token(Token::Kind::Type, E.first()), E.second);
-    for (const auto &E : ScopeDocs)
-      Result.try_emplace(Token(Token::Kind::Scope, E.first()), E.second);
-    for (const auto &E : ProximityDocs)
-      Result.try_emplace(Token(Token::Kind::ProximityURI, E.first()), E.second);
+      E.second = {};
+    }
+    TrigramDocs = llvm::DenseMap<Trigram, std::vector<DocID>>{};
     if (!RestrictedCCDocs.empty())
-      Result.try_emplace(RestrictedForCodeCompletion, RestrictedCCDocs);
+      Result.try_emplace(RestrictedForCodeCompletion,
+                         std::move(RestrictedCCDocs));
     return Result;
   }
 };
 
 } // namespace
 
 void Dex::buildIndex() {
   this->Corpus = dex::Corpus(Symbols.size());
for (size_t I = 0; I < ScoredSymbols.size(); ++I) {
     SymbolQuality[I] = ScoredSymbols[I].first;
     Symbols[I] = ScoredSymbols[I].second;
   }
 
   // Build posting lists for symbols.
   IndexBuilder Builder;
   for (DocID SymbolRank = 0; SymbolRank < Symbols.size(); ++SymbolRank)
     Builder.add(*Symbols[SymbolRank], SymbolRank);
-  InvertedIndex = Builder.build();
+  InvertedIndex = std::move(Builder).build();
 }
 
 std::unique_ptr<Iterator> Dex::iterator(const Token &Tok) const {
   auto It = InvertedIndex.find(Tok);
   return It == InvertedIndex.end() ? Corpus.none()
                                    : It->second.iterator(&It->first);
 }