You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
[PROPOSAL] Replace diff crate with a Myers diff implementation #401
Looking through the formatters (normal_diff, unified_diff, etc.), all five engines currently
rely on the external diff crate via diff::slice.
There are a couple of drawbacks with this crate:
It is poorly maintained (hasn't had a commit in over 2 years)
It builds an unoptimized 2D matrix table for LCS, which gets very memory-heavy and slow on large
files with many changes.
GNU diffutils uses Eugene Myers' algorithm with linear-space divide-and-conquer. Moving to Myers
would align us much closer to GNU diff's behavior and make large comparisons significantly faster
and lighter on memory.
Because all formatters only call diff::slice(&left, &right) and match on Left/Right/Both,
the surface area to replace it is very small. A couple of clean-room options:
similar crate: Permissively licensed (Apache-2.0), mature, and widely adopted clean-room
linear-space Myers implementation by Armin Ronacher.
In-tree clean-room Myers engine: Implementing the linear-space algorithm from Myers' 1986
paper directly in the repository to avoid adding any new external dependencies.
I have been researching more about Myers Diff algorithm. I think I can implement a drop-in replacement for the diff crate currently in use. I am working on this as a separate small crate for now, just to figure out things. Then I will benchmark this with current implementation
I already implemented a version of this myself, just over 1k lines of rust.
A 541KB file (10k lines) with sparse differences, it performed 30 times faster.
A 2.7MB file (50k lines) with sparse differences, it performed 555 times faster.
The algorithm performs better when the size of the file is large, and difference is sparse.
All benchmarks are done using hyperfine and on my Macbook Air M2
Since you prefer the similar crate approach, I'll open a PR implementing it soon. Thanks!
We should add benches for files that differ. Currently there is only benchmarks set for files that are same, this is not a enough to compare against GNU as the diff_engine does not work for same files.
I compared my implementation against the similar crate implemntation and got similar performance.
But similar crate gives so much better performance when comparing against GNU diff
Activity
shadowmkj commentedon Nov 16, 2026
I have been researching more about Myers Diff algorithm. I think I can implement a drop-in replacement for the
diffcrate currently in use. I am working on this as a separate small crate for now, just to figure out things. Then I will benchmark this with current implementationsylvestre commentedon Nov 17, 2026
similar sounds great!
it is a quite popular crate
shadowmkj commentedon Nov 17, 2026
I already implemented a version of this myself, just over 1k lines of rust.
A
541KBfile (10k lines) with sparse differences, it performed 30 times faster.A
2.7MBfile (50k lines) with sparse differences, it performed 555 times faster.The algorithm performs better when the size of the file is large, and difference is sparse.
All benchmarks are done using
hyperfineand on myMacbook Air M2Since you prefer the
similarcrate approach, I'll open a PR implementing it soon. Thanks!sylvestre commentedon Nov 17, 2026
Please replace the screenshot by text. Screenshots are terrible for search and accessiblity
sylvestre commentedon Nov 17, 2026
I prefer the similar approach. Let use what already exists!
shadowmkj commentedon Nov 17, 2026
541KB (10k lines)
./old_diff bench_data/med_sparse_a.txt bench_data/med_sparse_b.txt./new_diff bench_data/med_sparse_a.txt bench_data/med_sparse_b.txt2.7MB (50k lines)
./old_diff bench_data/large_sparse_a.txt bench_data/large_sparse_b.txt./new_diff bench_data/large_sparse_a.txt bench_data/large_sparse_b.txtshadowmkj commentedon Nov 17, 2026
Sure! I will open a PR soon 😄
shadowmkj commentedon Nov 17, 2026
We should add benches for files that differ. Currently there is only benchmarks set for files that are same, this is not a enough to compare against
GNUas the diff_engine does not work for same files.sylvestre commentedon Nov 17, 2026
are you sure about these benchs? they were both built with --release?
shadowmkj commentedon Nov 17, 2026
Yes I'm sure.
shadowmkj commentedon Nov 17, 2026
I compared my implementation against the
similarcrate implemntation and got similar performance.But
similarcrate gives so much better performance when comparing againstGNU diffThe benchmark for that is posted in #415