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...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords: InRadar
Depends on: 179955
Blocks:
  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:


Attachments
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]
patch
Comment 2 Simon Fraser (smfr) 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
Comment 3 Antti Koivisto 2017-11-22 11:48:54 PST
Created attachment 327466 [details]
patch
Comment 4 WebKit Commit Bot 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>
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
<rdar://problem/35674834>