https://github.com/nickitat updated https://github.com/llvm/llvm-project/pull/237760
>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 1/4] [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; >From 6212c7944b46adaedd8f4b752f3af2c236983ec6 Mon Sep 17 00:00:00 2001 From: Nikita Taranov <[email protected]> Date: Sun, 1 Nov 2026 19:10:57 +0000 Subject: [PATCH 2/4] [clangd] Intern ref file URIs by content in RefSlab::BundleBuilder `BundleBuilder` cached interned file URIs by the caller's pointer for its whole lifetime. A caller that reuses a buffer for a different URI got the first URI back, which breaks the deep-copy contract of `insert`. Intern by content, like `RefSlab::Builder` does. This costs about 0.1 s of the 4.4 s it takes to load a 950 MB index. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- clang-tools-extra/clangd/index/Ref.cpp | 5 +---- clang-tools-extra/clangd/index/Ref.h | 4 ---- .../clangd/unittests/IndexTests.cpp | 20 +++++++++++++++++++ 3 files changed, 21 insertions(+), 8 deletions(-) diff --git a/clang-tools-extra/clangd/index/Ref.cpp b/clang-tools-extra/clangd/index/Ref.cpp index 41bb3de7fb78a1..9a2de4c834ebe5 100644 --- a/clang-tools-extra/clangd/index/Ref.cpp +++ b/clang-tools-extra/clangd/index/Ref.cpp @@ -46,10 +46,7 @@ void RefSlab::BundleBuilder::insert(const SymbolID &ID, 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; + R.Location.FileURI = UniqueStrings.save(R.Location.FileURI).data(); new (&Copy[I]) Ref(R); } llvm::MutableArrayRef<Ref> Stored(Copy, SymbolRefs.size()); diff --git a/clang-tools-extra/clangd/index/Ref.h b/clang-tools-extra/clangd/index/Ref.h index d71d9c7ef916c0..fcd0b6849dfc1d 100644 --- a/clang-tools-extra/clangd/index/Ref.h +++ b/clang-tools-extra/clangd/index/Ref.h @@ -11,7 +11,6 @@ #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" @@ -145,9 +144,6 @@ class RefSlab { 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; }; diff --git a/clang-tools-extra/clangd/unittests/IndexTests.cpp b/clang-tools-extra/clangd/unittests/IndexTests.cpp index 3e790c0b4d8f19..7f8df6d5cdabf5 100644 --- a/clang-tools-extra/clangd/unittests/IndexTests.cpp +++ b/clang-tools-extra/clangd/unittests/IndexTests.cpp @@ -563,6 +563,26 @@ TEST(RefSlabTest, BundleBuilderMatchesBuilder) { } } +TEST(RefSlabTest, BundleBuilderCopiesReusedBuffers) { + // The same buffer holds a different file URI for each insert. + char Buffer[] = "file:///x.cc"; + Ref R; + R.Location.FileURI = Buffer; + RefSlab::BundleBuilder Builder; + Builder.insert(SymbolID("a"), {R}); + Buffer[8] = 'y'; + Builder.insert(SymbolID("b"), {R}); + Buffer[8] = '?'; + RefSlab Slab = std::move(Builder).build(); + llvm::StringMap<SymbolID> FileToSymbol; + for (const auto &[ID, Refs] : Slab) + for (const Ref &Ref : Refs) + FileToSymbol.try_emplace(Ref.Location.FileURI, ID); + EXPECT_EQ(FileToSymbol.size(), 2u); + EXPECT_EQ(FileToSymbol.lookup("file:///x.cc"), SymbolID("a")); + EXPECT_EQ(FileToSymbol.lookup("file:///y.cc"), SymbolID("b")); +} + TEST(MergeIndexTest, IndexedFiles) { SymbolSlab DynSymbols; RefSlab DynRefs; >From 18f244b70b60b266377af482d10c9baac8a5556e Mon Sep 17 00:00:00 2001 From: Nikita Taranov <[email protected]> Date: Sun, 1 Nov 2026 19:26:29 +0000 Subject: [PATCH 3/4] [clangd] Forward the refs map into Dex instead of special-casing rvalues `std::forward` covers both cases: an rvalue map is moved, and an lvalue map of the same type is copied, which is still cheaper than re-inserting every entry. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- clang-tools-extra/clangd/index/dex/Dex.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/clang-tools-extra/clangd/index/dex/Dex.h b/clang-tools-extra/clangd/index/dex/Dex.h index 70551cbb140c04..1b9cbbb62b2050 100644 --- a/clang-tools-extra/clangd/index/dex/Dex.h +++ b/clang-tools-extra/clangd/index/dex/Dex.h @@ -42,10 +42,10 @@ class Dex : public SymbolIndex { for (auto &&Sym : Symbols) this->Symbols.push_back(&Sym); 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); + decltype(this->Refs)>) { + // A map of the right type can be taken as is instead of rehashing every + // entry. + this->Refs = std::forward<RefsRange>(Refs); } else { for (auto &&Ref : Refs) this->Refs.try_emplace(Ref.first, Ref.second); >From a1ed6e4e85c74ca045514be643390a90a65d29f2 Mon Sep 17 00:00:00 2001 From: Nikita Taranov <[email protected]> Date: Sun, 1 Nov 2026 19:29:49 +0000 Subject: [PATCH 4/4] [clangd] Take the Dex refs fast path whenever the map is assignable Check that the refs argument can be assigned to the map instead of requiring the exact map type. `Dex::build` still passes a `RefSlab`, which is not assignable and keeps using the loop. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- clang-tools-extra/clangd/index/dex/Dex.h | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) diff --git a/clang-tools-extra/clangd/index/dex/Dex.h b/clang-tools-extra/clangd/index/dex/Dex.h index 1b9cbbb62b2050..c106a16aba5c84 100644 --- a/clang-tools-extra/clangd/index/dex/Dex.h +++ b/clang-tools-extra/clangd/index/dex/Dex.h @@ -41,10 +41,8 @@ class Dex : public SymbolIndex { : Corpus(0) { for (auto &&Sym : Symbols) this->Symbols.push_back(&Sym); - if constexpr (std::is_same_v<std::decay_t<RefsRange>, - decltype(this->Refs)>) { - // A map of the right type can be taken as is instead of rehashing every - // entry. + if constexpr (std::is_assignable_v<decltype(this->Refs) &, RefsRange>) { + // Take a map that can be assigned as is instead of rehashing every entry. this->Refs = std::forward<RefsRange>(Refs); } else { for (auto &&Ref : Refs) _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
