refactor(web): context operations should use a sliding window
- Dominant language
- Pascal
- Stars
- 534
- Forks
- 143
- Avg merge
- 2d 10h
- Merged PRs (30d)
- 113
Description
> ...
>
> 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 https://github.com/keymanapp/keyman/issues/5248#issuecomment-858198679_
Contributor guide
Assessment
This issue has not been assessed yet.