Limit effect of search-and-replace assessment on long documents
Closed, ResolvedPublic8 Story Points

Description

  1. Click on https://www.mediawiki.org/w/index.php?title=VisualEditor/status&veaction=edit
  2. Wait for editor to load
  3. Use find-and-replace
  4. Try to type "now support "
  5. Observe system die in flames after 'n' was typed, not letting you type 'o' yet, let alone the rest.
  6. Cry.

250ms is our normal threshold. Let's do that.

Jdforrester-WMF assigned this task to Esanders.
Jdforrester-WMF changed Security from none to None.
Jdforrester-WMF triaged this task as "Normal" priority.
Jdforrester-WMF added a subscriber: Jdforrester-WMF.

That makes it less likely to explode, but doesn't fix the problem, which is that rendering 16000 highlights is too much. There should either be a cap, or some smartness about not rendering off screen.

I wonder how much not rendering off-screen would save. You'd save on a bunch of DOM modification, but you'd still have to find every result and compute a rect for it to find out whether it's off-screen. I don't know how much time is spent in the DM search vs the highlight rendering, let's find out.

We could also refactor the DM code so it returns one result at a time instead of all at once, then stop once we hit the first off-screen result. This isn't quite perfect (there might be results in floated image captions that appear significantly above/below the text immediately before/after in the DM/DOM), and it would break the "Kth of N results" thing, so maybe we could try a hybrid approach where we only do full rendering (i.e. the current approach, maybe without off-screen highlights) if there are <=50 results, and above that we aggressively try to stop searching and rendering as soon as we can, while still allowing the user to force the next result to be found and highlighted by pressing next. Or we could base the approach on finding and rendering at most 10 results before and 10 after the currently highlighted one.

(Another problem that I don't quite have a solution for: if the user is scrolled most of the way down the page, how do you know where results start being visible without just trying them all in sequence)

Change 180195 had a related patch set uploaded (by Esanders):
Limit number of find and replace results to render

https://gerrit.wikimedia.org/r/180195

Patch-For-Review

So I considered the render on screen things, and as you point out you'd have occasional problems with floated things or worse, position absolute things. As you point it your approach doesn't help you work out where to start rendering and calculating if something is on screen is basically as expensive as rendering it (getClientRects being the bottleneck). As viable solution might be to do a binary search. Even on a document of 100k characters that would only be 16 checks.

That shouldn't be too difficult to implement, the only problem being we'd have to re-evaluate on window resize and scroll (although debounced), but being a binary search it should be efficient enough. In might even make sense to push that functionality up to the surface view, so you can just ask it to getVisibleRange.

Yeah I was thinking of binary search too, but I don't know how reliable it'll be because the DOM sequence is similar to but not the same as the rendered visual sequence (due to floated things; good call on absolute positioning but I don't think you'll see absolutely positioned editable text very often).

getVisibleRange() sounds interesting, and that may well be binary search-able if you stick to known-safe things (like .css( 'position' ) === 'static' maybe?)

getVisibleRange is only ever going to be an estimate due to floats and position absolute, and you'll probably add +/- 50% for good measure. Throwing in a computed style calls ( .css('position') ) is going to make it several times slower.

Change 180635 had a related patch set uploaded (by Esanders):
Use viewport clipping when lots of search results found

https://gerrit.wikimedia.org/r/180635

Patch-For-Review

Jdforrester-WMF moved this task from TR7: ???? to TR5: Rich media tools on the VisualEditor board.
Jdforrester-WMF changed the title from "De-bounce search-and-replace assessment until after user has finished typing" to "Limit effect of search-and-replace assessment on long documents".

Change 180195 merged by jenkins-bot:
Limit number of find and replace results to render

https://gerrit.wikimedia.org/r/180195

Change 180635 merged by jenkins-bot:
Use viewport clipping when lots of search results found

https://gerrit.wikimedia.org/r/180635

This is now better, but not great in very extreme cases.