bug 953247 - use binary search instead of linear scan to find tab-width records. r=roc
authorJonathan Kew <jkew@mozilla.com>
Sun, 29 Dec 2013 11:32:21 +0000
changeset 177846 da02316148fe3bee4728a8ba8e2964866ee693c9
parent 177845 0f5ac5ff7d43609365ab5bad30074f30eb7b0399
child 177850 39370ea1f0d6313bd11cbbf05d9d4cf1a5041ff7
child 177853 8b6f20bda157534bd01e73c1caa5179e95c9df9c
push id3343
push userffxbld
push dateMon, 17 Mar 2014 21:55:32 +0000
treeherdermozilla-beta@2f7d3415f79f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersroc
bugs953247
milestone29.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
bug 953247 - use binary search instead of linear scan to find tab-width records. r=roc
layout/generic/nsTextFrame.cpp
--- a/layout/generic/nsTextFrame.cpp
+++ b/layout/generic/nsTextFrame.cpp
@@ -119,29 +119,55 @@ struct TabWidthStore {
   // A TabWidth record for each tab character measured so far.
   nsTArray<TabWidth> mWidths;
 };
 
 void
 TabWidthStore::ApplySpacing(gfxTextRun::PropertyProvider::Spacing *aSpacing,
                             uint32_t aOffset, uint32_t aLength)
 {
-  // We could binary-search for the first record that falls within the range,
-  // but as the number of tabs is normally small and we usually process them
-  // sequentially from the beginning of the line, it doesn't seem worth doing
-  // at this point.
-  for (uint32_t i = 0; i < mWidths.Length(); ++i) {
-    TabWidth& tw = mWidths[i];
-    if (tw.mOffset < aOffset) {
-      continue;
-    }
-    if (tw.mOffset - aOffset >= aLength) {
+  uint32_t i = 0, len = mWidths.Length();
+
+  // If aOffset is non-zero, do a binary search to find where to start
+  // processing the tab widths, in case the list is really long. (See bug
+  // 953247.)
+  // We need to start from the first entry where mOffset >= aOffset.
+  if (aOffset > 0) {
+    uint32_t lo = 0, hi = len;
+    while (lo < hi) {
+      i = (lo + hi) / 2;
+      const TabWidth& tw = mWidths[i];
+      if (tw.mOffset < aOffset) {
+        // mWidths[i] precedes the target range; new search range
+        // will be [i+1, hi)
+        lo = ++i;
+        continue;
+      }
+      if (tw.mOffset > aOffset) {
+        // mWidths[i] is within (or beyond) the target range;
+        // new search range is [lo, i). If it turns out that
+        // mWidths[i] was the first entry within the range,
+        // we'll never move hi any further, and end up exiting
+        // when i == lo == this value of hi.
+        hi = i;
+        continue;
+      }
+      // Found an exact match for aOffset, so end search now
+      break;
+    }
+  }
+
+  uint32_t limit = aOffset + aLength;
+  while (i < len) {
+    const TabWidth& tw = mWidths[i];
+    if (tw.mOffset >= limit) {
       break;
     }
     aSpacing[tw.mOffset - aOffset].mAfter += tw.mWidth;
+    i++;
   }
 }
 
 static void DestroyTabWidth(void* aPropertyValue)
 {
   delete static_cast<TabWidthStore*>(aPropertyValue);
 }