llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-tools-extra Author: Nikita Taranov (nickitat) <details> <summary>Changes</summary> 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 on disk) 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 assigns the argument to its map directly (here: moves it) whenever that assignment compiles, and keeps the loop for other ranges such as the `RefSlab` from `Dex::build`. 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 (index files are written from a `RefSlab`, one bundle per symbol), so the new `RefSlab::BundleBuilder` takes whole per-symbol bundles, skipping the per-ref `DenseSet`. It sorts bundles and refs only if they are out of order, which happens for a file written on a host of the other endianness, since `SymbolID::operator<` compares the hash as a native integer. `readRIFF` checks for decoding errors right after each bundle and rejects a symbol with refs in more than one bundle as malformed. This was about 12% of the load. Master is in fact tolerant to endianness mismatch, so it was addressed to avoid breaking backward compatibility. If nobody finds this case important, I'd be happy to remove the related code. ### Results Time from `Enqueueing N commands for indexing` to serving the index loaded from disk, warm page cache, 4 alternating runs each. Each run starts from a fresh copy of the same snapshot of a ClickHouse index (44k shards, 363 MB on disk, 950 MB in memory; converted from format v20, so symbol tags are 0): | | load shards | build + serve | total | |---|---|---|---| | main (e0a86c11efad) | 2.3 s | 4.9 s | 7.1-7.2 s | | this PR | 1.7 s | 2.7-2.8 s | 4.4-4.5 s | ### Testing - To check the new reader on real data, I applied this change to a format-v20 base and ran `readIndexFile` over every shard of 29 existing background indexes (810,935 shards, written by clangd 21 and 22): no errors. - All 1509 `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 (primarily useful in the cold-cache scenario). --- Full diff: https://github.com/llvm/llvm-project/pull/237760.diff 6 Files Affected: - (modified) clang-tools-extra/clangd/index/Ref.cpp (+23) - (modified) clang-tools-extra/clangd/index/Ref.h (+20) - (modified) clang-tools-extra/clangd/index/Serialization.cpp (+10-5) - (modified) clang-tools-extra/clangd/index/dex/Dex.h (+7-2) - (modified) clang-tools-extra/clangd/unittests/IndexTests.cpp (+65) - (modified) clang-tools-extra/clangd/unittests/SerializationTests.cpp (+75) ``````````diff diff --git a/clang-tools-extra/clangd/index/Ref.cpp b/clang-tools-extra/clangd/index/Ref.cpp index edbfb95b528400..a28450423a20cd 100644 --- a/clang-tools-extra/clangd/index/Ref.cpp +++ b/clang-tools-extra/clangd/index/Ref.cpp @@ -39,6 +39,29 @@ 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]; + R.Location.FileURI = UniqueStrings.save(R.Location.FileURI).data(); + 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() && { + if (!llvm::is_sorted(Refs, llvm::less_first())) + llvm::sort(Refs, llvm::less_first()); + return RefSlab(std::move(Refs), std::move(Arena), NumRefs); +} + 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..8422e63629640c 100644 --- a/clang-tools-extra/clangd/index/Ref.h +++ b/clang-tools-extra/clangd/index/Ref.h @@ -131,6 +131,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. Much cheaper than Builder, which has to + /// group and deduplicate refs one by one. Bundles are put in RefSlab order + /// if needed: that order depends on the host (SymbolID's operator< does), + /// so a file written elsewhere may differ. + class BundleBuilder { + public: + BundleBuilder() : UniqueStrings(Arena) {} + /// Adds all refs of \p ID. Deep copy: strings will be owned by the slab. + /// Each symbol may be added only once. + void insert(const SymbolID &ID, llvm::ArrayRef<Ref> SymbolRefs); + RefSlab build() &&; + + private: + llvm::BumpPtrAllocator Arena; + llvm::UniqueStringSaver UniqueStrings; // Contents on the arena. + 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..5ee804693a5ecb 100644 --- a/clang-tools-extra/clangd/index/Serialization.cpp +++ b/clang-tools-extra/clangd/index/Serialization.cpp @@ -518,15 +518,20 @@ 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); + // Check before using the refs: a bad string index leaves a null URI. + if (RefsReader.err()) + return error("malformed or truncated refs"); + Refs.insert(RefsBundle.first, RefsBundle.second); } - if (RefsReader.err()) - return error("malformed or truncated refs"); Result.Refs = std::move(Refs).build(); + // Refs are written from a RefSlab, which has one bundle per symbol. + if (llvm::adjacent_find(*Result.Refs, [](const auto &L, const auto &R) { + return L.first == R.first; + }) != Result.Refs->end()) + return error("malformed refs: repeated symbol"); } if (Chunks.count("rela")) { Reader RelationsReader(Chunks.lookup("rela")); diff --git a/clang-tools-extra/clangd/index/dex/Dex.h b/clang-tools-extra/clangd/index/dex/Dex.h index 1ea7d8c06c67c5..c106a16aba5c84 100644 --- a/clang-tools-extra/clangd/index/dex/Dex.h +++ b/clang-tools-extra/clangd/index/dex/Dex.h @@ -41,8 +41,13 @@ 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_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) + 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..096e58c32540f7 100644 --- a/clang-tools-extra/clangd/unittests/IndexTests.cpp +++ b/clang-tools-extra/clangd/unittests/IndexTests.cpp @@ -514,6 +514,71 @@ TEST(MergeIndexTest, Refs) { fileURI("unittest:///test2.cc")))))); } +TEST(RefSlabTest, BundleBuilderMatchesBuilder) { + 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; + }; + std::vector<std::pair<SymbolID, std::vector<Ref>>> Bundles = { + {SymbolID("a"), {MakeRef(FileX, 3)}}, + {SymbolID("b"), {MakeRef(FileY, 2), MakeRef(FileX, 1)}}, + {SymbolID("c"), {MakeRef(FileY, 4), MakeRef(FileX, 5)}}, + }; + // The order of a file written on another host may differ from ours: give + // BundleBuilder bundles in decreasing order and refs out of order. + llvm::sort(Bundles, + [](const auto &L, const auto &R) { return R.first < L.first; }); + for (auto &[ID, Refs] : Bundles) + llvm::sort(Refs, [](const Ref &L, const Ref &R) { return R < L; }); + + RefSlab::Builder ExpectedBuilder; + RefSlab::BundleBuilder ActualBuilder; + for (const auto &[ID, Refs] : Bundles) { + for (const Ref &R : Refs) + ExpectedBuilder.insert(ID, R); + ActualBuilder.insert(ID, Refs); + } + RefSlab Expected = std::move(ExpectedBuilder).build(); + RefSlab Actual = std::move(ActualBuilder).build(); + // 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); + } +} + +TEST(RefSlabTest, BundleBuilderCopiesReusedBuffers) { + SymbolID First("a"), Second("b"); + // 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(First, {R}); + Buffer[8] = 'y'; + Builder.insert(Second, {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"), First); + EXPECT_EQ(FileToSymbol.lookup("file:///y.cc"), Second); +} + TEST(MergeIndexTest, IndexedFiles) { SymbolSlab DynSymbols; RefSlab DynRefs; diff --git a/clang-tools-extra/clangd/unittests/SerializationTests.cpp b/clang-tools-extra/clangd/unittests/SerializationTests.cpp index cbe2a9726f8656..4789d14432677d 100644 --- a/clang-tools-extra/clangd/unittests/SerializationTests.cpp +++ b/clang-tools-extra/clangd/unittests/SerializationTests.cpp @@ -543,6 +543,81 @@ TEST(SerializationTest, NoCrashOnBadArraySize) { "malformed or truncated include uri"); } +// Serializes the YAML fixture as RIFF, replaces its refs chunk with the result +// of Edit, and reads the edited file back. +llvm::Expected<IndexFileIn> +readWithEditedRefs(llvm::function_ref<std::string(llvm::StringRef)> Edit) { + auto In = readIndexFile(YAML); + if (!In) + return In.takeError(); + IndexFileOut Out(*In); + Out.Format = IndexFileFormat::RIFF; + std::string Serialized = llvm::to_string(Out); + auto Parsed = riff::readFile(Serialized); + if (!Parsed) + return Parsed.takeError(); + auto Refs = llvm::find_if(Parsed->Chunks, [](riff::Chunk C) { + return C.ID == riff::fourCC("refs"); + }); + if (Refs == Parsed->Chunks.end()) + return llvm::createStringError("no refs chunk"); + std::string Edited = Edit(Refs->Data); + Refs->Data = Edited; + return readIndexFile(llvm::to_string(*Parsed)); +} + +// The fixture's refs chunk is a single bundle: an 8-byte SymbolID, the number +// of refs (1, as a one-byte varint), then the ref. +constexpr size_t RefsBundleHeaderSize = SymbolID::RawSize + 1; + +TEST(SerializationTest, RejectsRepeatedRefsBundle) { + auto Read = readWithEditedRefs( + [](llvm::StringRef Refs) { return (Refs + Refs).str(); }); + ASSERT_TRUE(!Read); + EXPECT_EQ(llvm::toString(Read.takeError()), + "malformed refs: repeated symbol"); +} + +TEST(SerializationTest, NoCrashOnBadRefsFileURI) { + // Give the bundle a second ref whose file URI is not in the string table. + auto Read = readWithEditedRefs([](llvm::StringRef Refs) { + llvm::StringRef ID = Refs.take_front(SymbolID::RawSize); + llvm::StringRef Ref = Refs.drop_front(RefsBundleHeaderSize); + EXPECT_EQ(Refs[SymbolID::RawSize], 1); + // A ref is: 1 byte kind, varint(stringID) file URI, ... We need the URI to + // be encoded in one byte to replace it. + EXPECT_LT(static_cast<uint8_t>(Ref[1]), 0x80); + std::string BadRef = + (Ref.take_front(1) + llvm::fromHex("ffffffff0f") + Ref.drop_front(2)) + .str(); + return (ID + "\x02" + Ref + BadRef).str(); + }); + ASSERT_TRUE(!Read); + EXPECT_EQ(llvm::toString(Read.takeError()), "malformed or truncated refs"); +} + +// SymbolID order depends on the host's endianness, so a valid index written on +// another host can have its refs in a different order. +TEST(SerializationTest, AcceptsRefsBundlesInAnyOrder) { + SymbolID First, Second; + auto Read = readWithEditedRefs([&](llvm::StringRef Refs) { + std::string OtherID = Refs.take_front(SymbolID::RawSize).str(); + OtherID.back() ^= 1; + SymbolID A = SymbolID::fromRaw(Refs.take_front(SymbolID::RawSize)); + SymbolID B = SymbolID::fromRaw(OtherID); + std::tie(First, Second) = A < B ? std::tie(A, B) : std::tie(B, A); + // Write the bundles in decreasing order for this host. + llvm::StringRef Rest = Refs.drop_front(SymbolID::RawSize); + return (llvm::StringRef(Second.raw()) + Rest + First.raw() + Rest).str(); + }); + ASSERT_FALSE(!Read) << Read.takeError(); + ASSERT_TRUE(Read->Refs); + std::vector<SymbolID> IDs; + for (const auto &[ID, Refs] : *Read->Refs) + IDs.push_back(ID); + EXPECT_THAT(IDs, ElementsAre(First, Second)); +} + // Check we detect invalid string table size size without allocating it first. // If this detection fails, the test should allocate a huge array and crash. TEST(SerializationTest, NoCrashOnBadStringTableSize) { `````````` </details> https://github.com/llvm/llvm-project/pull/237760 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
