Title: [225110] trunk/Source/WebCore
- Revision
- 225110
- Author
- an...@apple.com
- Date
- 2017-11-23 02:45:26 -0800 (Thu, 23 Nov 2017)
Log 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.
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (225109 => 225110)
--- trunk/Source/WebCore/ChangeLog 2017-11-23 10:31:07 UTC (rev 225109)
+++ trunk/Source/WebCore/ChangeLog 2017-11-23 10:45:26 UTC (rev 225110)
@@ -1,3 +1,28 @@
+2017-11-23 Antti Koivisto <an...@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 <zdober...@igalia.com>
[CoordGraphics] Replace CoordinatedSurface, ThreadSafeCoordinatedSurface with CoordinatedBuffer
Modified: trunk/Source/WebCore/platform/text/BidiResolver.h (225109 => 225110)
--- trunk/Source/WebCore/platform/text/BidiResolver.h 2017-11-23 10:31:07 UTC (rev 225109)
+++ trunk/Source/WebCore/platform/text/BidiResolver.h 2017-11-23 10:45:26 UTC (rev 225110)
@@ -245,6 +245,7 @@
// FIXME: Instead of InlineBidiResolvers subclassing this method, we should
// 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;
// sor and eor are "start of run" and "end of run" respectively and correpond
@@ -277,6 +278,7 @@
void reorderRunsFromLevels();
void incrementInternal() { m_current.increment(); }
void appendRunInternal();
+ bool needsContinuePastEndInternal() const { return true; }
Vector<BidiEmbedding, 8> m_currentExplicitEmbeddingSequence;
};
@@ -292,6 +294,7 @@
void incrementInternal();
void appendRunInternal();
+ bool needsContinuePastEndInternal() const;
Vector<IsolateRun>& isolatedRuns() { return m_isolatedRuns; }
private:
@@ -880,7 +883,7 @@
break;
}
- if (pastEnd && m_eor == m_current) {
+ if (pastEnd && (m_eor == m_current || !needsContinuePastEnd())) {
if (!m_reachedEndOfLine) {
m_eor = endOfLine;
switch (m_status.eor) {
Modified: trunk/Source/WebCore/rendering/InlineIterator.h (225109 => 225110)
--- trunk/Source/WebCore/rendering/InlineIterator.h 2017-11-23 10:31:07 UTC (rev 225109)
+++ trunk/Source/WebCore/rendering/InlineIterator.h 2017-11-23 10:45:26 UTC (rev 225110)
@@ -586,4 +586,11 @@
m_status.eor = U_OTHER_NEUTRAL;
}
+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
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes
