[clangd] Add building benchmark and memory consumption tracking

[kbobyrev]

Summary

Split build stage into loading SymbolSlab from file and actual index building stage to simplify benchmarking distinct parts of index builds.

As for the memory consumption "benchmark", while this looks like misuse of benchmark library, this can be still when experimenting with index compression techniques as discussed offline.

Also, switch to ms for benchmark measurements time units and fix incorrect logger message ( BackingMemorySize is not initialized to correct value when the logger is called, callers should be responsible for memory usage logging).

[kbobyrev]

• Start measuring time in ms
• Add Tokens' Data size for more precise memory usage estimation (accounts for ~1MB of Static Index in LLVM)

[kbobyrev]

Move vlog message to the outer build(...) function: otherwise BackingMemorySize is not set to the correct value and log reports index overhead (instead of the complete index + slab) size.

[ioeric]

The benchmark change looks fine to me. But I'm not very familiar with the trick, so I'll let Sam (who proposed the idea as you mentioned), stamp the patch.

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

75 ↗

(On Diff #165440)

It's a bit strange to log this in the constructor. And we only do the logging for one of the constructors. Maybe just have the user log the mem usage when they want?

[kbobyrev]

Rebase on top of master, move logging to symbol index build() caller side.

[ioeric]

clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp

82

The hack might not be obvious for other people who run these benchmarks. Is it possible to print some extra message along with the result to explain the hack?

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

239 ↗

(On Diff #165962)

Why do we need P.second.bytes() * sizeof(DocID)? Isn't P.second.bytes() already the memory size of the posting list?

[kbobyrev]

clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp

82

Yes, that makes sense. I might try to use User-Defined Counters for that.

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

239 ↗

(On Diff #165962)

Yes, the patch is out of sync. Will fix!

[kbobyrev]

Add symbol index building benchmarks, split loadIndex() into symbolsFromFile() and actual index build.

[kbobyrev]

Add benchmark for SymbolSlab loading from file. This might be useful for RIFF/YAML symbol loader optimizations.

[kbobyrev]

Remove BuildMem benchmark, which collects data about MemIndex building time (which is essentially nothing and therefore not really interesting).

[ilya-biryukov]

Also not sure about the trick:

• Would be surprising to see the "ms" instead of "mbytes"
• Time tends to vary between runs, so using Google Benchmark's capabilities to run multiple times and report aggregated times seems useful. Not so much for the memory usage: it's deterministic and running multiple times is just a waste of time.

I wonder if a separate (and trivial) C++ binary that would load the index and report the index size is any worse than the benchmark hack? What are the pros of the latter?

clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp

84

Given the trick we use for display, how are we going to show two memory uses?

181

Since return 0 is implied for main in C++, there's no need to add one.
May add clarity though, so feel free to keep it!

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

189 ↗

(On Diff #166271)

Return llvm::Expected instead of Optional and create errors with the specified text instead.
This is a slightly better option for the library code (callers can report errors in various ways, e.g. one can imagine reporting it in the LSP instead of stderr)

200 ↗

(On Diff #166271)

Same here: just propagate the error to the caller.

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

239 ↗

(On Diff #166271)

Just to clarify: P.first.Data.size() is the size of the arena for all the symbols?

[kbobyrev]

Use llvm::Expected<SymbolSlab>, cleanup the patch.

[kbobyrev]

clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp

84

As discussed offline, this hack also relies on the fact that benchmark has a dynamic nature of determining iterations count. Giving a large number of "time units" to the counter results in a single iteration.

I've tried to understand whether I could use any flags for User-Defined Counter that could just divide the number of iterations by IterationTime, but I could find one that would do exactly what is needed here. Also, I didn't find any way to manually set the iteration count.

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

239 ↗

(On Diff #166271)

P is std::pair<Token, PostingList> here, so that would be Token.Data.size() which is the size of std::string stored in Token (e.g. trigram symbols for Trigram tokens, directory URI for ProximityPath tokens, etc). P is probably bad here, I'll change the naming to be more explicit.

[lebedev.ri]

clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp

84

divide the number of iterations by IterationTime

And more unsolicited advices:
[[ https://github.com/google/benchmark/blob/1b44120cd16712f3b5decd95dc8ff2813574b273/include/benchmark/benchmark.h#L366-L368 | kIsIterationInvariantRate ]], but it is master-only, not in any release.
For now, do

State.counters["kIsIterationInvariantRate"] = benchmark::Counter(
                                                state.iterations(),
                                                benchmark::Counter::Flags::kIsRate);

If understood the question right.

Also, I didn't find any way to manually set the iteration count.

[[ https://github.com/google/benchmark/blob/1b44120cd16712f3b5decd95dc8ff2813574b273/include/benchmark/benchmark.h#L853-L859 | benchmark::Benchmark::Iterations() ]]

[kbobyrev]

• Be more explicit about the nature of "benchmarks" with memory tracking logic via State::SetLabel(...).
• Force single iteration for "benchmarks" with memory usage tracking
• Add another "benchmark" with Dex memory overhead over plain SymbolSlab

Huge thanks to @lebedev.ri for helping! This looks much better to me now.

[ioeric]

clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp

82

Why did we move this benchmark (DexQueries)? It seems unnecessary.

101

nit: maybe divide by 1000.0 to avoid precision loss?

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

187 ↗

(On Diff #166481)

Could you put this near the old loadIndex to preserve the revision history?

[sammccall]

This change does several things, and I think most of them need further thought. Can we discuss Monday?

clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp

91

This looks like it'll be really stable, why does it need to be a benchmark vs say a dexp subcommand?

[kbobyrev]

Don't include misc changes elsewhere: focus on adding more benchmarks in this revision.

clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp

91

As discussed offline, this is meant to make it easier for people to investigate memory + performance changes and simplify the development pipeline as opposed to remembering multiple binaries and their options and running all these binaries after each change.

[kbobyrev]

Pass data from I/O to readIndexFile(StringRef).

clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp

 std::unique_ptr<SymbolIndex> buildMem() {
   return loadIndex(IndexFilename, {}, false);
 }
 
 std::unique_ptr<SymbolIndex> buildDex() {
   return loadIndex(IndexFilename, {}, true);
 }
 
+SymbolSlab loadSlab() {
+  auto IndexFile = readIndexFile(IndexFilename);
+  if (!IndexFile) {
+    llvm::errs() << llvm::toString(IndexFile.takeError()) << '\n';
+    exit(1);
+  } else if (!IndexFile->Symbols) {
+    llvm::errs() << "Couldn't read symbol slab from the index file: "
+                 << IndexFilename << '\n';
+    exit(1);
+  }
+  return std::move(*IndexFile->Symbols);
+}
+
 // Reads JSON array of serialized FuzzyFindRequest's from user-provided file.
 std::vector<FuzzyFindRequest> extractQueriesFromLogs() {
   std::ifstream InputStream(RequestsFilename);
   std::string Log((std::istreambuf_iterator<char>(InputStream)),
                   std::istreambuf_iterator<char>());
 
   std::vector<FuzzyFindRequest> Requests;
   auto JSONArray = llvm::json::parse(Log);
if (!fromJSON(Item, Request)) {
       llvm::errs() << "Error when deserializing request: " << Item << '\n';
       exit(1);
     }
     Requests.push_back(Request);
   }
   return Requests;
 }
 
 static void MemQueries(benchmark::State &State) {
   const auto Mem = buildMem();
   const auto Requests = extractQueriesFromLogs();
   for (auto _ : State)
     for (const auto &Request : Requests)
       Mem->fuzzyFind(Request, [](const Symbol &S) {});
 }
-BENCHMARK(MemQueries);
+BENCHMARK(MemQueries)->Unit(benchmark::kMillisecond);
 
 static void DexQueries(benchmark::State &State) {
   const auto Dex = buildDex();
   const auto Requests = extractQueriesFromLogs();
   for (auto _ : State)
     for (const auto &Request : Requests)
       Dex->fuzzyFind(Request, [](const Symbol &S) {});
 }
-BENCHMARK(DexQueries);
+BENCHMARK(DexQueries)->Unit(benchmark::kMillisecond);
+
+// This is not a *real* benchmark: it shows size of built MemIndex (in bytes).
+// Same for the next "benchmark".
+// FIXME(kbobyrev): Track memory usage caused by different index parts:
+// SymbolSlab and RefSlabs, InverseIndex, PostingLists of different types for
+// Dex, etc.
+static void MemSize(benchmark::State &State) {
+  const auto Mem = buildMem();
+  for (auto _ : State)
+    // Divide size of Mem by 1000 so that it will be correctly displayed in the
+    // benchmark report (possible options for time units are ms, ns and us).
+    State.SetIterationTime(/*double Seconds=*/Mem->estimateMemoryUsage() /
+                           1000.0);
+  State.SetLabel("This tracks in-memory size of MemIndex (SymbolSlab + Index "
+                 "overhead) in bytes");
+}
+BENCHMARK(MemSize)
+    ->UseManualTime()
+    ->Unit(benchmark::kMillisecond)
+    ->Iterations(1);
+
+static void DexSize(benchmark::State &State) {
+  const auto Dex = buildDex();
+
+  for (auto _ : State)
+    State.SetIterationTime(Dex->estimateMemoryUsage() / 1000.0);
+  State.SetLabel("This tracks in-memory size of Dex (SymbolSlab + Index "
+                 "overhead) in bytes");
+}
+BENCHMARK(DexSize)
+    ->UseManualTime()
+    ->Unit(benchmark::kMillisecond)
+    ->Iterations(1);
+
+static void DexOverhead(benchmark::State &State) {
+  const auto Slab = loadSlab();
+  const auto Dex = buildDex();
+  for (auto _ : State)
+    State.SetIterationTime((Dex->estimateMemoryUsage() - Slab.bytes()) /
+                           1000.0);
+  State.SetLabel("This tracks in-memory size of Dex Index overhead (and "
+                 "excludes underlying SymbolSlab size) in bytes");
+}
+BENCHMARK(DexOverhead)
+    ->UseManualTime()
+    ->Unit(benchmark::kMillisecond)
+    ->Iterations(1);
+
+static void SymbolSlabLoading(benchmark::State &State) {
+  for (auto _ : State)
+    benchmark::DoNotOptimize(loadSlab());
+}
+BENCHMARK(SymbolSlabLoading)->Unit(benchmark::kMillisecond);
+
+static void DexBuild(benchmark::State &State) {
+  auto Slab = loadSlab();
+  for (auto _ : State)
+    benchmark::DoNotOptimize(dex::Dex::build(std::move(Slab), {}));
+}
+BENCHMARK(DexBuild)->Unit(benchmark::kMillisecond);
 
 } // namespace
 } // namespace clangd
 } // namespace clang
 
-// FIXME(kbobyrev): Add index building time benchmarks.
-// FIXME(kbobyrev): Add memory consumption "benchmarks" by manually measuring
-// in-memory index size and reporting it as time.
 // FIXME(kbobyrev): Create a logger wrapper to suppress debugging info printer.
 int main(int argc, char *argv[]) {
   if (argc < 3) {
     llvm::errs() << "Usage: " << argv[0]
                  << " global-symbol-index.yaml requests.json "
                     "BENCHMARK_OPTIONS...\n";
     return -1;
   }
   IndexFilename = argv[1];
   RequestsFilename = argv[2];
   // Trim first two arguments of the benchmark invocation and pretend no
   // arguments were passed in the first place.
   argv[2] = argv[0];
   argv += 2;
   argc -= 2;
   ::benchmark::Initialize(&argc, argv);
   ::benchmark::RunSpecifiedBenchmarks();
 }