https://github.com/nickitat created https://github.com/llvm/llvm-project/pull/237760
On a large project, loading the background index at startup takes several seconds before clangd can answer index-backed requests. A profile of that load on ClickHouse (17k TUs, 41k shards, 447 MB index) showed two easy hot spots: - **`Dex` re-inserted the whole refs map.** `FileSymbols::buildIndex` builds a `DenseMap<SymbolID, ArrayRef<Ref>>` and passes it by rvalue, and the `Dex` constructor copied it entry by entry into its own map of the same type. It now takes the map over. This was 18.6% of the load. - **Refs read from disk went through `RefSlab::Builder`.** That builder interns the file URI and inserts into a `DenseSet` for every single ref, and then sorts everything again (the `FIXME: bulk insert?` in `readRIFF`). Refs on disk are already grouped by symbol, so the new `RefSlab::BundleBuilder` takes whole per-symbol bundles, interns each URI once per distinct string, and keeps the existing order. If a symbol appears in more than one bundle it falls back to `RefSlab::Builder`, so the result is the same either way. This was about 12% of the load. ### Results Time from `Enqueueing N commands for indexing` to serving the index loaded from disk, with a warm page cache, 4 alternating runs each: | | load shards | build + serve | total | |---|---|---|---| | main (e0a86c11efad) | 2.0-2.1 s | 3.4-3.5 s | 5.4-5.6 s | | this PR | 1.5 s | 2.5-2.6 s | 4.0-4.1 s | `workspace/symbol` results for 7 queries and `textDocument/references` results for 4 symbols (up to 19,839 refs) are identical before and after. ### Testing - New `RefSlabTest.BundleBuilderMatchesBuilder` checks that `BundleBuilder` produces the same slab as `Builder`, including unsorted input, a symbol split across bundles, and string ownership. - `SerializationTest.BinaryConversions` already round-trips refs through `readRIFF`. - All 1505 `ClangdTests` pass locally. ### What's left After this change, loading is split roughly evenly between reading shards (single-threaded), merging refs in `FileSymbols::buildIndex` (mostly sorting each symbol's refs), and building the `Dex` posting lists. I'm planning to follow up with loading shards in parallel. 🤖 Generated with [Claude Code](https://claude.com/claude-code) >From 07d52699e1b110c4eb1a5cdd2ca059dcc1ea823f Mon Sep 17 00:00:00 2001 From: Nikita Taranov <[email protected]> Date: Sun, 1 Nov 2026 18:34:41 +0000 Subject: [PATCH] [clangd] Speed up loading the background index from disk Two hot spots showed up when profiling how clangd loads a large background index (17k TUs, 41k shards, 447 MB) at startup: - `Dex` re-inserted every entry of the refs map built by `FileSymbols::buildIndex` into its own `DenseMap` of the same type. It now takes the map over when it is passed by rvalue. This was 18.6% of the load. - Refs read from an index file went through `RefSlab::Builder`, which interns the file URI and inserts into a `DenseSet` for every ref, then sorts everything again. Refs on disk are already grouped by symbol, so add `RefSlab::BundleBuilder`, which takes whole per-symbol bundles, interns each URI once per distinct string, and keeps the existing order. If a symbol appears in several bundles it falls back to `RefSlab::Builder`, so the result is the same. This was about 12% of the load. Time from enqueueing the project to serving the loaded index, on a warm page cache: 5.4-5.6 s before, 4.0-4.1 s after (-26%). Results of `workspace/symbol` and `textDocument/references` queries are identical. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- clang-tools-extra/clangd/index/Ref.cpp | 39 +++++++++++++++ clang-tools-extra/clangd/index/Ref.h | 21 ++++++++ .../clangd/index/Serialization.cpp | 5 +- clang-tools-extra/clangd/index/dex/Dex.h | 11 ++++- .../clangd/unittests/IndexTests.cpp | 49 +++++++++++++++++++ 5 files changed, 120 insertions(+), 5 deletions(-) diff --git a/clang-tools-extra/clangd/index/Ref.cpp b/clang-tools-extra/clangd/index/Ref.cpp index edbfb95b528400..41bb3de7fb78a1 100644 --- a/clang-tools-extra/clangd/index/Ref.cpp +++ b/clang-tools-extra/clangd/index/Ref.cpp @@ -39,6 +39,45 @@ void RefSlab::Builder::insert(const SymbolID &ID, const Ref &S) { Entries.insert(std::move(E)); } +void RefSlab::BundleBuilder::insert(const SymbolID &ID, + llvm::ArrayRef<Ref> SymbolRefs) { + if (SymbolRefs.empty()) + return; + Ref *Copy = Arena.Allocate<Ref>(SymbolRefs.size()); + for (size_t I = 0; I < SymbolRefs.size(); ++I) { + Ref R = SymbolRefs[I]; + const char *&Interned = InternedURIs[R.Location.FileURI]; + if (!Interned) + Interned = UniqueStrings.save(R.Location.FileURI).data(); + R.Location.FileURI = Interned; + new (&Copy[I]) Ref(R); + } + llvm::MutableArrayRef<Ref> Stored(Copy, SymbolRefs.size()); + if (!llvm::is_sorted(Stored)) + llvm::sort(Stored); // By file, affects xrefs display order. + Refs.emplace_back(ID, Stored); + NumRefs += SymbolRefs.size(); +} + +RefSlab RefSlab::BundleBuilder::build() && { + // Keep the invariant of Builder: sorted by SymbolID, one entry per symbol. + if (!llvm::is_sorted(Refs, llvm::less_first())) + llvm::stable_sort(Refs, llvm::less_first()); + std::vector<value_type> Merged; + bool HasDuplicates = false; + for (size_t I = 1; I < Refs.size() && !HasDuplicates; ++I) + HasDuplicates = Refs[I - 1].first == Refs[I].first; + if (!HasDuplicates) + return RefSlab(std::move(Refs), std::move(Arena), NumRefs); + // Rare: the same symbol appeared in several bundles. Fall back to Builder, + // which also removes duplicate refs. + Builder B; + for (const auto &[ID, SymbolRefs] : Refs) + for (const Ref &R : SymbolRefs) + B.insert(ID, R); + return std::move(B).build(); +} + RefSlab RefSlab::Builder::build() && { std::vector<std::pair<SymbolID, llvm::ArrayRef<Ref>>> Result; // We'll reuse the arena, as it only has unique strings and we need them all. diff --git a/clang-tools-extra/clangd/index/Ref.h b/clang-tools-extra/clangd/index/Ref.h index b71f09611fed1f..d71d9c7ef916c0 100644 --- a/clang-tools-extra/clangd/index/Ref.h +++ b/clang-tools-extra/clangd/index/Ref.h @@ -11,6 +11,7 @@ #include "index/SymbolID.h" #include "index/SymbolLocation.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Hashing.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/StringSaver.h" @@ -131,6 +132,26 @@ class RefSlab { sizeof(value_type) * Refs.capacity(); } + /// Builds a RefSlab from refs that are already grouped by symbol, such as + /// the ones read from an index file. Unlike Builder, does not deduplicate + /// individual refs, which makes it much cheaper. + class BundleBuilder { + public: + BundleBuilder() : UniqueStrings(Arena) {} + /// Adds all refs of \p ID. Deep copy: strings will be owned by the slab. + void insert(const SymbolID &ID, llvm::ArrayRef<Ref> SymbolRefs); + RefSlab build() &&; + + private: + llvm::BumpPtrAllocator Arena; + llvm::UniqueStringSaver UniqueStrings; // Contents on the arena. + /// Input FileURI pointer -> interned copy. The input usually points into + /// a string table, so most lookups hit without hashing the string. + llvm::DenseMap<const char *, const char *> InternedURIs; + std::vector<value_type> Refs; + size_t NumRefs = 0; + }; + /// RefSlab::Builder is a mutable container that can 'freeze' to RefSlab. class Builder { public: diff --git a/clang-tools-extra/clangd/index/Serialization.cpp b/clang-tools-extra/clangd/index/Serialization.cpp index 764ec7903aecb9..508c9783e74e0f 100644 --- a/clang-tools-extra/clangd/index/Serialization.cpp +++ b/clang-tools-extra/clangd/index/Serialization.cpp @@ -518,11 +518,10 @@ llvm::Expected<IndexFileIn> readRIFF(llvm::StringRef Data, } if (Chunks.count("refs")) { Reader RefsReader(Chunks.lookup("refs")); - RefSlab::Builder Refs; + RefSlab::BundleBuilder Refs; while (!RefsReader.eof()) { auto RefsBundle = readRefs(RefsReader, Strings->Strings); - for (const auto &Ref : RefsBundle.second) // FIXME: bulk insert? - Refs.insert(RefsBundle.first, Ref); + Refs.insert(RefsBundle.first, RefsBundle.second); } if (RefsReader.err()) return error("malformed or truncated refs"); diff --git a/clang-tools-extra/clangd/index/dex/Dex.h b/clang-tools-extra/clangd/index/dex/Dex.h index 1ea7d8c06c67c5..70551cbb140c04 100644 --- a/clang-tools-extra/clangd/index/dex/Dex.h +++ b/clang-tools-extra/clangd/index/dex/Dex.h @@ -41,8 +41,15 @@ class Dex : public SymbolIndex { : Corpus(0) { for (auto &&Sym : Symbols) this->Symbols.push_back(&Sym); - for (auto &&Ref : Refs) - this->Refs.try_emplace(Ref.first, Ref.second); + if constexpr (std::is_same_v<std::decay_t<RefsRange>, + decltype(this->Refs)> && + !std::is_lvalue_reference_v<RefsRange>) { + // Take over a map of the right type instead of rehashing every entry. + this->Refs = std::move(Refs); + } else { + for (auto &&Ref : Refs) + this->Refs.try_emplace(Ref.first, Ref.second); + } for (auto &&Rel : Relations) { this->Relations[std::make_pair(Rel.Subject, static_cast<uint8_t>(Rel.Predicate))] diff --git a/clang-tools-extra/clangd/unittests/IndexTests.cpp b/clang-tools-extra/clangd/unittests/IndexTests.cpp index a66680d39c87d2..3e790c0b4d8f19 100644 --- a/clang-tools-extra/clangd/unittests/IndexTests.cpp +++ b/clang-tools-extra/clangd/unittests/IndexTests.cpp @@ -514,6 +514,55 @@ TEST(MergeIndexTest, Refs) { fileURI("unittest:///test2.cc")))))); } +TEST(RefSlabTest, BundleBuilderMatchesBuilder) { + SymbolID A("a"), B("b"), C("c"); + std::string FileX = "file:///x.cc", FileY = "file:///y.cc"; + auto MakeRef = [](const std::string &File, uint32_t Line) { + Ref R; + R.Location.FileURI = File.c_str(); + R.Location.Start.setLine(Line); + R.Location.End.setLine(Line); + R.Kind = RefKind::Reference; + return R; + }; + // Bundles out of SymbolID order, refs out of order within a bundle, and + // symbol C split over two bundles that share a ref. + std::vector<std::pair<SymbolID, std::vector<Ref>>> Bundles = { + {B, {MakeRef(FileY, 2), MakeRef(FileX, 1)}}, + {C, {MakeRef(FileX, 5)}}, + {A, {MakeRef(FileX, 3)}}, + {C, {MakeRef(FileY, 4), MakeRef(FileX, 5)}}, + }; + auto Build = [&](bool WithDuplicateSymbol) { + RefSlab::Builder Expected; + RefSlab::BundleBuilder Actual; + for (const auto &[ID, Refs] : Bundles) { + if (!WithDuplicateSymbol && &Bundles.back().second == &Refs) + continue; + for (const Ref &R : Refs) + Expected.insert(ID, R); + Actual.insert(ID, Refs); + } + return std::make_pair(std::move(Expected).build(), + std::move(Actual).build()); + }; + for (bool WithDuplicateSymbol : {false, true}) { + auto [Expected, Actual] = Build(WithDuplicateSymbol); + // Strings must be owned by the slabs. + std::fill(FileX.begin(), FileX.end(), '?'); + std::fill(FileY.begin(), FileY.end(), '?'); + EXPECT_EQ(Expected.numRefs(), Actual.numRefs()); + ASSERT_EQ(Expected.size(), Actual.size()); + for (size_t I = 0; I < Expected.size(); ++I) { + auto ExpectedIt = Expected.begin() + I, ActualIt = Actual.begin() + I; + EXPECT_EQ(ExpectedIt->first, ActualIt->first); + EXPECT_EQ(ExpectedIt->second, ActualIt->second); + } + FileX = "file:///x.cc"; + FileY = "file:///y.cc"; + } +} + TEST(MergeIndexTest, IndexedFiles) { SymbolSlab DynSymbols; RefSlab DynRefs; _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
