- Change Summary:
-
Targeting 1.7.x for this.
- Branch:
-
masterrelease-1.7.x
Re-enable an important optimization in the Myers diff algorithm.
Review Request #5228 — Created Jan. 9, 2014 and submitted
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 … |
 david
|
|
|
Instead of using xrange here, you should add this to the top of the file: from djblets.util.compat.six.moves import range |
david
|
|
|
Actually, how about we define symbolic COMPAT_VERSION_*s in differ.py next to the DEFAULT one, and then import it here? |
david
|
- Change Summary:
-
- Changed the capability version check to be more specific.
- Fixde a tyop.
- Description:
-
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 ~ rever it, and test manually with any diffs by setting the stored compat ~ 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.