Custom Diffing Implementation

[kirawi]

Currently, we depend upon similar to provide the diffing we need for :reload and in the future, file comparison (#405). However, this comes with a few drawbacks: (a) it can only operate on contiguous data, and (b) it is too expensive to calculate on moderately sized, extremely different files. A big part of that is our need to temporarily convert the Rope representation of the text into a String as Ropes are not a contiguous data structure. A histogram implementation and/or incorporating SIMD may also improve real-world performance, but it would not affect the time complexity of the algorithm which is currently O(n + (N+M)D).

Our main priority should be to investigate an alternative algorithm for :reload that can efficiently calculate a diff without human readability in mind, rsync, and how we can adapt these algorithms to be able to work on a Rope directly. I suspect that implementing the rsync algorithm would be the easiest one to tackle.

This is a difficult solution to a difficult problem, but it would be nice to have.

[kirawi]

Pijul also recently rolled their own rsync implementation.

[kirawi]

https://docs.rs/xi-rope/latest/xi_rope/diff/index.html

[kirawi]

Will close in favor of #4457. That implementation is significantly faster for expected workloads.