check in an experiment that didn't work out, to allow for future investigation.

llvm-svn: 40460

1 files changed, 27 insertions, 5 deletions

diff --git a/clang/Basic/SourceManager.cpp b/clang/Basic/SourceManager.cpp
index 05ead2d786f..e53547087df 100644
--- a/clang/Basic/SourceManager.cpp
+++ b/clang/Basic/SourceManager.cpp
@@ -337,11 +337,33 @@ unsigned SourceManager::getLineNumber(SourceLocation Loc) {
     }
   }
   
-  unsigned *Pos;
-  // TODO: If this is performance sensitive, we could try doing simple radix
-  // type approaches to make good (tight?) initial guesses based on the
-  // assumption that all lines are the same average size.
-  Pos = std::lower_bound(SourceLineCache, SourceLineCacheEnd, QueriedFilePos);
+  // If the spread is large, do a "radix" test as our initial guess, based on
+  // the assumption that lines average to approximately the same length.
+  // NOTE: This is currently disabled, as it does not appear to be profitable in
+  // initial measurements.
+  if (0 && SourceLineCacheEnd-SourceLineCache > 20) {
+    unsigned FileLen = FileInfo->SourceLineCache[FileInfo->NumLines-1];
+    
+    // Take a stab at guessing where it is.
+    unsigned ApproxPos = FileInfo->NumLines*QueriedFilePos / FileLen;
+    
+    // Check for -10 and +10 lines.
+    unsigned LowerBound = std::max(int(ApproxPos-10), 0);
+    unsigned UpperBound = std::min(ApproxPos+10, FileLen);
+
+    // If the computed lower bound is less than the query location, move it in.
+    if (SourceLineCache < SourceLineCacheStart+LowerBound &&
+        SourceLineCacheStart[LowerBound] < QueriedFilePos)
+      SourceLineCache = SourceLineCacheStart+LowerBound;
+    
+    // If the computed upper bound is greater than the query location, move it.
+    if (SourceLineCacheEnd > SourceLineCacheStart+UpperBound &&
+        SourceLineCacheStart[UpperBound] >= QueriedFilePos)
+      SourceLineCacheEnd = SourceLineCacheStart+UpperBound;
+  }
+  
+  unsigned *Pos
+    = std::lower_bound(SourceLineCache, SourceLineCacheEnd, QueriedFilePos);
   unsigned LineNo = Pos-SourceLineCacheStart;
   
   LastLineNoFileIDQuery = FileID;