Bug 129065

Summary: Render tree construction is O(N^2) in number of siblings
Product: WebKit Reporter: Maciej Stachowiak <mjs>
Component: Layout and RenderingAssignee: Nobody <webkit-unassigned>
Status: RESOLVED FIXED    
Severity: Normal CC: abarth, aroben, bjonesbe, dbates, koivisto, lvidacs.u-szeged, ossy, sergio, sun.shin, tgergely.u-szeged
Priority: P2 Keywords: InRadar
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
URL: http://jsfiddle.net/vwG2J/2/
Attachments:
Description Flags
patch darin: review+

Description Maciej Stachowiak 2014-02-19 14:47:09 PST
Render tree construction is O(N^2) in the number of sibling nodes.

Here is a test case and JSFiddle link demonstrating the issue; if you create 10x as many nodes, the time growth is approximately quadratic, rather than linear.

var t = Date.now();
for (var i = 0; i < 5000; ++i)
  document.body.appendChild(document.createElement('div'));
document.body.offsetTop;
document.body.textContent = Date.now() - t;

http://jsfiddle.net/vwG2J/2/


Blink fixed this by assembling the Render tree (approximately) backwards:
https://codereview.chromium.org/24350009


I am not sure offhand if this is the best or only solution.
Comment 1 Maciej Stachowiak 2014-02-19 14:48:48 PST
<rdar://problem/16114572>
Comment 2 Antti Koivisto 2014-03-25 09:22:11 PDT
Created attachment 227760 [details]
patch
Comment 3 Darin Adler 2014-03-25 09:36:10 PDT
Comment on attachment 227760 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=227760&action=review

The approach here looks good. The details are a little confusing.

> Source/WebCore/style/StyleResolveTree.cpp:7
> + * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2012, 2013, 2014 Apple Inc. All rights reserved.

We learned recently that year ranges are OK. So this should say:

    2004-2010, 2012-2014

> Source/WebCore/style/StyleResolveTree.cpp:75
> +    RenderObject* before;

The name “before” here is not so great. We name the other member “parent”, not “above” or “containing”, despite the fact that it’s not really the parent of anything. I think this might be clearer as “nextSibling”.

> Source/WebCore/style/StyleResolveTree.cpp:76
> +    bool isValid;

I don’t think that from this name it’s clear that isValid is specifically about the before field. I think it should probably be named nextSiblingPointerIsValid.

I find that the rules for when a RenderTreePosition is valid and when it might not be are confusing.

> Source/WebCore/style/StyleResolveTree.cpp:78
> +    unsigned assertCount;

I would call this assertionLimitCounter.

> Source/WebCore/style/StyleResolveTree.cpp:237
> +static void computeRenderTreePositionIfNeeded(RenderTreePosition& renderTreePosition, const Node& node, ContainerNode& renderingParentNode)

I don’t think the IfNeeded suffix in these two function names helps. I would just take it out.

> Source/WebCore/style/StyleResolveTree.cpp:249
> +static void invalidateRenderTreePositionIfNeeded(RenderTreePosition& renderTreePosition, const Node& node)

I don’t think the IfNeeded suffix in these two function names helps. I would just take it out.

> Source/WebCore/style/StyleResolveTree.cpp:280
> +    ASSERT(renderTreePosition.isValid);

Making the position a little more of a class would be good. Then the assertion that the pointer is valid could be a part of the getter rather than something we assert here, but use elsewhere.

> Source/WebCore/style/StyleResolveTree.cpp:285
> +        insertionPosition.before = parentFlowRenderer->nextRendererForElement(element);

It’s strange and subtle that we rely on the fact that isValid is already set here.

> LayoutTests/fast/css/sibling-renderer-On2.html:11
> +shouldBe("timeRenderTreeCreation(5000) < 20 * timeRenderTreeCreation(500)", "true");

I’m surprised you made a custom test here. I would have suggested instead doing a LayoutTests/perf test; those are designed to check that things are linear.

But perhaps the number "20" here is related to the the number "20" in the assertion limit count for debug builds?
Comment 4 Antti Koivisto 2014-03-25 09:41:56 PDT
> I’m surprised you made a custom test here. I would have suggested instead doing a LayoutTests/perf test; those are designed to check that things are linear.

I didn't know about LayoutTests/perf. It is not immediately obvious to me how they are better but I'll move/refactor the test.

> But perhaps the number "20" here is related to the the number "20" in the assertion limit count for debug builds?

No it isn't.
Comment 5 Antti Koivisto 2014-03-26 11:38:43 PDT
https://trac.webkit.org/r166303

Factored RenderTreePosition to be more of a class.
Moved the test to LayoutTests/perf but didn't use magnitude-perf.js as it seemed unsuitable for a something that requires a relatively long testing function (it calls the function many times).