hokein created this revision.
hokein added reviewers: sammccall, nickdesaulniers.
Herald added a project: All.
hokein requested review of this revision.
Herald added a project: clang.
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%
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D135132
Files:
clang/lib/Basic/SourceManager.cpp
Index: clang/lib/Basic/SourceManager.cpp
===================================================================
--- clang/lib/Basic/SourceManager.cpp
+++ clang/lib/Basic/SourceManager.cpp
@@ -790,15 +790,20 @@
// 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;
+ // "I" is an iterator that points to a FileID whose offset is known to be
+ // larger than SLocOffset.
+ const SrcMgr::SLocEntry *I = LocalSLocEntryTable.end();
+ // 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;
+ if (LastFileIDLookup.ID >= 0) {
+ // Use the LastFileIDLookup to prune the search space.
+ if (LocalSLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset)
+ LessIndex = LastFileIDLookup.ID;
+ else
+ I = LocalSLocEntryTable.begin() + LastFileIDLookup.ID;
}
// Find the FileID that contains this. "I" is an iterator that points to a
@@ -820,10 +825,6 @@
// 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;
Index: clang/lib/Basic/SourceManager.cpp
===================================================================
--- clang/lib/Basic/SourceManager.cpp
+++ clang/lib/Basic/SourceManager.cpp
@@ -790,15 +790,20 @@
// 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;
+ // "I" is an iterator that points to a FileID whose offset is known to be
+ // larger than SLocOffset.
+ const SrcMgr::SLocEntry *I = LocalSLocEntryTable.end();
+ // 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;
+ if (LastFileIDLookup.ID >= 0) {
+ // Use the LastFileIDLookup to prune the search space.
+ if (LocalSLocEntryTable[LastFileIDLookup.ID].getOffset() < SLocOffset)
+ LessIndex = LastFileIDLookup.ID;
+ else
+ I = LocalSLocEntryTable.begin() + LastFileIDLookup.ID;
}
// Find the FileID that contains this. "I" is an iterator that points to a
@@ -820,10 +825,6 @@
// 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;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
