kbobyrev created this revision. kbobyrev added reviewers: ioeric, ilya-biryukov, sammccall. kbobyrev added a project: clang-tools-extra. Herald added subscribers: kadircet, arphaman, jkorous, MaskRay, mgorny.
This patch introduces index benchmarks on top of the proposed LLVM benchmark pull. The preliminary results are here (benchmark invocation is given LLVM + Clang + Clang-Tools-Extra + libc++ symbol database): 2018-08-22 11:12:34 Run on (72 X 3700 MHz CPU s) CPU Caches: L1 Data 32K (x36) L1 Instruction 32K (x36) L2 Unified 1024K (x36) L3 Unified 25344K (x2) ------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------ BuildMem 6042296009 ns 6041974540 ns 1 MemAdHocQueries 117140353 ns 117134140 ns 6 BuildDex 8902015670 ns 8901575912 ns 1 DexAdHocQueries 5137288 ns 5137076 ns 132 Dex is about 22 times faster compared to MemIndex despite actually processing 100x more items since `ItemsToRetrieve = 100 * Req.MaxCandidateCount`. When setting `ItemsToRetrieve = Req.MaxCandidateCount`, it is up to 1000x faster. https://reviews.llvm.org/D51090 Files: clang-tools-extra/clangd/CMakeLists.txt clang-tools-extra/clangd/benchmarks/CMakeLists.txt clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp clang-tools-extra/clangd/index/SymbolYAML.cpp clang-tools-extra/clangd/index/SymbolYAML.h clang-tools-extra/clangd/index/dex/DexIndex.cpp clang-tools-extra/clangd/tool/ClangdMain.cpp
Index: clang-tools-extra/clangd/tool/ClangdMain.cpp =================================================================== --- clang-tools-extra/clangd/tool/ClangdMain.cpp +++ clang-tools-extra/clangd/tool/ClangdMain.cpp @@ -38,24 +38,6 @@ 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( @@ -294,7 +276,7 @@ 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; Index: clang-tools-extra/clangd/index/dex/DexIndex.cpp =================================================================== --- clang-tools-extra/clangd/index/dex/DexIndex.cpp +++ clang-tools-extra/clangd/index/dex/DexIndex.cpp @@ -161,7 +161,6 @@ } } - void DexIndex::findOccurrences( const OccurrencesRequest &Req, llvm::function_ref<void(const SymbolOccurrence &)> Callback) const { Index: clang-tools-extra/clangd/index/SymbolYAML.h =================================================================== --- clang-tools-extra/clangd/index/SymbolYAML.h +++ clang-tools-extra/clangd/index/SymbolYAML.h @@ -42,6 +42,12 @@ // 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 Index: clang-tools-extra/clangd/index/SymbolYAML.cpp =================================================================== --- clang-tools-extra/clangd/index/SymbolYAML.cpp +++ clang-tools-extra/clangd/index/SymbolYAML.cpp @@ -9,6 +9,7 @@ #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" @@ -203,5 +204,21 @@ 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 Index: clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp =================================================================== --- /dev/null +++ clang-tools-extra/clangd/benchmarks/IndexBenchmark.cpp @@ -0,0 +1,93 @@ +//===--- 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 "benchmark/benchmark.h" + +// 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::string IndexFilename; + +void initializeEnvironment(char *argv[]) { + IndexFilename = argv[1]; + + 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 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); + +} // 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 < 2) { + llvm::errs() << "Usage: " << argv[0] + << " global-symbol-index.yaml 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(); +} Index: clang-tools-extra/clangd/benchmarks/CMakeLists.txt =================================================================== --- /dev/null +++ clang-tools-extra/clangd/benchmarks/CMakeLists.txt @@ -0,0 +1,2 @@ +add_executable(IndexBenchmark IndexBenchmark.cpp) +target_link_libraries(IndexBenchmark benchmark clangDaemon LLVMSupport) Index: clang-tools-extra/clangd/CMakeLists.txt =================================================================== --- clang-tools-extra/clangd/CMakeLists.txt +++ clang-tools-extra/clangd/CMakeLists.txt @@ -71,3 +71,7 @@ endif() add_subdirectory(tool) add_subdirectory(global-symbol-builder) + +if (LLVM_BUILD_BENCHMARKS) + add_subdirectory(benchmarks) +endif()
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits