RESOLVED FIXED 264076
SVGTextMetricsBuilder::measureTextRenderer exhibits O(n^2) behavior 
https://bugs.webkit.org/show_bug.cgi?id=264076
Summary SVGTextMetricsBuilder::measureTextRenderer exhibits O(n^2) behavior
Ryosuke Niwa
Reported 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>
Attachments
Add attachment proposed patch, testcase, etc.
Ryosuke Niwa
Comment 1 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
Ryosuke Niwa
Comment 2 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).
Ryosuke Niwa
Comment 3 2023-11-01 23:23:06 PDT
Pull request: https://github.com/WebKit/WebKit/pull/19877
EWS
Comment 4 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.
Note You need to log in before you can comment on or make changes to this bug.