Bug 264076

Summary: SVGTextMetricsBuilder::measureTextRenderer exhibits O(n^2) behavior
Product: WebKit Reporter: Ryosuke Niwa <rniwa>
Component: SVGAssignee: 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

Description Ryosuke Niwa 2023-11-01 20:07:40 PDT 
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>
Comment 1 Ryosuke Niwa 2023-11-01 20:09:12 PDT 
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
Comment 2 Ryosuke Niwa 2023-11-01 21:13:35 PDT 
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).
Comment 3 Ryosuke Niwa 2023-11-01 23:23:06 PDT 
Pull request: https://github.com/WebKit/WebKit/pull/19877
Comment 4 EWS 2023-11-02 08:57:11 PDT 
Committed 270110@main (1f27ea47a392): <https://commits.webkit.org/270110@main>

Reviewed commits have been landed. Closing PR #19877 and removing active labels.