Pasting a 4MB JSON into prism.js spends 4+ min in culled-inline hit-tests

#454861482 Filed 2025-10-25 Status: Accepted (P3 / S3) CL 8604967

Summary

Problem

Prism.js builds many thousands of culled inline <span>s per line to color-code a syntax-highlighted block. Hit-testing (e.g. the spellcheck or caret-position queries that follow pasting) walks each line with an InlineCursor and calls InlineCursor::MoveToFirstForCulledInline once per culled inline. On a descendants cursor that function scans every fragment item in the cursor's range -- fine for a short line, O(line_length) per inline otherwise. With N culled inlines on one line that's O(N^2): pasting a 4MB JSON file spent 4+ minutes in IsPartOfCulledInlineBox. Firefox finishes in 6s.

Fix (CL 8604967)

When the culled inline has at most 8 LayoutObject descendants (common case: an inline tag with a short text run), skip the fragment scan and walk the LayoutObject descendants directly. The counting walk itself stops at 9. Large culled inlines still take the fragment-scan path to preserve the behavior from crbug.com/1008523. MoveToNextCulledInlineDescendantIfNeeded now applies IsPartOfCulledInlineBox as a filter on the descendants-cursor path so atomic inlines inside the culled inline (e.g. <img>) are skipped, matching the fragment-scan semantics.

Benchmark (2000 culled inlines, one line, 80 elementFromPoint calls)

buildminmedianmaxper hit
stable Chromium 155 (pre-fix) 4267 ms 4458 ms 4715 ms 55.72 ms
content_shell w/ CL 8604967 (release) 20.8 ms 22.2 ms 26.0 ms 0.28 ms
median per-hit speedup ~200x

sampler -- 2000 spans, elementFromPoint benchmark

Live benchmark in your browser. Click "run benchmark". On stable Chrome expect ~4-5 s total; on patched Chrome ~a few hundred ms.
before: system Chromium stable
System Chromium 155 (pre-fix). ~57 ms per elementFromPoint call.
after: patched content_shell
content_shell with CL 8604967 (release build). ~0.28 ms per hit.

content_shell: before / after

pre-fix benchmark output
beforestable Chromium 155, 2000 spans
post-fix benchmark output
aftercontent_shell + CL 8604967, same input

Unit tests

Three new tests in inline_cursor_test.cc pin the two branches of MoveToFirstForCulledInline plus the atomic-inline filter in MoveToNextCulledInlineDescendantIfNeeded:

• CulledInlineDescendantsCursorSmallCulledInline -- <=8 descendants, uses the LayoutObject-walk branch (UsesFragmentTreeForCulledInlineForTesting() == false).

• CulledInlineDescendantsCursorLargeCulledInline -- 9 descendants, still takes the fragment-scan branch (regression guard for crbug/1008523).

• CulledInlineDescendantsCursorWithAtomicInline -- an <img> inside the culled inline is skipped by the descendants-cursor filter, matching the fragment-scan semantics.

References

crbug.com/454861482 -- original report (filed 2025-10-25)

CL 8604967 -- Avoid quadratic culled-inline lookups when hit-testing long lines

crbug.com/1008523 -- original reason for the fragment-scan path on descendants cursors

Samply profile from the reporter

standalone sampler.html