[SourceManager] Speedup getFileIDLocal with a separate Offset Table.

[hokein]

Summary

This patch introduces a separate Offset array in SourceManager, it is redundant
and merely used for searching. This "AOS vs. SOA" optimization give us a large
memory locality win, see the data below.

This is a low-hanging fruit optimization (without significantly changing the
SlocEntry and its underlying storge in SourceManager). The sad bit is thatit
increases SourceManager memory usage, however it is a small fraction (< 10%) of
clang AST memory usage, which I think it is mostly negligible.

getFileIDLoaded is excluded in this patch, it is trickier due to the lazy load of
SLocEntry, unclear we will gain as much speedup as the local one.

Speedup:

Linux kernel: getFileIDLocal overhead is reduced to 1.66% (~30% saving)

Memory usage in bytes (AST built in clangd):

SemaExpr.cpp:  149502874 ->149529494 
FindTarget.cpp  83177157 ->  83177569

[nickdesaulniers]

clang/include/clang/Basic/SourceManager.h

696

Add to this comment that the size is expected to stay in sync with LocalSLocEntryTable.

697

LocalSLocEntryTable is a vec of SrcMgr::SLocEntry. SrcMgr::SLocEntry's Offset is:

static constexpr int OffsetBits = 8 * sizeof(SourceLocation::UIntTy) - 1;
  SourceLocation::UIntTy Offset : OffsetBits;

So this is a vector of 32b values vs the 24b values we need. Does packing this by declaring a struct improve locality further?

