• 
      

    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.