icdiff hanging on large files about icdiff

[jeffkaufman]

This is an issue in python's difflib. You can get diff.py from https://docs.python.org/3/library/difflib.html and you'll see python3 diff.py file1.txt file2.txt hangs (or just is very slow).

I think this is "expected behavior" for difflib: "The basic Ratcliff-Obershelp algorithm is cubic time in the worst case and quadratic time in the expected case. SequenceMatcher is quadratic time for the worst case and has expected-case behavior dependent in a complicated way on how many elements the sequences have in common; best case time is linear." --https://docs.python.org/3.5/library/difflib.html#difflib.SequenceMatcher

You could consider filing a bug on difflib, or contributing something there that improves worst-case behavior?

[mattrussell2]

Is adding an option to use cdifflib something you'd consider?

https://stackoverflow.com/a/66694154/8742968

https://pypi.org/project/cdifflib/

[jeffkaufman]

@mattrussell2 I think that wouldn't solve the problem? Skimming that package. It looks like a re-implementation in C, but still the same algorithm?

(It's also missing some parts of difflib that icdiff depends on, but that might not be insurmountable?)

[mattrussell2]

Fair enough. Yeah 4x is certainly not going to fix polynomial-time issues.

If anyone's interested, the relevant issue re: difflib is here: python/cpython#51180

[mattrussell2]

What about using google's diff-match-patch?

https://github.com/google/diff-match-patch

This also takes an optional timeout parameter.

From my very quick reading of the source code here, seems like this library should be interoperable....but I'll dig into it a bit more.