diff --git a/clang/include/clang/Basic/SourceManager.h b/clang/include/clang/Basic/SourceManager.h
index 70ba85bbe948..518c6ed59120 100644
--- a/clang/include/clang/Basic/SourceManager.h
+++ b/clang/include/clang/Basic/SourceManager.h
@@ -692,9 +692,15 @@ class SourceManager : public RefCountedBase<SourceManager> {
   /// Positive FileIDs are indexes into this table. Entry 0 indicates an invalid
   /// expansion.
   SmallVector<SrcMgr::SLocEntry, 0> LocalSLocEntryTable;
+
+  struct SMOffset {
+    SourceLocation::UIntTy Offset : 24;
+    SMOffset (SourceLocation::UIntTy O): Offset(O){}
+    operator SourceLocation::UIntTy() const { return Offset; }
+  };
   /// An in-parallel SlocEntry offset table, merely used for speeding up the
   /// FileID lookup.
-  SmallVector<SourceLocation::UIntTy> LocalLocOffsetTable;
+  SmallVector<SMOffset> LocalLocOffsetTable;
 
   /// The table of SLocEntries that are loaded from other modules.
   ///

clang/lib/Basic/SourceManager.cpp

676

should we add some asserts that LocalSLocEntryTable.size() == LocalLocOffsetTable.size() somewhere?

[nickdesaulniers]

clang/include/clang/Basic/SourceManager.h

697

struct SMOffset { ... } __attribute__((packed));

[sammccall]

This looks good to me, I think we should ask @aaron.ballman about the memory increase.

If we wanted to eliminate SLocEntry::Offset then we could add SourceManager::getOffset(FileID) based on this table and deprecate SLocEntry::getOffset().
We'd have to tackle loaded SLocs for that though.

SemaExpr.cpp: 149529494 -> 149502874

Are these numbers backwards? Why would memory usage go down?

clang/include/clang/Basic/SourceManager.h

697

So this is a vector of 32b values vs the 24b values we need

It's 31 bits: 8 * sizeof - 1, not 8 * (sizeof - 1).
(And none of those bits are spare in practice)

[sammccall]

It'd be great to have some numbers for overall memory increase based on clang rather than clangd, that's a more critical case and has a different memory pattern.

[hokein]

print memory usage in SourceManager::PrintStats.

[hokein]

SemaExpr.cpp: 149529494 -> 149502874

Are these numbers backwards? Why would memory usage go down?

Oops, you're right, I made a mistake, correct it in the description.

[hokein]

More data on clang memory usage (measured with the clang -cc1 -fsyntax-only -print-stats, AST size = ASTContext + Decl + Stmt/Expr; Total = AST size + SourceManager size)

The memory increase for C++ is negligible (< 1%), but for C, we have ~5% memory increase.

	AST size	SourceManager size	Total
SemaExpr.cpp	275.1 MB	15MB -> 16.6 MB	290.1MB-> 291.7MB
FindTarget.cpp	131.9MB	14.3MB -> 15.9MB	146.2MB -> 147.8 MB
drm_property.c	11.4MB	3.6MB -> 4.4 MB	15MB -> 15.8MB
nl80211.c	28.4MB	26.4MB -> 29.6MB	54.8MB -> 58MB

[nickdesaulniers]

Is it worth it and possible to fully decompose LocalSLocEntryTable into arrays of its constituent parts, and only construct a SLocEntry when necessary?

I'm ok with the cost increase; please also adding asserts to keep the size of the vectors equivalent.

[hokein]

add assert

[hokein]

In D135440#3847720, @nickdesaulniers wrote:

Is it worth it and possible to fully decompose LocalSLocEntryTable into arrays of its constituent parts, and only construct a SLocEntry when necessary?

Fully decomposing LocalSLocEntryTable into arrays seems a good idea (which will get us more memory back, since we don't need to pay the 4 padding bytes for SLocEntry).
But I think constructing a SLocEntry every time we call getSLocEntry would be expensive since this is a hot function. Instead, we should probably deprecate the SLocEntry structure at all -- adding getOffset(FileID), getFileInfo(FileID), getExpansionInfo(FileID) to the SourceManager, this would take some more work (update all SLocEntry usage, tackle loadedSLocEntry` etc).

I'm ok with the cost increase; please also adding asserts to keep the size of the vectors equivalent.

added. I'd wait for a few days before landing it for @aaron.ballman's opinion.

[MaskRay]

Speedup: Linux kernel: getFileIDLocal overhead is reduced to 1.66% (~30% saving)

What's the fraction related to the whole parsing time?

The sad bit is thatit increases SourceManager memory usage, however it is a small fraction (< 10%) of clang AST memory usage, which I think it is mostly negligible.

What's the fraction related to the whole memory usage?

Have you tried decreasing the number of linear probing (8) or switching to branch-less binary search?

clang/include/clang/Basic/SourceManager.h

class SourceManager : public RefCountedBase<SourceManager> {
   /// as they do not refer to a file.
   std::vector<SrcMgr::ContentCache*> MemBufferInfos;
 
   /// The table of SLocEntries that are local to this module.
   ///
   /// Positive FileIDs are indexes into this table. Entry 0 indicates an invalid
   /// expansion.
   SmallVector<SrcMgr::SLocEntry, 0> LocalSLocEntryTable;
+  /// An in-parallel SlocEntry offset table, merely used for speeding up the
+  /// FileID lookup.
+  SmallVector<SourceLocation::UIntTy> LocalLocOffsetTable;
 
   /// The table of SLocEntries that are loaded from other modules.
   ///
   /// Negative FileIDs are indexes into this table. To get from ID to an index,
   /// use (-ID - 2).
   SmallVector<SrcMgr::SLocEntry, 0> LoadedSLocEntryTable;
 
   /// The starting offset of the next local SLocEntry.

clang/lib/Basic/SourceManager.cpp

if (I->second) {
       ContentCacheAlloc.Deallocate(I->second);
     }
   }
 }
 
 void SourceManager::clearIDTables() {
   MainFileID = FileID();
   LocalSLocEntryTable.clear();
+  LocalLocOffsetTable.clear();
   LoadedSLocEntryTable.clear();
   SLocEntryLoaded.clear();
   LastLineNoFileIDQuery = FileID();
   LastLineNoContentCache = nullptr;
   LastFileIDLookup = FileID();
 
   if (LineTable)
     LineTable->clear();
if (LoadedID < 0) {
     return FileID::get(LoadedID);
   }
   unsigned FileSize = File.getSize();
   if (!(NextLocalOffset + FileSize + 1 > NextLocalOffset &&
         NextLocalOffset + FileSize + 1 <= CurrentLoadedOffset)) {
     Diag.Report(IncludePos, diag::err_include_too_large);
     return FileID();
   }
+  assert(LoadedSLocEntryTable.size() == LocalLocOffsetTable.size());
   LocalSLocEntryTable.push_back(
       SLocEntry::get(NextLocalOffset,
                      FileInfo::get(IncludePos, File, FileCharacter, Filename)));
+  LocalLocOffsetTable.push_back(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.
   NextLocalOffset += FileSize + 1;
 
   // Set LastFileIDLookup to the newly created file.  The next getFileID call is
   // almost guaranteed to be from that file.
   FileID FID = FileID::get(LocalSLocEntryTable.size()-1);
   return LastFileIDLookup = FID;
if (LoadedID < 0) {
     assert(LoadedID != -1 && "Loading sentinel FileID");
     unsigned Index = unsigned(-LoadedID) - 2;
     assert(Index < LoadedSLocEntryTable.size() && "FileID out of range");
     assert(!SLocEntryLoaded[Index] && "FileID already loaded");
     LoadedSLocEntryTable[Index] = SLocEntry::get(LoadedOffset, Info);
     SLocEntryLoaded[Index] = true;
     return SourceLocation::getMacroLoc(LoadedOffset);
   }
+  assert(LocalSLocEntryTable.size() == LocalLocOffsetTable.size());
   LocalSLocEntryTable.push_back(SLocEntry::get(NextLocalOffset, Info));
+  LocalLocOffsetTable.push_back(NextLocalOffset);
   assert(NextLocalOffset + Length + 1 > NextLocalOffset &&
          NextLocalOffset + Length + 1 <= CurrentLoadedOffset &&
          "Ran out of source locations!");
   // See createFileID for that +1.
   NextLocalOffset += Length + 1;
   return SourceLocation::getMacroLoc(NextLocalOffset - (Length + 1));
 }
 
FileID SourceManager::getFileIDLocal(SourceLocation::UIntTy SLocOffset) const {
   // See if this is near the file point - worst case we start scanning from the
   // most newly created FileID.
 
   // LessIndex - This is the lower bound of the range that we're searching.
   // We know that the offset corresponding to the FileID is is less than
   // SLocOffset.
   unsigned LessIndex = 0;
   // upper bound of the search range.
-  unsigned GreaterIndex = LocalSLocEntryTable.size();
+  unsigned GreaterIndex = LocalLocOffsetTable.size();
   if (LastFileIDLookup.ID >= 0) {
     // Use the LastFileIDLookup to prune the search space.
-    if (LocalSLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset)
+    if (LocalLocOffsetTable[LastFileIDLookup.ID] < SLocOffset)
       LessIndex = LastFileIDLookup.ID;
     else
       GreaterIndex = LastFileIDLookup.ID;
   }
 
   // Find the FileID that contains this.
   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;
       NumLinearScans += NumProbes+1;
       return Res;
     }
     if (++NumProbes == 8)
       break;
   }
 
   NumProbes = 0;
   while (true) {
     unsigned MiddleIndex = (GreaterIndex-LessIndex)/2+LessIndex;
-    SourceLocation::UIntTy MidOffset =
-        getLocalSLocEntry(MiddleIndex).getOffset();
+    SourceLocation::UIntTy MidOffset = LocalLocOffsetTable[MiddleIndex];
 
     ++NumProbes;
 
     // If the offset of the midpoint is too large, chop the high side of the
     // range to the midpoint.
     if (MidOffset > SLocOffset) {
       GreaterIndex = MiddleIndex;
       continue;
     }
 
     // If the middle index contains the value, succeed and return.
-    if (MiddleIndex + 1 == LocalSLocEntryTable.size() ||
-        SLocOffset < getLocalSLocEntry(MiddleIndex + 1).getOffset()) {
+    if (MiddleIndex + 1 == LocalLocOffsetTable.size() ||
+        SLocOffset < LocalLocOffsetTable[MiddleIndex + 1]) {
       FileID Res = FileID::get(MiddleIndex);
 
       // Remember it.  We have good locality across FileID lookups.
       LastFileIDLookup = Res;
       NumBinaryProbes += NumProbes;
       return Res;
     }
 
void SourceManager::PrintStats() const {
   }
   unsigned NumMacroArgsComputed = MacroArgsCacheMap.size();
 
   llvm::errs() << NumFileBytesMapped << " bytes of files mapped, "
                << NumLineNumsComputed << " files with line #'s computed, "
                << NumMacroArgsComputed << " files with macro args computed.\n";
   llvm::errs() << "FileID scans: " << NumLinearScans << " linear, "
                << NumBinaryProbes << " binary.\n";
+  llvm::errs() << "Total bytes: "
+               << getDataStructureSizes() + getContentCacheSize() +
+                      getMemoryBufferSizes().malloc_bytes;
 }
 
 LLVM_DUMP_METHOD void SourceManager::dump() const {
   llvm::raw_ostream &out = llvm::errs();
 
   auto DumpSLocEntry = [&](int ID, const SrcMgr::SLocEntry &Entry,
                            llvm::Optional<SourceLocation::UIntTy> NextStart) {
     out << "SLocEntry <FileID " << ID << "> " << (Entry.isFile() ? "file" : "expansion")
if (size_t sized_mapped = MemBufferInfos[i]->getSizeBytesMapped())
       }
 
   return MemoryBufferSizes(malloc_bytes, mmap_bytes);
 }
 
 size_t SourceManager::getDataStructureSizes() const {
   size_t size = llvm::capacity_in_bytes(MemBufferInfos)
     + llvm::capacity_in_bytes(LocalSLocEntryTable)
+    + llvm::capacity_in_bytes(LocalLocOffsetTable)
     + llvm::capacity_in_bytes(LoadedSLocEntryTable)
     + llvm::capacity_in_bytes(SLocEntryLoaded)
     + llvm::capacity_in_bytes(FileInfos);
 
   if (OverriddenFilesInfo)
     size += llvm::capacity_in_bytes(OverriddenFilesInfo->OverriddenFiles);
 
   return size;