[clangd] Add more tracing to index queries. NFC

[sammccall]

clangd/index/Merge.cpp

42

might be fun to add static/dynamic/both counts

clangd/index/dex/Dex.cpp

143

We should attach the query tree to the span here.

Right now that's not practical as the dump() representation holds the posting lists rather than their token, but maybe add a FIXME?

[kbobyrev]

clangd/index/dex/Dex.cpp

143

Yes, that's an interesting topic. I was thinking about better dump format for queries for the dexp commands (namely, find): right now there's no API to pull even the query dump for the external callers, so this is another problem. For better format, I was thinking about adding either LABEL iterator or actually having StringRef Iterator::label() const; as most iterators are likely to have one. E.g. PostingList's can store the Token reference, but then we're likely to run into the memory issues so it can be disabled in all builds other than DEBUG. Other iterators are fine, because they are only constructed once per query and never stored afterwards.

And it would be very useful to see the full query structure for both debugging purposes and for understanding which queries are slow (and why). I thought about measuring distinct queries latency to have better statistics (latency histogram & distributions) to understand how to optimize Dex and improve performance.

[ioeric]

• address comments.

clangd/index/MemIndex.cpp

 //===--- MemIndex.cpp - Dynamic in-memory symbol index. ----------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===-------------------------------------------------------------------===//
 
 #include "MemIndex.h"
 #include "FuzzyMatch.h"
 #include "Logger.h"
 #include "Quality.h"
+#include "Trace.h"
 
 namespace clang {
 namespace clangd {
 
 std::unique_ptr<SymbolIndex> MemIndex::build(SymbolSlab Slab, RefSlab Refs) {
   // Store Slab size before it is moved.
   const auto BackingDataSize = Slab.bytes() + Refs.bytes();
   auto Data = std::make_pair(std::move(Slab), std::move(Refs));
   return llvm::make_unique<MemIndex>(Data.first, Data.second, std::move(Data),
                                      BackingDataSize);
 }
 
 bool MemIndex::fuzzyFind(
     const FuzzyFindRequest &Req,
     llvm::function_ref<void(const Symbol &)> Callback) const {
   assert(!StringRef(Req.Query).contains("::") &&
          "There must be no :: in query.");
+  trace::Span Tracer("MemIndex fuzzyFind");
 
   TopN<std::pair<float, const Symbol *>> Top(
       Req.Limit ? *Req.Limit : std::numeric_limits<size_t>::max());
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
   for (const auto Pair : Index) {
     const Symbol *Sym = Pair.second;
 
     // Exact match against all possible scopes.
     if (!Req.Scopes.empty() && !llvm::is_contained(Req.Scopes, Sym->Scope))
       continue;
     if (Req.RestrictForCodeCompletion &&
         !(Sym->Flags & Symbol::IndexedForCodeCompletion))
       continue;
 
     if (auto Score = Filter.match(Sym->Name))
       if (Top.push({*Score * quality(*Sym), Sym}))
         More = true; // An element with smallest score was discarded.
   }
-  for (const auto &Item : std::move(Top).items())
+  auto Results = std::move(Top).items();
+  SPAN_ATTACH(Tracer, "results", static_cast<int>(Results.size()));
+  for (const auto &Item : Results)
     Callback(*Item.second);
   return More;
 }
 
 void MemIndex::lookup(const LookupRequest &Req,
                       llvm::function_ref<void(const Symbol &)> Callback) const {
+  trace::Span Tracer("MemIndex lookup");
   for (const auto &ID : Req.IDs) {
     auto I = Index.find(ID);
     if (I != Index.end())
       Callback(*I->second);
   }
 }
 
 void MemIndex::refs(const RefsRequest &Req,
                     llvm::function_ref<void(const Ref &)> Callback) const {
+  trace::Span Tracer("MemIndex refs");
   for (const auto &ReqID : Req.IDs) {
     auto SymRefs = Refs.find(ReqID);
     if (SymRefs == Refs.end())
       continue;
     for (const auto &O : SymRefs->second)
       if (static_cast<int>(Req.Filter & O.Kind))
         Callback(O);
   }
 }
 
 size_t MemIndex::estimateMemoryUsage() const {
   return Index.getMemorySize() + Refs.getMemorySize() + BackingDataSize;
 }
 
 } // namespace clangd
 } // namespace clang

clangd/index/Merge.cpp

 //===--- Merge.cpp -----------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Merge.h"
 #include "Logger.h"
+#include "Trace.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/raw_ostream.h"
 #include <set>
 
 namespace clang {
 namespace clangd {
 namespace {
public:
    bool fuzzyFind(const FuzzyFindRequest &Req,
                   function_ref<void(const Symbol &)> Callback) const override {
      // We can't step through both sources in parallel. So:
      //  1) query all dynamic symbols, slurping results into a slab
      //  2) query the static symbols, for each one:
      //    a) if it's not in the dynamic slab, yield it directly
      //    b) if it's in the dynamic slab, merge it and yield the result
      //  3) now yield all the dynamic symbols we haven't processed.
+     trace::Span Tracer("MergedIndex fuzzyFind");
      bool More = false; // We'll be incomplete if either source was.
      SymbolSlab::Builder DynB;
-     More |= Dynamic->fuzzyFind(Req, [&](const Symbol &S) { DynB.insert(S); });
+     unsigned DynamicCount = 0;
+     unsigned StaticCount = 0;
+     unsigned MergedCount = 0;
+     More |= Dynamic->fuzzyFind(Req, [&](const Symbol &S) {
+       ++DynamicCount;
+       DynB.insert(S);
+     });
      SymbolSlab Dyn = std::move(DynB).build();
 
      DenseSet<SymbolID> SeenDynamicSymbols;
      More |= Static->fuzzyFind(Req, [&](const Symbol &S) {
        auto DynS = Dyn.find(S.ID);
+       ++StaticCount;
        if (DynS == Dyn.end())
          return Callback(S);
+       ++MergedCount;
        SeenDynamicSymbols.insert(S.ID);
        Callback(mergeSymbol(*DynS, S));
      });
+     SPAN_ATTACH(Tracer, "dynamic", DynamicCount);
+     SPAN_ATTACH(Tracer, "static", StaticCount);
+     SPAN_ATTACH(Tracer, "merged", MergedCount);
      for (const Symbol &S : Dyn)
        if (!SeenDynamicSymbols.count(S.ID))
          Callback(S);
      return More;
   }
 
   void
   lookup(const LookupRequest &Req,
          llvm::function_ref<void(const Symbol &)> Callback) const override {
+    trace::Span Tracer("MergedIndex lookup");
     SymbolSlab::Builder B;
 
     Dynamic->lookup(Req, [&](const Symbol &S) { B.insert(S); });
 
     auto RemainingIDs = Req.IDs;
     Static->lookup(Req, [&](const Symbol &S) {
       const Symbol *Sym = B.find(S.ID);
       RemainingIDs.erase(S.ID);
       if (!Sym)
         Callback(S);
       else
         Callback(mergeSymbol(*Sym, S));
     });
     for (const auto &ID : RemainingIDs)
       if (const Symbol *Sym = B.find(ID))
         Callback(*Sym);
   }
 
   void refs(const RefsRequest &Req,
             llvm::function_ref<void(const Ref &)> Callback) const override {
+    trace::Span Tracer("MergedIndex refs");
     // We don't want duplicated refs from the static/dynamic indexes,
     // and we can't reliably duplicate them because offsets may differ slightly.
     // We consider the dynamic index authoritative and report all its refs,
     // and only report static index refs from other files.
     //
     // FIXME: The heuristic fails if the dynamic index contains a file, but all
     // refs were removed (we will report stale ones from the static index).
     // Ultimately we should explicit check which index has the file instead.

clangd/index/dex/Dex.cpp

 //===--- Dex.cpp - Dex Symbol Index Implementation --------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Dex.h"
 #include "FileDistance.h"
 #include "FuzzyMatch.h"
 #include "Logger.h"
 #include "Quality.h"
+#include "Trace.h"
 #include "llvm/ADT/StringSet.h"
 #include <algorithm>
 #include <queue>
 
 namespace clang {
 namespace clangd {
 namespace dex {
 

 
 /// 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("::") &&
          "There must be no :: in query.");
+  // FIXME: attach the query tree to the trace span.
+  trace::Span Tracer("Dex fuzzyFind");
   FuzzyMatcher Filter(Req.Query);
   bool More = false;
 
   std::vector<std::unique_ptr<Iterator>> TopLevelChildren;
   const auto TrigramTokens = generateIdentifierTrigrams(Req.Query);
 
   // Generate query trigrams and construct AND iterator over all query
   // trigrams.
bool Dex::fuzzyFind(const FuzzyFindRequest &Req,
   // order of cumulative score.
   for (const auto &Item : std::move(Top).items())
     Callback(*Symbols[Item.first]);
   return More;
 }
 
 void Dex::lookup(const LookupRequest &Req,
                  llvm::function_ref<void(const Symbol &)> Callback) const {
+  trace::Span Tracer("Dex lookup");
   for (const auto &ID : Req.IDs) {
     auto I = LookupTable.find(ID);
     if (I != LookupTable.end())
       Callback(*I->second);
   }
 }
 
 void Dex::refs(const RefsRequest &Req,
                llvm::function_ref<void(const Ref &)> Callback) const {
+  trace::Span Tracer("Dex refs");
   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();