Re-enable an important optimization in the Myers diff algorithm.

Review Request #5228 — Created Jan. 9, 2014 and submitted — Latest diff uploaded

Information

Review Board
release-1.7.x

Reviewers

Re-enable an important optimization in the Myers diff algorithm.

There's an optimization we turned off many years ago in MyersDiffer
that results in excessively long diff times for very large files. This
was the source of some huge CPU spikes and memory usage, especially if
users dogpiled on the review request.

We turned this off in the early days of Review Board, and the commit
message was vague about why. It seems that it resulted in a breakage
with some diffs. I have not been able to reproduce this, and this part
of the algorithm matches GNU diff's perfectly. I know we've made other
fixes to the differ since then, so most likely, the breakage was due to
one of those.

To ensure compatibility with older diffs, I've bumped the diff compat
version. If it turns out that this does break things, we can easily
revert it, and test manually with any diffs by setting the stored compat
version in the database per-diffset.

This gets some large, more insane diffs from 1-2 minutes down to around
10 seconds.

Unit tests pass.

Tested with some large diffs that went down the optimized code path. Didn't
see any problems.