RESOLVED FIXED Bug 179950
RenderBlockFlow::layoutRunsAndFloatsInRange is O(n^2) for runs of inlines without any text 
https://bugs.webkit.org/show_bug.cgi?id=179950
Summary RenderBlockFlow::layoutRunsAndFloatsInRange is O(n^2) for runs of inlines wit...
Antti Koivisto
Reported 2017-11-22 08:35:44 PST
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.
Attachments
patch (2.18 KB, patch)
2017-11-22 08:38 PST, Antti Koivisto 		simon.fraser: review+
DetailsFormatted DiffDiff
patch (3.73 KB, patch)
2017-11-22 11:48 PST, Antti Koivisto 		no flags
DetailsFormatted DiffDiff
Show Obsolete (1) View All Add attachment proposed patch, testcase, etc.
Antti Koivisto
Comment 1 2017-11-22 08:38:09 PST
Created attachment 327456 [details] patch
Simon Fraser (smfr)
Comment 2 2017-11-22 09:01:18 PST
Comment on attachment 327456 [details] patch View in context: https://bugs.webkit.org/attachment.cgi?id=327456&action=review > Source/WebCore/platform/text/BidiResolver.h:248 > + bool needsContinuePastEnd() { return static_cast<DerivedClass&>(*this).needsContinuePastEndInternal(); } make the function const. > Source/WebCore/platform/text/BidiResolver.h:281 > + bool needsContinuePastEndInternal() { return true; } const > Source/WebCore/platform/text/BidiResolver.h:297 > + bool needsContinuePastEndInternal(); const > Source/WebCore/rendering/InlineIterator.h:590 > +inline bool InlineBidiResolver::needsContinuePastEndInternal() const
Antti Koivisto
Comment 3 2017-11-22 11:48:54 PST
Created attachment 327466 [details] patch
WebKit Commit Bot
Comment 4 2017-11-23 02:45:29 PST
Comment on attachment 327466 [details] patch Clearing flags on attachment: 327466 Committed r225110: <https://trac.webkit.org/changeset/225110>
WebKit Commit Bot
Comment 5 2017-11-23 02:45:31 PST
All reviewed patches have been landed. Closing bug.
Radar WebKit Bug Importer
Comment 6 2017-11-23 02:46:25 PST
<rdar://problem/35674834>
Note You need to log in before you can comment on or make changes to this bug.