[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

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

+//===--- IndexBenchmark.cpp - Clangd index 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/Dex.h"
+#include "benchmark/benchmark.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/Regex.h"
+#include <fstream>
+#include <streambuf>
+#include <string>
+
+const char *IndexFilename;
+const char *LogFilename;
+
+namespace clang {
+namespace clangd {
+namespace {
+
+std::unique_ptr<clang::clangd::SymbolIndex> buildMem() {
+  return clang::clangd::loadIndex(IndexFilename, {}, false);
+}
+
+std::unique_ptr<clang::clangd::SymbolIndex> buildDex() {
+  return clang::clangd::loadIndex(IndexFilename, {}, true);
+}
+
+// This function processes user-provided Log file with fuzzy find requests in
+// the following format:
+//
+// fuzzyFind("UnqualifiedName", scopes=["clang::", "clang::clangd::"])
+//
+// It constructs vector of FuzzyFindRequests which is later used for the
+// benchmarks.
+std::vector<clang::clangd::FuzzyFindRequest> extractQueriesFromLogs() {
+  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 Temporary(Log);
+  llvm::SmallVector<llvm::StringRef, 200> Strings;
+  Temporary.split(Strings, '\n');
+
+  clang::clangd::FuzzyFindRequest R;
+  R.MaxCandidateCount = 100;
+
+  llvm::SmallVector<llvm::StringRef, 200> CommaSeparatedValues;
+
+  std::vector<clang::clangd::FuzzyFindRequest> RealRequests;
+  for (auto Line : Strings) {
+    if (RequestMatcher.match(Line, &Matches)) {
+      R.Query = Matches[1];
+      CommaSeparatedValues.clear();
+      Line.split(CommaSeparatedValues, ',');
+      R.Scopes.clear();
+      for (auto C : CommaSeparatedValues) {
+        R.Scopes.push_back(C);
+      }
+      RealRequests.push_back(R);
+    }
+  }
+  return RealRequests;
+}
+
+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);
+
+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);
+
+} // 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.
+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;
+  }
+  IndexFilename = argv[1];
+  LogFilename = argv[2];
+  // Trim first two arguments of the benchmark invocation.
+  argv += 3;
+  argc -= 3;
+  ::benchmark::Initialize(&argc, argv);
+  ::benchmark::RunSpecifiedBenchmarks();
+}

clang-tools-extra/test/clangd/Inputs/BenchmarkHeader.h

+namespace clang {
+namespace clangd {
+namespace dex {
+class Dex;
+} // namespace dex
+} // namespace clangd
+} // namespace clang
+
+namespace llvm {
+namespace sys {
+
+int getHostNumPhysicalCores();
+
+} // namespace sys
+} // namespace llvm
+
+namespace {
+int Variable;
+} // namespace

clang-tools-extra/test/clangd/Inputs/BenchmarkSource.cpp

+#include "BenchmarkHeader.h"

clang-tools-extra/test/clangd/Inputs/requests.log

+V[09:08:34.301] Code complete: fuzzyFind("s", scopes=[llvm::])
+V[09:08:34.368] Code complete: fuzzyFind("sy", scopes=[llvm::])
+V[09:08:34.442] Code complete: fuzzyFind("sys", scopes=[llvm::])
+V[09:09:12.075] Code complete: fuzzyFind("Dex", scopes=[clang::clangd::, clang::, clang::clangd::dex::])
+V[09:09:12.075] Code complete: fuzzyFind("Variable", scopes=[])

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

+# RUN: global-symbol-builder %p/Inputs/BenchmarkSource.cpp -- -I%p/Inputs > %t.index
+# RUN: %clangd-benchmark-dir/IndexBenchmark %t.index %p/Inputs/requests.log

clang-tools-extra/test/lit.cfg

if config.clang_staticanalyzer:
     run_clang_tidy = os.path.join(
         config.test_source_root, "..", "clang-tidy", "tool", "run-clang-tidy.py")
     config.substitutions.append(
         ('%run_clang_tidy',
          '%s %s' % (config.python_executable, run_clang_tidy)) )
 else:
     # exclude the clang-tidy test directory
     config.excludes.append('clang-tidy')
+
+clangd_benchmarks_dir = os.path.join(os.path.dirname(config.clang_tools_dir),
+                                     "tools", "clang", "tools", "extra",
+                                     "clangd", "benchmarks")
+config.substitutions.append(('%clangd-benchmark-dir',
+                             '%s' % (clangd_benchmarks_dir)))