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

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

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.

Description From Last Updated

Just to improve forward-compatibility for the next time we change this code, can you do this instead? if compat_version in …

daviddavid

Instead of using xrange here, you should add this to the top of the file: from djblets.util.compat.six.moves import range

daviddavid

Actually, how about we define symbolic COMPAT_VERSION_*s in differ.py next to the DEFAULT one, and then import it here?

daviddavid
chipx86
david
  1. 
      
  2. reviewboard/diffviewer/differ.py (Diff revision 1)
     
     

    Just to improve forward-compatibility for the next time we change this code, can you do this instead?

    if compat_version in (1, 2):
    
  3. You've also got a tyop in your description: "rever"

chipx86
david
  1. 
      
  2. reviewboard/diffviewer/myersdiff.py (Diff revisions 1 - 2)
     
     

    Instead of using xrange here, you should add this to the top of the file:

    from djblets.util.compat.six.moves import range
    
    1. The interdiff is being tricky. I moved this back to release-1.7.x, and that line was close enough to get caught up in the valid interdiff ranges. I actually didn't touch that line in either change (and six wouldn't be appropriate for 1.7.x).

  3. 
      
david
  1. 
      
  2. reviewboard/diffviewer/myersdiff.py (Diff revision 2)
     
     

    Actually, how about we define symbolic COMPAT_VERSION_*s in differ.py next to the DEFAULT one, and then import it here?

  3. 
      
chipx86
david
  1. Ship It!
  2. 
      
chipx86
Review request changed

Status: Closed (submitted)

Loading...