Performance regression when selecting multiple "lines" with line-wrapping enabled

[krassowski]

Describe the issue

Downstream issue: jupyterlab/jupyterlab#18456

546213769-c35e0204-1825-490e-9994-46b7cf88e780.mp4

This started happening on upgrade. JupyterLab v4.5.3 pulled in:

@codemirror/autocomplete ^6.18.6 -> ^6.20.0
@codemirror/commands ^6.8.1 -> ^6.10.1
@codemirror/lang-cpp ^6.0.2 -> ^6.0.3
@codemirror/lang-html ^6.4.9 -> ^6.4.11
@codemirror/lang-java ^6.0.1 -> ^6.0.2
@codemirror/lang-javascript ^6.2.3 -> ^6.2.4
@codemirror/lang-json ^6.0.1 -> ^6.0.2
@codemirror/lang-markdown ^6.3.2 -> ^6.5.0
@codemirror/lang-php ^6.0.1 -> ^6.0.2
@codemirror/lang-python ^6.2.0 -> ^6.2.1
@codemirror/lang-rust ^6.0.1 -> ^6.0.2
@codemirror/lang-sql ^6.8.0 -> ^6.10.0
@codemirror/language ^6.11.0 -> ^6.12.1
@codemirror/legacy-modes ^6.5.1 -> ^6.5.2
@codemirror/search ^6.5.10 -> ^6.6.0
@codemirror/state ^6.5.2 -> ^6.5.4
@codemirror/view ^6.38.1 -> ^6.39.11

The issue persists after upgrade to latest versions:

@codemirror/commands ^6.10.1 -> ^6.10.2
@codemirror/view ^6.39.11 -> ^6.39.13

Profile:

Zoomed in:

The trace leads posAtCoordsInline which was rewritten 3 months ago (in view 6.39.0) in codemirror/view@12ff19d. Its documentation mentions that a binary search could be used. Maybe it would help indeed.

// Scan through the rectangles for the content of a tile, finding the
// one closest to the given coordinates, prefering closeness in Y over
// closeness in X.
//
// If this is a text tile, go character-by-character. For line or mark
// tiles, check each non-point-widget child, and descend text or mark
// tiles with a recursive call.
//
// For non-wrapped, purely left-to-right text, this could use a binary
// search. But because this seems to be fast enough, for how often it
// is called, there's not currently a specialized implementation for
// that.
function posAtCoordsInline(view, tile, offset, x, y) {

The exact lines of code which contribute to slowness according to sampling profiler (which might be off):

Important

The reproducer only reproduces on a wide screen (2k or 4k or ultrawide HD) and requires either hiding the source code panel on the demo website or increasing max-width of the article in CSS:

Browser and platform

Chrome

Reproduction link

https://codemirror.net/try/#c=aW1wb3J0IHtiYXNpY1NldHVwLCBFZGl0b3JWaWV3fSBmcm9tICJjb2RlbWlycm9yIgppbXBvcnQge3B5dGhvbn0gZnJvbSAiQGNvZGVtaXJyb3IvbGFuZy1weXRob24iCgoKbmV3IEVkaXRvclZpZXcoewogIGRvYzogSlNPTi5zdHJpbmdpZnkoeyJ4IjogQXJyYXkoMzAwMCkuZmlsbCgicXdlcnR5dWlvcCIpfSksCiAgZXh0ZW5zaW9uczogW2Jhc2ljU2V0dXAsIHB5dGhvbigpLCBFZGl0b3JWaWV3LmxpbmVXcmFwcGluZ10sCiAgcGFyZW50OiBkb2N1bWVudC5ib2R5Cn0pCg==