myers-diff

[ bsd3, library, unclassified ] [ Propose Tags ]

Modules

[Index] [Quick Jump]

Flags

Manual Flags

NameDescriptionDefault
diff

Include the diff implementation from the Diff package

Disabled
uni_myers

Use the diff implementation from the "uni-util" package (buggy). This causes LGPL code to be included.

Disabled

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0, 0.2.0.0, 0.3.0.0
Change log CHANGELOG.md
Dependencies base (>=4.7 && <5), containers, exceptions, primitive, text, vector [details]
License BSD-3-Clause
Copyright 2023 Tom McLaughlin
Author Tom McLaughlin
Maintainer tom@codedown.io
Home page https://github.com/codedownio/myers-diff#readme
Bug tracker https://github.com/codedownio/myers-diff/issues
Source repo head: git clone https://github.com/codedownio/myers-diff
Uploaded by thomasjm at 2023-11-12T02:38:32Z
Distributions LTSHaskell:0.3.0.0, NixOS:0.3.0.0, Stackage:0.3.0.0
Downloads 230 total (14 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2023-11-12 [all 1 reports]

Readme for myers-diff-0.3.0.0

[back to package description]

Welcome to myers-diff Hackage myers-diff

This is a fast Haskell implementation of the Myers text diff algorithm1. It is heavily inspired by the Python version in this post, and should have the same \(O(\min(len(a), len(b)))\) space complexity. The implementation uses unboxed mutable vectors for performance.

This repo also can also build a couple other versions for benchmarking comparison, gated behind flags.

  • -funi_myers will build the version from the uni-util package.
  • -fdiff will use the Diff package.

Comparison to other libraries

The Diff package also implements the Myers algorithm, but a less space-efficient variant. That package advertises \(O(D^2)\) space complexity, where \(D\) is the number of differences between the two inputs. In the worst case, \(D = \max(len(a), len(b))\), so the space usage can be quadratic in the input length.

Benchmarks

You can generate all the benchmarks by running ./run_all_benchmarks.sh. Full results can be found in ./benchmark_results. All benchmarks were run on an Intel i9-13900K.

TL;DR:

  • These benchmarks focus on inputs of different sizes, where a single ~30 character region is either inserted or deleted.
  • myers-diff is faster by around 2.5x, and the advantage grows with larger inputs (around 100k characters).
  • myers-diff is more space-efficient by 5x for tiny inputs, shrinking to 1.5x for 10k character inputs and 1.3x for 100k character inputs.

Other benchmarks could be run, of course. Future work could involve testing inputs with multiple separated edits, and/or edits of different sizes. Please file an issue if you'd like to discuss a particular workload.

Time: small inserts

Test scenario: generate a random input of \(N\) characters, then insert a random string of \(\leq 30\) characters somewhere to produce a modified input. Generate 100 such pairs and compare the diffing time of myers-diff with Diff using criterion.

small_insert.png

Input size (chars) myers-diff Diff Speedup
10 408us 1.07ms 2.6x
100 587us 1.53ms 2.6x
1000 1.81ms 3.46ms 1.9x
10000 16.6ms 40.8ms 2.5x
100000 188ms 823ms 4.4x

Time: small deletes

Test scenario: same as for small inserts, but this time delete \(\leq 30\) characters from the second input.

small_delete.png

These results are very similar to those for small inserts.

Space: small inserts

Test scenario: same as for the small inserts time test. In this test, we measure the bytes allocated by the diffing process using weigh.

Input size (chars) myers-diff (bytes) Diff (bytes) Diff / myers-diff
10 1,681,120 8,904,176 5.3x
100 3,619,928 13,833,520 3.8x
1000 20,044,048 31,669,480 1.6x
10000 171,103,240 250,594,080 1.5x
100000 1,666,421,824 2,172,753,512 1.3x
1

E. Myers (1986). "An O(ND) Difference Algorithm and Its Variations". Algorithmica. 1 (2): 251–266. CiteSeerX 10.1.1.4.6927. doi:10.1007/BF01840446. S2CID 6996809.