...

Still, it does just move the goalposts. As expected, when I tested with longer documents, I observed linear growth in script time. So this still fails with long documents -- and not all that long really, with just over 1 page of text in a note, I saw 160msec/key event which is barely tolerable. This is on a relatively fast device (for Android), so slower devices would probably be completely unusable with that much content.

The big problem in this whole algorithm is that it is ever scanning the whole document. That's not limited to this one function, but to the whole approach, I think. That seems completely unnecessary: we're never going to have a keyboard that affects more than the last few characters.

We should be working with a sliding window, say 128 code units either side of the caret. Is this possible to achieve? We may still need to iterate through the document once to get our relative code point base for the sliding window but that should be done just once for a keystroke and would then be relatively inconsequential.

I know that all our indexing is by document position, so it may be a significant challenge to rewrite it. But improved algorithms are only going to take us so far and I think we may need to consider this for a full fix.

As noted, this is important... but is also definitely not trivial.

In terms of context passed through to the KeyboardProcessor, there would be little problem. As noted, keystrokes don't ever have that wide a range of effect.

The major pain point would be retooling how suggestions and reversions are applied. The process for both involves comparing the "before" snapshot with the current context state, which gets tricky when context is represented by sliding windows. It does seem possible, though.

I do think we should have a "design" round before making such a change. There are a number of ramifications to think through, especially given how critical context synchronization is when embedded within the mobile apps.

Originally posted by @jahorton in #5248 (comment)