perf: don't process the entire body of text for every movement

[mcauley-penney]

As of right now, the plugin gets the entire visual selection and parses it for whitespace on every CursorMoved. For example, if we have 100 lines selected and we move down one line, we get the entire 101 lines and parse it again, despite extmarks already existing. We do not need to parse the entire thing again.

We should be able to improve performance by only parsing the text between the last cursor position during visual mode and the current cursor position. For example, instead of parsing the entire 100 lines again just to add extmarks to one line, start at the last cursor position (row, col) and just parse up to the new row col.

[mcauley-penney]

It is also setting new marks for existing marked positions on all CursorMoved events. For example, if you have the text "Lorem ipsum" and you have highlighted "Lorem " (including the space), charwise movements across "ipsum" seem to set more marks for that space, but I don't know why just yet. This creates large amounts of extmarks.

Edit: I have two ideas to address this:

1. only loop to set marks when "advancing", i.e. expanding the visual selection

• This also allows us to skip parsing new text when not advancing

2. keep a set of marks so that we reject setting marks at previously seen positions.

• This allows us to skip the nvim_buf_get_extmarks() call we make on every movement, though we could also do this by only deleting marks when we are not "advancing". We could do both: only make the deletion call on advancement and keep a set of marks so that we can avoid duplicate entries. This means making the deletion call far less often and not using an API call when we do, though the API call is pretty nice because it reduces complexity.

[mcauley-penney]

5676c99 improves deletion speed at least for large selections in charwise visual. For some large files I tested on, this is a dramatic improvement. Specifically, some papers in LaTeX, with many wrapped lines, were much smoother.

[mcauley-penney]

The incremental-hl branch (which builds off of the getregionpos branch) implements incremental processing of the visually selected content. If the user makes a visual selection then expands it, only the newly selected content will be processed (with duplicated processing on the connecting boundary of the selection, for the sake of simplicity of the algorithm). If the user contracts/shrinks the visually selected area, only the extmarks that are no longer under visual selection will be deleted. This means we don't have to reprocess the entire selection on every movement.

We attempted using interval trees and had a functioning implementation, but it was orders of magnitude slower: 1.2 to 1.5 seconds to instantiate the tree, while our naive approach is around 0.000025 seconds for a single line, or around 0.000300 seconds for a large update at once (e.g. visually selecting an entire function with a keymap). The code is complex, but the speed is nice. We need to refactor