Bug 179950 - RenderBlockFlow::layoutRunsAndFloatsInRange is O(n^2) for runs of inlines without any text
Summary: RenderBlockFlow::layoutRunsAndFloatsInRange is O(n^2) for runs of inlines wit...
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
Keywords: InRadar
Depends on: 179955
  Show dependency treegraph
Reported: 2017-11-22 08:35 PST by Antti Koivisto
Modified: 2017-11-23 02:46 PST (History)
5 users (show)

See Also:

patch (2.18 KB, patch)
2017-11-22 08:38 PST, Antti Koivisto
simon.fraser: review+
Details | Formatted Diff | Diff
patch (3.73 KB, patch)
2017-11-22 11:48 PST, Antti Koivisto
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Antti Koivisto 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.
Comment 1 Antti Koivisto 2017-11-22 08:38:09 PST
Created attachment 327456 [details]
Comment 2 Simon Fraser (smfr) 2017-11-22 09:01:18 PST
Comment on attachment 327456 [details]

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; }


> Source/WebCore/platform/text/BidiResolver.h:297
> +    bool needsContinuePastEndInternal();


> Source/WebCore/rendering/InlineIterator.h:590
> +inline bool InlineBidiResolver::needsContinuePastEndInternal()

Comment 3 Antti Koivisto 2017-11-22 11:48:54 PST
Created attachment 327466 [details]
Comment 4 WebKit Commit Bot 2017-11-23 02:45:29 PST
Comment on attachment 327466 [details]

Clearing flags on attachment: 327466

Committed r225110: <https://trac.webkit.org/changeset/225110>
Comment 5 WebKit Commit Bot 2017-11-23 02:45:31 PST
All reviewed patches have been landed.  Closing bug.
Comment 6 Radar WebKit Bug Importer 2017-11-23 02:46:25 PST