Summary: | Render tree construction is O(N^2) in number of siblings | ||||||
---|---|---|---|---|---|---|---|
Product: | WebKit | Reporter: | Maciej Stachowiak <mjs> | ||||
Component: | Layout and Rendering | Assignee: | 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
Maciej Stachowiak
2014-02-19 14:47:09 PST
Created attachment 227760 [details]
patch
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? > 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. 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). |