[SourceManager] Improve getFileIDLocal.

[hokein]

Summary

Prune the search space -- If we know offset(LastFileIDLookup) < SearchOffset, we
can prune the initial binary-search range from [0, end) to [LastFileIDlookup, end).

It reduces the binary search scan by ~30%.

SemaExpr.cpp: 1393437 -> 1035426
FindTarget.cpp: 1275930 -> 920087

Linux kernel:
getFileIDLocal: 2.45% -> 2.15%

[sammccall]

Nice!

clang/lib/Basic/SourceManager.cpp

796

hmm, while here, why not just get rid of I and use GreaterIndex throughout?

Of its uses: line 806 and 815 would be clearer, 814 would be less clear, 796 and 813 are the same, and 827 goes away entirely.

(This is a little thing to nitpick, but I always hate trying to read this function)

808

this comment duplicates your new one above

897

is the same optimization available here?
I think getFileIDLoaded() is important for module builds and when we use PCH.
Though admittedly I don't think this is relevant to the lexer path we've been looking at: those locations should always be local.

[hokein]

Remove the I variable, use GreaterIndex instead.

clang/lib/Basic/SourceManager.cpp

897

Yeah. That's my next step. I plan to send a separate patch for it.

[sammccall]

clang/lib/Basic/SourceManager.cpp

807

Just checking: we decrement GreaterIndex without a bounds check in the loop and then dereference it in the loop.

I guess this is safe because:

• in the case where it's equal to size(), it's nonzero due to a dummy entry at 0 (and unchanged in this patch)
• in the case where the cache is used, it's also nonzero (guarded)

Maybe this is worth an assertion?

[hokein]

add an assertion.

[nickdesaulniers]

clang/lib/Basic/SourceManager.cpp

797

Consider renaming this LesserIndex which matches with GreaterIndex better.

797

So this comment was wrong?

[hokein]

update

clang/lib/Basic/SourceManager.cpp

797

This comment was true before the patch. I have updated it to match the current code.

797

I'm not sure, it doesn't seem to be much better (I'm leaning towards keeping it as-is).

807

yes, exactly. added an assertion.

clang/lib/Basic/SourceManager.cpp

FileID SourceManager::getFileIDLocal(SourceLocation::UIntTy SLocOffset) const {
   // completely random and may be a very long way away.
   //
   // To handle this, we do a linear search for up to 8 steps to catch #1 quickly
   // then we fall back to a less cache efficient, but more scalable, binary
   // search to find the location.
 
   // See if this is near the file point - worst case we start scanning from the
   // most newly created FileID.
-  const SrcMgr::SLocEntry *I;
 
-  if (LastFileIDLookup.ID < 0 ||
-      LocalSLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset) {
-    // Neither loc prunes our search.
-    I = LocalSLocEntryTable.end();
-  } else {
-    // Perhaps it is near the file point.
-    I = LocalSLocEntryTable.begin()+LastFileIDLookup.ID;
+  // 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();
+  if (LastFileIDLookup.ID >= 0) {
+    // Use the LastFileIDLookup to prune the search space.
+    if (LocalSLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset)
+      LessIndex = LastFileIDLookup.ID;
+    else
+      GreaterIndex = LastFileIDLookup.ID;
   }
 
   // Find the FileID that contains this.  "I" is an iterator that points to a
   // FileID whose offset is known to be larger than SLocOffset.
   unsigned NumProbes = 0;
   while (true) {
-    --I;
-    if (I->getOffset() <= SLocOffset) {
-      FileID Res = FileID::get(int(I - LocalSLocEntryTable.begin()));
+    --GreaterIndex;
+    if (LocalSLocEntryTable[GreaterIndex].getOffset() <= 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;
   }
 
-  // Convert "I" back into an index.  We know that it is an entry whose index is
-  // larger than the offset we are looking for.
-  unsigned GreaterIndex = I - LocalSLocEntryTable.begin();
-  // 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;
   NumProbes = 0;
   while (true) {
     unsigned MiddleIndex = (GreaterIndex-LessIndex)/2+LessIndex;
     SourceLocation::UIntTy MidOffset =
         getLocalSLocEntry(MiddleIndex).getOffset();
 
     ++NumProbes;
 
if (E.getOffset() <= SLocOffset) {
       NumLinearScans += NumProbes + 1;
       return Res;
     }
   }
 
   // Linear scan failed. Do the binary search. Note the reverse sorting of the
   // table: GreaterIndex is the one where the offset is greater, which is
   // actually a lower index!
   unsigned GreaterIndex = I;
   unsigned LessIndex = LoadedSLocEntryTable.size();
   NumProbes = 0;
   while (true) {
     ++NumProbes;
     unsigned MiddleIndex = (LessIndex - GreaterIndex) / 2 + GreaterIndex;
     const SrcMgr::SLocEntry &E = getLoadedSLocEntry(MiddleIndex, &Invalid);
     if (Invalid)
       return FileID(); // invalid entry.