Author: Haojian Wu Date: 2025-07-07T09:42:38+02:00 New Revision: 784bd61fc497b11a6d8d30abb6157c8a3597ffbf
URL: https://github.com/llvm/llvm-project/commit/784bd61fc497b11a6d8d30abb6157c8a3597ffbf DIFF: https://github.com/llvm/llvm-project/commit/784bd61fc497b11a6d8d30abb6157c8a3597ffbf.diff LOG: [clang] Speedup getFileIDLocal with a separate offset table. (#146604) The `SLocEntry` structure is 24 bytes, and the binary search only needs the offset. Loading an entry's offset might pull the entire SLocEntry object into the CPU cache. To make the binary search much more cache-efficient, we use a separate offset table. See https://llvm-compile-time-tracker.com/compare.php?from=650d0151c623c123e4e9736fe50421624a329260&to=6af564c0d75aff28a2784a8554448c0679877792&stat=instructions:u. Added: Modified: clang/include/clang/Basic/SourceManager.h clang/lib/Basic/SourceManager.cpp Removed: ################################################################################ diff --git a/clang/include/clang/Basic/SourceManager.h b/clang/include/clang/Basic/SourceManager.h index a90cc70825ffd..ed967fd47dc83 100644 --- a/clang/include/clang/Basic/SourceManager.h +++ b/clang/include/clang/Basic/SourceManager.h @@ -719,6 +719,8 @@ class SourceManager : public RefCountedBase<SourceManager> { /// Positive FileIDs are indexes into this table. Entry 0 indicates an invalid /// expansion. SmallVector<SrcMgr::SLocEntry, 0> LocalSLocEntryTable; + /// An in-parallel offset table, merely used for speeding up FileID lookup. + SmallVector<SourceLocation::UIntTy> LocalLocOffsetTable; /// The table of SLocEntries that are loaded from other modules. /// diff --git a/clang/lib/Basic/SourceManager.cpp b/clang/lib/Basic/SourceManager.cpp index 7d1b23bbc3b2c..79a0d9d28c40b 100644 --- a/clang/lib/Basic/SourceManager.cpp +++ b/clang/lib/Basic/SourceManager.cpp @@ -329,6 +329,7 @@ SourceManager::~SourceManager() { void SourceManager::clearIDTables() { MainFileID = FileID(); LocalSLocEntryTable.clear(); + LocalLocOffsetTable.clear(); LoadedSLocEntryTable.clear(); SLocEntryLoaded.clear(); SLocEntryOffsetLoaded.clear(); @@ -628,9 +629,11 @@ FileID SourceManager::createFileIDImpl(ContentCache &File, StringRef Filename, noteSLocAddressSpaceUsage(Diag); return FileID(); } + assert(LocalSLocEntryTable.size() == LocalLocOffsetTable.size()); LocalSLocEntryTable.push_back( SLocEntry::get(NextLocalOffset, FileInfo::get(IncludePos, File, FileCharacter, Filename))); + LocalLocOffsetTable.push_back(NextLocalOffset); LastLookupStartOffset = NextLocalOffset; // We do a +1 here because we want a SourceLocation that means "the end of the // file", e.g. for the "no newline at the end of the file" diagnostic. @@ -684,7 +687,9 @@ SourceManager::createExpansionLocImpl(const ExpansionInfo &Info, SLocEntryLoaded[Index] = SLocEntryOffsetLoaded[Index] = true; return SourceLocation::getMacroLoc(LoadedOffset); } + assert(LocalSLocEntryTable.size() == LocalLocOffsetTable.size()); LocalSLocEntryTable.push_back(SLocEntry::get(NextLocalOffset, Info)); + LocalLocOffsetTable.push_back(NextLocalOffset); if (NextLocalOffset + Length + 1 <= NextLocalOffset || NextLocalOffset + Length + 1 > CurrentLoadedOffset) { Diag.Report(diag::err_sloc_space_too_large); @@ -807,6 +812,7 @@ FileID SourceManager::getFileIDLocal(SourceLocation::UIntTy SLocOffset) const { assert(SLocOffset < NextLocalOffset && "Bad function choice"); assert(SLocOffset >= LocalSLocEntryTable[0].getOffset() && SLocOffset > 0 && "Invalid SLocOffset"); + assert(LocalSLocEntryTable.size() == LocalLocOffsetTable.size()); assert(LastFileIDLookup.ID >= 0 && "Only cache local file sloc entry"); // After the first and second level caches, I see two common sorts of @@ -837,8 +843,8 @@ FileID SourceManager::getFileIDLocal(SourceLocation::UIntTy SLocOffset) const { unsigned NumProbes = 0; while (true) { --GreaterIndex; - assert(GreaterIndex < LocalSLocEntryTable.size()); - if (LocalSLocEntryTable[GreaterIndex].getOffset() <= SLocOffset) { + assert(GreaterIndex < LocalLocOffsetTable.size()); + if (LocalLocOffsetTable[GreaterIndex] <= SLocOffset) { FileID Res = FileID::get(int(GreaterIndex)); // Remember it. We have good locality across FileID lookups. LastFileIDLookup = Res; @@ -858,11 +864,7 @@ FileID SourceManager::getFileIDLocal(SourceLocation::UIntTy SLocOffset) const { ++NumBinaryProbes; unsigned MiddleIndex = LessIndex + (GreaterIndex - LessIndex) / 2; - - SourceLocation::UIntTy MidOffset = - LocalSLocEntryTable[MiddleIndex].getOffset(); - - if (MidOffset <= SLocOffset) + if (LocalLocOffsetTable[MiddleIndex] <= SLocOffset) LessIndex = MiddleIndex + 1; else GreaterIndex = MiddleIndex; _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
