jsdiff
jsdiff copied to clipboard
kpdecker
Near Endless Loop calling execEditLength
I was noticing an endless hang when using mocha and filed this issue and managed to run down the problem in mocha to the use of jsdiff. Their use of createPatch here seems to cause an almost endless loop.
While it would eventually fail once maxEditLength is exceeded this would take ages as diagonalPath grows at the rate of editLength here.
The test has a maxEditLength of 57579 and even after about ~10 minutes of processing editLength is only 4542. Sadly it gets exponential worse.
We have had some pathological diff cases in the past. Some of that is inherent with the algorithm but we may be able to perform some optimization steps.
It's not ideal, but using the async mode along with a timeout could at least protect the mocha case from massive amounts of developer frustration while this is being investigated (I don't have a whole bunch of time to look into this in the near term unfortunately)
I can reproduce the slowness if I try diffing c.json and d.json from your repo using diff.diffJson; I'm not 100% certain if that matches the behaviour when running Mocha, but it'll do as a test case.
https://github.com/kpdecker/jsdiff/pull/411 will improve this somewhat, but even after that change this test case is still slow. I note in the description of that PR that there is room to improve performance further, but fundamentally I suspect there are always gonna be performance problems when diffing texts with a huge edit distance like, since the Myers diff algorithm is in the worst case an O(n + d^2) algorithm. I don't want to definitively write off getting this test case down to near-instant speed as an impossible fantasy until I've figured out rigorously what the hard limits on speed are, but I am not optimistic that anything we can do is gonna make that particular diff tolerably fast to compute.
