Skip to content

[PROPOSAL] Replace diff crate with a Myers diff implementation #401

Open

Description

@shadowmkj

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:

  1. similar crate: Permissively licensed (Apache-2.0), mature, and widely adopted clean-room
    linear-space Myers implementation by Armin Ronacher.
  2. 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.

References:
https://github.com/utkarshkukreti/diff.rs
https://github.com/mitsuhiko/similar

Do you have a preference between using similar vs. an in-tree implementation?

I would like to work on this implementation, opened this issue to have more discussion on this
matter.

Activity

  1. shadowmkj commented on Nov 16, 2026

    @shadowmkj
    ContributorAuthor

    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

  2. sylvestre commented on Nov 17, 2026

    @sylvestre
    SponsorCollaborator

    similar sounds great!
    it is a quite popular crate

  3. shadowmkj commented on Nov 17, 2026

    @shadowmkj
    ContributorAuthor

    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.

    Screenshot 2026-11-18 at 12 07 28 AM

    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.

    image

    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!

  4. sylvestre commented on Nov 17, 2026

    @sylvestre
    SponsorCollaborator

    Please replace the screenshot by text. Screenshots are terrible for search and accessiblity

  5. sylvestre commented on Nov 17, 2026

    @sylvestre
    SponsorCollaborator

    I prefer the similar approach. Let use what already exists!

  6. shadowmkj commented on Nov 17, 2026

    @shadowmkj
    ContributorAuthor

    541KB (10k lines)

    Command Mean [ms] Min [ms] Max [ms] Relative
    ./old_diff bench_data/med_sparse_a.txt bench_data/med_sparse_b.txt 185.3 ± 6.2 181.8 208.3 44.59 ± 3.51
    ./new_diff bench_data/med_sparse_a.txt bench_data/med_sparse_b.txt 4.2 ± 0.3 3.9 7.9 1.00

    2.7MB (50k lines)

    Command Mean [s] Min [s] Max [s] Relative
    ./old_diff bench_data/large_sparse_a.txt bench_data/large_sparse_b.txt 3.914 ± 0.026 3.890 3.977 547.01 ± 15.57
    ./new_diff bench_data/large_sparse_a.txt bench_data/large_sparse_b.txt 0.007 ± 0.000 0.007 0.008 1.00
    
    
  7. shadowmkj commented on Nov 17, 2026

    @shadowmkj
    ContributorAuthor

    I prefer the similar approach. Let use what already exists!

    Sure! I will open a PR soon 😄

  8. shadowmkj commented on Nov 17, 2026

    @shadowmkj
    ContributorAuthor

    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.

  9. sylvestre commented on Nov 17, 2026

    @sylvestre
    SponsorCollaborator

    are you sure about these benchs? they were both built with --release?

  10. shadowmkj commented on Nov 17, 2026

    @shadowmkj
    ContributorAuthor

    are you sure about these benchs? they were both built with --release?

    Yes I'm sure.

  11. shadowmkj commented on Nov 17, 2026

    @shadowmkj
    ContributorAuthor

    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

    The benchmark for that is posted in #415

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions