Changeset 148750 in webkit

Timestamp:

Apr 19, 2013 9:17:42 AM (11 years ago)

Author:

akling@apple.com

Message:

[Mac] ComplexTextController is slow with large numbers of text runs.
<​http://webkit.org/b/114875>
<rdar://problem/13337036>

Reviewed by Dan Bernstein.

Instead of iterating over the text runs in indexOfCurrentRun() to figure out the leftmost glyph,
create a lookup table of [run# -> distance in glyphs] at ComplexTextController construction time.

This avoids O(n^{2) behavior in indexOfCurrentRun().}

• platform/graphics/mac/ComplexTextController.cpp:

(WebCore::ComplexTextController::ComplexTextController):
(WebCore::ComplexTextController::indexOfCurrentRun):

• platform/graphics/mac/ComplexTextController.h:

(ComplexTextController):

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• platform/graphics/mac/ComplexTextController.cpp (modified) (2 diffs)
• platform/graphics/mac/ComplexTextController.h (modified) (1 diff)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2013-04-19  Andreas Kling  <akling@apple.com>
+
+        [Mac] ComplexTextController is slow with large numbers of text runs.
+        <http://webkit.org/b/114875>
+        <rdar://problem/13337036>
+
+        Reviewed by Dan Bernstein.
+
+        Instead of iterating over the text runs in indexOfCurrentRun() to figure out the leftmost glyph,
+        create a lookup table of [run# -> distance in glyphs] at ComplexTextController construction time.
+
+        This avoids O(n^2) behavior in indexOfCurrentRun().
+
+        * platform/graphics/mac/ComplexTextController.cpp:
+        (WebCore::ComplexTextController::ComplexTextController):
+        (WebCore::ComplexTextController::indexOfCurrentRun):
+        * platform/graphics/mac/ComplexTextController.h:
+        (ComplexTextController):
+
 2013-04-19  Mario Sanchez Prada  <mario.prada@samsung.com>
 

trunk/Source/WebCore/platform/graphics/mac/ComplexTextController.cpp

@@ -160 +160 @@
     adjustGlyphsAndAdvances();
 
-    if (!m_isLTROnly)
+    if (!m_isLTROnly) {
         m_runIndices.reserveInitialCapacity(m_complexTextRuns.size());
+
+        m_glyphCountFromStartToIndex.reserveInitialCapacity(m_complexTextRuns.size());
+        unsigned glyphCountSoFar = 0;
+        for (unsigned i = 0; i < m_complexTextRuns.size(); ++i) {
+            m_glyphCountFromStartToIndex.uncheckedAppend(glyphCountSoFar);
+            glyphCountSoFar += m_complexTextRuns[i]->glyphCount();
+        }
+    }
 
     m_runWidthSoFar = m_leadingExpansion;
@@ -449 +457 @@
 
     unsigned currentRunIndex = m_runIndices[m_currentRun];
-    for (unsigned i = 0; i < currentRunIndex; ++i)
-        leftmostGlyph += m_complexTextRuns[i]->glyphCount();
+    leftmostGlyph = m_glyphCountFromStartToIndex[currentRunIndex];
     return currentRunIndex;
 }

trunk/Source/WebCore/platform/graphics/mac/ComplexTextController.h

@@ -133 +133 @@
     unsigned incrementCurrentRun(unsigned& leftmostGlyph);
 
-    // The default size of this vector was selected as being the smallest power of two greater than
+    // The initial capacity of these vectors was selected as being the smallest power of two greater than
     // the average (3.5) plus one standard deviation (7.5) of nonzero sizes used on Arabic Wikipedia.
     Vector<unsigned, 16> m_runIndices;
+    Vector<unsigned, 16> m_glyphCountFromStartToIndex;
 
     const Font& m_font;