Changeset 225110 in webkit

Timestamp:

Nov 23, 2017 2:45:26 AM (6 years ago)

Author:

Antti Koivisto

Message:

RenderBlockFlow::layoutRunsAndFloatsInRange is O(n^{2) for runs of inlines without any text
​https://bugs.webkit.org/show_bug.cgi?id=179950}

Reviewed by Simon Fraser.

It calls createBidiRunsForLine for each line. createBidiRunsForLine traverses past the end of the line until
it finds the end of the current bidi run. If there is no text in the flow, it never finds anything and traverses
the entire flow. This is O(n^{2) for the number of renderers in the flow.}

Tested by PerformanceTests/Layout/inline-layout-no-text.html

• platform/text/BidiResolver.h:

(WebCore::BidiResolverBase::needsContinuePastEnd const):
(WebCore::BidiResolverBase::needsContinuePastEndInternal const):
(WebCore::DerivedClass>::createBidiRunsForLine):

When past end of line call needsContinuePastEnd() to see if we need to continue searching for the end of the bidi run.

• rendering/InlineIterator.h:

(WebCore::InlineBidiResolver::needsContinuePastEndInternal const):

InlineBidiResolver only returns runs up to the last renderer on the line and can bail out.

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• platform/text/BidiResolver.h (modified) (4 diffs)
• rendering/InlineIterator.h (modified) (1 diff)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2017-11-23  Antti Koivisto  <antti@apple.com>
+
+        RenderBlockFlow::layoutRunsAndFloatsInRange is O(n^2) for runs of inlines without any text
+        https://bugs.webkit.org/show_bug.cgi?id=179950
+
+        Reviewed by Simon Fraser.
+
+        It calls createBidiRunsForLine for each line. createBidiRunsForLine traverses past the end of the line until
+        it finds the end of the current bidi run. If there is no text in the flow, it never finds anything and traverses
+        the entire flow. This is O(n^2) for the number of renderers in the flow.
+
+        Tested by PerformanceTests/Layout/inline-layout-no-text.html
+
+        * platform/text/BidiResolver.h:
+        (WebCore::BidiResolverBase::needsContinuePastEnd const):
+        (WebCore::BidiResolverBase::needsContinuePastEndInternal const):
+        (WebCore::DerivedClass>::createBidiRunsForLine):
+
+            When past end of line call needsContinuePastEnd() to see if we need to continue searching for the end of the bidi run.
+
+        * rendering/InlineIterator.h:
+        (WebCore::InlineBidiResolver::needsContinuePastEndInternal const):
+
+            InlineBidiResolver only returns runs up to the last renderer on the line and can bail out.
+
 2017-11-23  Zan Dobersek  <zdobersek@igalia.com>
 

trunk/Source/WebCore/platform/text/BidiResolver.h

@@ -246 +246 @@
     // pass in some sort of Traits object which knows how to create runs for appending.
     void appendRun() { static_cast<DerivedClass&>(*this).appendRunInternal(); }
+    bool needsContinuePastEnd() const { return static_cast<const DerivedClass&>(*this).needsContinuePastEndInternal(); }
 
     Iterator m_current;
@@ -278 +279 @@
     void incrementInternal() { m_current.increment(); }
     void appendRunInternal();
+    bool needsContinuePastEndInternal() const { return true; }
 
     Vector<BidiEmbedding, 8> m_currentExplicitEmbeddingSequence;
@@ -293 +295 @@
     void incrementInternal();
     void appendRunInternal();
+    bool needsContinuePastEndInternal() const;
     Vector<IsolateRun>& isolatedRuns() { return m_isolatedRuns; }
 
@@ -881 +884 @@
         }
 
-        if (pastEnd && m_eor == m_current) {
+        if (pastEnd && (m_eor == m_current || !needsContinuePastEnd())) {
             if (!m_reachedEndOfLine) {
                 m_eor = endOfLine;

trunk/Source/WebCore/rendering/InlineIterator.h

@@ -587 +587 @@
 }
 
+template<>
+inline bool InlineBidiResolver::needsContinuePastEndInternal() const
+{
+    // We don't collect runs beyond the endOfLine renderer. Stop traversing when the iterator moves to the next renderer to prevent O(n^2).
+    return m_current.renderer() == endOfLine.renderer();
+}
+
 } // namespace WebCore