[clangd] Add index benchmarks

[kbobyrev]

Summary

This patch introduces index benchmarks on top of the proposed LLVM benchmark pull.

[kbobyrev]

The current diff is rather messy and it is also blocked by the parent revision (D50894). It is likely to change if the parent CMake structure is changed.

[kbobyrev]

Rebase on top of parent patch.

[kbobyrev]

• Rebase on top of new code
• Simplify code structure and get rid of global state (except for two filenames coming from main())

The only problem now is that the generated output contains log strings (e.g. "Built DexIndex with estimated memory usage 63445392 bytes.", see example in the Summary), I should find a way to deal with that (since it's rather annoying). It's also the case for the dexplorer tool.

[kbobyrev]

Sync with HEAD

[sammccall]

Nice and simple :-) Looks good, just some details.

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

2

rename? (it's not just dex now, right?)

22

const char* (no globals with nontrivial constructors/destructors)

26

these should be in ns clang::clangd::<anonymous> I think?

27

This includes reading the file contents, which I'm not sure is a useful part of the BuildDex() benchmark.

You could consider splitting into loadIndex that takes content and loadIndexFromFile that takes a filename. The former would be more appropriate to time.

34

comment?

66

this seems a little weird - the extractQueriesFromLogs/buildDex seem to be agnostic to the index contents, but here we assume knowledge of it being LLVM.

The former model is nicer, and we can extend it by using the JSON representation to add more query attributes. Can we drop this function, and ArtificialQueries->Queries?

105

remove dex if this isn't dex-specific?

133

BTW this also counts *destruction* time. I think that's fine, though.

[kbobyrev]

Address few comments (not all of them for now, though).

[kbobyrev]

The only problem left is that I'm not sure how to run binary which is not under bin (IndexBenchmark) using llvm-lit.

[lebedev.ri]

In D51090#1230579, @kbobyrev wrote:

The only problem left is that I'm not sure how to run binary which is not under bin (IndexBenchmark) using llvm-lit.

But it's a benchmark.. What use could be from running it as part of the _tests_?
For test-suite (lnt) integration, i'm not sure.

[kbobyrev]

Find a hacky workaround to call IndexBenchmark binary.

[sammccall]

In D51090#1230582, @lebedev.ri wrote:

In D51090#1230579, @kbobyrev wrote:

The only problem left is that I'm not sure how to run binary which is not under bin (IndexBenchmark) using llvm-lit.

But it's a benchmark.. What use could be from running it as part of the _tests_?
For test-suite (lnt) integration, i'm not sure.

Same as any other binary that isn't itself a test - make sure it works :-)
(Mostly just that it doesn't crash)

clang-tools-extra/test/clangd/benchmark-dummy.test

1 ↗

(On Diff #164887)

i'd call this index-tools.test - it's a good integration test for global-symbol-builder, better when we add dexp to the test to verify the output.

[lebedev.ri]

In D51090#1230629, @sammccall wrote:

In D51090#1230582, @lebedev.ri wrote:

In D51090#1230579, @kbobyrev wrote:

The only problem left is that I'm not sure how to run binary which is not under bin (IndexBenchmark) using llvm-lit.

But it's a benchmark.. What use could be from running it as part of the _tests_?
For test-suite (lnt) integration, i'm not sure.

Same as any other binary that isn't itself a test - make sure it works :-)
(Mostly just that it doesn't crash)

Then you don't actually care about the measurements, do you?
It would be a great idea to add --benchmark_min_time=0.01 so it does not actually try to measure anything good.

[kbobyrev]

Add --benchmark_min_time=0.01 to prevent testing time increase.

[lebedev.ri]

In D51090#1230659, @kbobyrev wrote:

Add --benchmark_min_time=0.01 to prevent testing time increase.

Thanks!

clang-tools-extra/clangd/CMakeLists.txt

add_clang_library(clangDaemon
   ${CLANGD_ATOMIC_LIB}
   )
 
 if( LLVM_LIB_FUZZING_ENGINE OR LLVM_USE_SANITIZE_COVERAGE )
   add_subdirectory(fuzzer)
 endif()
 add_subdirectory(tool)
 add_subdirectory(global-symbol-builder)
+
+if (LLVM_INCLUDE_BENCHMARKS)
+  add_subdirectory(benchmarks)
+endif()

clang-tools-extra/clangd/benchmarks/CMakeLists.txt

+include_directories(${CMAKE_CURRENT_SOURCE_DIR}/../)
+
+add_benchmark(IndexBenchmark IndexBenchmark.cpp)
+
+target_link_libraries(IndexBenchmark
+  PRIVATE
+  clangDaemon
+  LLVMSupport
+  )

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

+//===--- DexBenchmark.cpp - DexIndex benchmarks -----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../index/SymbolYAML.h"
+#include "../index/dex/DexIndex.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Regex.h"
+#include "benchmark/benchmark.h"
+#include <string>
+#include <fstream>
+#include <streambuf>
+
+// FIXME(kbobyrev): Get rid of global variables and put them into
+// benchmark::State?
+std::unique_ptr<clang::clangd::SymbolIndex> Dex;
+std::unique_ptr<clang::clangd::SymbolIndex> Mem;
+
+std::vector<clang::clangd::FuzzyFindRequest> Requests;
+
+std::vector<clang::clangd::FuzzyFindRequest> RealRequests;
+
+std::string IndexFilename;
+std::string LogFilename;
+
+void readLogFile() {
+  llvm::Regex RequestMatcher("fuzzyFind\\(\"([a-zA-Z]*)\", scopes=\\[(.*)\\]");
+  llvm::SmallVector<llvm::StringRef, 200> Matches;
+  std::ifstream InputStream(LogFilename);
+  std::string Log((std::istreambuf_iterator<char>(InputStream)),
+                  std::istreambuf_iterator<char>());
+  llvm::StringRef S = Log;
+  llvm::SmallVector<llvm::StringRef, 200> Strings;
+  S.split(Strings, '\n');
+
+  clang::clangd::FuzzyFindRequest R;
+  R.MaxCandidateCount = 100;
+
+  llvm::SmallVector<llvm::StringRef, 200> CSS;
+
+  for (auto Line : Strings) {
+    if (RequestMatcher.match(Line, &Matches)) {
+      R.Query = Matches[1];
+      CSS.clear();
+      Line.split(CSS, ',');
+      R.Scopes.clear();
+      for (auto C : CSS) {
+        R.Scopes.push_back(C);
+      }
+      RealRequests.push_back(R);
+    }
+  }
+  llvm::outs() << "Generated " << RealRequests.size() << " requests.\n";
+}
+
+void initializeEnvironment(char *argv[]) {
+  IndexFilename = argv[1];
+  LogFilename = argv[2];
+
+  readLogFile();
+
+  Dex = clang::clangd::buildStaticIndex(IndexFilename, true);
+  Mem = clang::clangd::buildStaticIndex(IndexFilename, false);
+
+  // FXIME(kbobyrev): Add more requests.
+  clang::clangd::FuzzyFindRequest R;
+  R.MaxCandidateCount = 100;
+  Requests.push_back(R);
+  R.Scopes = {"::"};
+  Requests.push_back(R);
+  R.Scopes = {"::", "llvm::", "clang::", "clangd::"};
+  Requests.push_back(R);
+  R.Scopes = {"::", "clang::", "llvm::", "std::"};
+  R.Query = "TUDec";
+  Requests.push_back(R);
+  R.Query = "non-existent symbol";
+  Requests.push_back(R);
+}
+
+namespace clang {
+namespace clangd {
+namespace dex {
+
+static void BuildMem(benchmark::State &State) {
+  for (auto _ : State)
+    Mem = clang::clangd::buildStaticIndex(IndexFilename, false);
+}
+BENCHMARK(BuildMem);
+
+static void MemAdHocQueries(benchmark::State &State) {
+  for (auto _ : State)
+    for (const auto Req : Requests)
+      Mem->fuzzyFind(Req, [](const Symbol &S) {});
+}
+BENCHMARK(MemAdHocQueries);
+
+static void MemRealQ(benchmark::State &State) {
+  for (auto _ : State)
+    for (const auto Req : RealRequests)
+      Mem->fuzzyFind(Req, [](const Symbol &S) {});
+}
+BENCHMARK(MemRealQ);
+
+static void BuildDex(benchmark::State &State) {
+  for (auto _ : State)
+    Dex = clang::clangd::buildStaticIndex(IndexFilename, true);
+}
+BENCHMARK(BuildDex);
+
+static void DexAdHocQueries(benchmark::State &State) {
+  for (auto _ : State)
+    for (const auto Req : Requests)
+      Dex->fuzzyFind(Req, [](const Symbol &S) {});
+}
+BENCHMARK(DexAdHocQueries);
+
+static void DexRealQ(benchmark::State &State) {
+  for (auto _ : State)
+    for (const auto Req : RealRequests)
+      Dex->fuzzyFind(Req, [](const Symbol &S) {});
+}
+BENCHMARK(DexRealQ);
+
+} // namespace dex
+} // namespace clangd
+} // namespace clang
+
+// FIXME(kbobyrev): Extract fuzzyFind requests from the user logs (-log=verbose)
+// and add a separate benchmark target for a bunch of user-provided fuzzy find
+// requests.
+int main(int argc, char *argv[]) {
+  if (argc < 3) {
+    llvm::errs() << "Usage: " << argv[0]
+                 << " global-symbol-index.yaml fuzzy-find-requests.log BENCHMARK_OPTIONS...\n";
+    return -1;
+  }
+  initializeEnvironment(argv);
+  // Trim first two arguments of the benchmark invocation.
+  argv += 2;
+  argc -= 2;
+  ::benchmark::Initialize(&argc, argv);
+  ::benchmark::RunSpecifiedBenchmarks();
+}

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

 // Convert a single symbol to YAML-format string.
 // The YAML result is safe to concatenate.
 std::string SymbolToYAML(Symbol Sym);
 
 // Convert symbols to a YAML-format string.
 // The YAML result is safe to concatenate if you have multiple symbol slabs.
 void SymbolsToYAML(const SymbolSlab &Symbols, llvm::raw_ostream &OS);
 
+// Build an in-memory static index for global symbols from a YAML-format file.
+// The size of global symbols should be relatively small, so that all symbols
+// can be managed in memory.
+std::unique_ptr<SymbolIndex> buildStaticIndex(llvm::StringRef YamlSymbolFile,
+                                              bool UseDex);
+
 } // namespace clangd
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANGD_INDEX_SYMBOL_FROM_YAML_H

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

 //===--- SymbolYAML.cpp ------------------------------------------*- C++-*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SymbolYAML.h"
 #include "Index.h"
+#include "dex/DexIndex.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 
 LLVM_YAML_IS_DOCUMENT_LIST_VECTOR(clang::clangd::Symbol)
 
 namespace llvm {

 std::string SymbolToYAML(Symbol Sym) {
   std::string Str;
   llvm::raw_string_ostream OS(Str);
   llvm::yaml::Output Yout(OS);
   Yout << Sym;
   return OS.str();
 }
 
+std::unique_ptr<SymbolIndex> buildStaticIndex(llvm::StringRef YamlSymbolFile,
+                                              bool UseDex) {
+  auto Buffer = llvm::MemoryBuffer::getFile(YamlSymbolFile);
+  if (!Buffer) {
+    llvm::errs() << "Can't open " << YamlSymbolFile << "\n";
+    return nullptr;
+  }
+  auto Slab = symbolsFromYAML(Buffer.get()->getBuffer());
+  SymbolSlab::Builder SymsBuilder;
+  for (auto Sym : Slab)
+    SymsBuilder.insert(Sym);
+
+  return UseDex ? dex::DexIndex::build(std::move(SymsBuilder).build())
+                : MemIndex::build(std::move(SymsBuilder).build());
+}
+
 } // namespace clangd
 } // namespace clang

clang-tools-extra/clangd/tool/ClangdMain.cpp

static llvm::cl::opt<bool>
     UseDex("use-dex-index",
            llvm::cl::desc("Use experimental Dex static index."),
            llvm::cl::init(false), llvm::cl::Hidden);
 
 namespace {
 
 enum class PCHStorageFlag { Disk, Memory };
 
-// Build an in-memory static index for global symbols from a YAML-format file.
-// The size of global symbols should be relatively small, so that all symbols
-// can be managed in memory.
-std::unique_ptr<SymbolIndex> buildStaticIndex(llvm::StringRef YamlSymbolFile) {
-  auto Buffer = llvm::MemoryBuffer::getFile(YamlSymbolFile);
-  if (!Buffer) {
-    llvm::errs() << "Can't open " << YamlSymbolFile << "\n";
-    return nullptr;
-  }
-  auto Slab = symbolsFromYAML(Buffer.get()->getBuffer());
-  SymbolSlab::Builder SymsBuilder;
-  for (auto Sym : Slab)
-    SymsBuilder.insert(Sym);
-
-  return UseDex ? dex::DexIndex::build(std::move(SymsBuilder).build())
-                : MemIndex::build(std::move(SymsBuilder).build());
-}
-
 } // namespace
 
 static llvm::cl::opt<Path> CompileCommandsDir(
     "compile-commands-dir",
     llvm::cl::desc("Specify a path to look for compile_commands.json. If path "
                    "is invalid, clangd will look in the current directory and "
                    "parent paths of each source file."));
 
case PCHStorageFlag::Disk:
     Opts.StorePreamblesInMemory = false;
     break;
   }
   if (!ResourceDir.empty())
     Opts.ResourceDir = ResourceDir;
   Opts.BuildDynamicSymbolIndex = EnableIndex;
   std::unique_ptr<SymbolIndex> StaticIdx;
   if (EnableIndex && !YamlSymbolFile.empty()) {
-    StaticIdx = buildStaticIndex(YamlSymbolFile);
+    StaticIdx = buildStaticIndex(YamlSymbolFile, UseDex);
     Opts.StaticIndex = StaticIdx.get();
   }
   Opts.AsyncThreadsCount = WorkerThreadsCount;
 
   clangd::CodeCompleteOptions CCOpts;
   CCOpts.IncludeIneligibleResults = IncludeIneligibleResults;
   CCOpts.Limit = LimitResults;
   CCOpts.BundleOverloads = CompletionStyle != Detailed;