Announcing `imara-diff`, a reliably performant diffing library for rust

imara-diff provides an implementation of Myers algorithm and the histogram algorithm. These allow a quick comparison of files similar to git diff or the diff utility. Compared to existing rust-crates like similar or dissimilar, the algorithms in imara-diff have been extensively optimized with heuristics similar to those used in git and gnu-diff.
As a result imara-diff significantly outperforms similar across a wide variety of real-world test data (more details in the repo).

The implementation of Myers algorithm was ported from git/gnu-diff and as such uses battle-tested heuristics. While porting the histogram I was able to improve on the original implementation from git. As a result the histogram implementation always outperforms Myers algorithm (by around 20% and for large diffs up to 2x faster) while providing more human readable output.

7 Likes

I am studying something similar recently. Can you provide some examples in your project?