Bug 264076
| Summary: | SVGTextMetricsBuilder::measureTextRenderer exhibits O(n^2) behavior | ||
|---|---|---|---|
| Product: | WebKit | Reporter: | Ryosuke Niwa <rniwa> |
| Component: | SVG | Assignee: | Ryosuke Niwa <rniwa> |
| Status: | RESOLVED FIXED | ||
| Severity: | Normal | CC: | cdumez, darin, sabouhallawa, zimmermann |
| Priority: | P2 | Keywords: | InRadar |
| Version: | Safari Technology Preview | ||
| Hardware: | Unspecified | ||
| OS: | Unspecified | ||
| See Also: | https://bugs.webkit.org/show_bug.cgi?id=262192 | ||
Ryosuke Niwa
According to Yusuke’s analysis, we’re calling SVGTextMetricsBuilder::measureTextRenderer on the same RenderSVGText multiple times per layout.
> RenderSVGText::willLayout's m_layoutAttributesBuilder.rebuildMetricsForTextRenderer first runs SVGTextMetricsBuilder::measureTextRenderer for each child RenderSVGInlineText. And then, in layout, we run m_layoutAttributesBuilder.buildLayoutAttributesForForSubtree, which runs measureTextRenderer again.
To reproduce the issue, visit https://speedometer-preview.netlify.app/?developerMode=&tags=svg#details and activate "Start Test".
<rdar://117778942>
| Attachments | ||
|---|---|---|
| Add attachment proposed patch, testcase, etc. |
Ryosuke Niwa
Somehow this stuff seems even worse. We're repeatedly calling SVGTextMetricsBuilder::measureTextRenderer on the same sequence of RenderSVGInlineText over and over as we progress through the render tree. This is likelky O(n^2).
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0c2860 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0c9770 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0c9980 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0c9b90 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0c9e40 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0c9770 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0c9980 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0c9b90 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0c9e40 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0c9fb0 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0ca260 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0ca3d0 data=0x16b9fb178
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0ca680 data=0x16b9fb178
SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer text=0x14f090500
SVGTextMetricsBuilder::measureTextRenderer text=0x14f090500 data=0x16b9fd2a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f090500 data=0x16b9fd2a8
SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer text=0x14f090ac0
SVGTextMetricsBuilder::measureTextRenderer text=0x14f090ac0 data=0x16b9fd2a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f090ac0 data=0x16b9fd2a8
SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer text=0x14f091080
SVGTextMetricsBuilder::measureTextRenderer text=0x14f091080 data=0x16b9fd2a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f091080 data=0x16b9fd2a8
SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer text=0x14f091640
SVGTextMetricsBuilder::measureTextRenderer text=0x14f091640 data=0x16b9fd2a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f091640 data=0x16b9fd2a8
SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer text=0x14f091c00
SVGTextMetricsBuilder::measureTextRenderer text=0x14f091c00 data=0x16b9fd2a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f091c00 data=0x16b9fd2a8
SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer text=0x14f0a8d60
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a8d60 data=0x16b9fd5a8
SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer text=0x14f0a8f70
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a8d60 data=0x16b9fd5a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a8f70 data=0x16b9fd5a8
SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer text=0x14f0a9180
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a8d60 data=0x16b9fd5a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a8f70 data=0x16b9fd5a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a9180 data=0x16b9fd5a8
SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer text=0x14f0a9390
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a8d60 data=0x16b9fd5a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a8f70 data=0x16b9fd5a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a9180 data=0x16b9fd5a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a9390 data=0x16b9fd5a8
SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer text=0x14f0a9640
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a8d60 data=0x16b9fd5a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a8f70 data=0x16b9fd5a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a9180 data=0x16b9fd5a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a9390 data=0x16b9fd5a8
SVGTextMetricsBuilder::measureTextRenderer text=0x14f0a9640 data=0x16b9fd5a8
SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer text=0x14f0a97b0
Ryosuke Niwa
Yeah, this stuff is definitely O(n^2). RenderSVGText::willLayout(), for example, calls SVGTextLayoutAttributesBuilder::rebuildMetricsForTextRenderer on each descendant RenderObject, which in turn calls SVGTextMetricsBuilder::measureTextRenderer on each. But this function will do a tree walk from the ancestor RenderSVGText until the specified node (i.e. for n-th node, we'd traverse n nodes). So this is O(1+2+3+ ... +n) = O(n^2).
Ryosuke Niwa
Pull request: https://github.com/WebKit/WebKit/pull/19877
EWS
Committed 270110@main (1f27ea47a392): <https://commits.webkit.org/270110@main>
Reviewed commits have been landed. Closing PR #19877 and removing active labels.