GeezerVison is showing github.com — Difflib creates unreasonably large diffs · Issue #118150 · python/cpython
Difflib creates unreasonably large diffs #118150DescriptionBug report
Bug description:
#!/usr/bin/python3
import difflib
def get_lines(filename):
with open(filename, 'r', encoding='utf8') as fd:
return fd.readlines()
old_new = list(difflib.unified_diff(
get_lines('external.old'),
get_lines('external.new'),
))
new_old = list(difflib.unified_diff(
get_lines('external.new'),
get_lines('external.old'),
))
print('diff -u external.old external.new.json | wc -l')
print(len(old_new))
print('diff -u external.new external.old.json | wc -l')
print(len(new_old))$ ./difftest.py
diff -u external.old.json external.new.json | wc -l
30854
diff -u external.new.json external.old.json | wc -l
26 $ diff -u external.old.json external.new.json | wc -l
26 $ diff -u external.new.json external.old.json | wc -l
26
Running on RHEL9 with Python 3.9.18.
I have a JSON file that I'm diffing and I tend to get very large diffs when lines are removed from the file. When lines are added the produced diffs are simple. The JSON file is a list of DNS records.
external.old.json
external.new.json
Here are smaller files that reproduce the effect. In trying to create the smaller files I noticed that if I go too small then the diffs work fine. If you remove the "abcluster.eas.gatech.edu" from both files the diffs work. I could not get the file smaller.
small.external.old.json
small.external.new.json
CPython versions tested on:
3.9
Operating systems tested on:
Linux
Linked PRs
Activityterryjreedy commented on Apr 22, 2024 Can you illustrate the issue with much smaller strings, perhaps 20 or fewer lines included in the code, the instead of the 340Kb files attached? Sxderp commented on Apr 22, 2024 I updated the first post with smaller JSON. Unfortunately I couldn't reproduce the issue when I tried to make even smaller files. A size issue? blhsing commented on Apr 23, 2024 This is because of the autojunk option that is True by default. With this option enabled SequenceMatcher would automatically consider "popular" elements (those that account for 1 + 1% of the total elements) as junk when the size of the second sequence is 200 or more. The intention is to speed up the diff by ignoring elements that repeat too much--at the cost of accuracy.
You code would work as intended if you patch SequenceMatcher with autojunk=False:
import difflib
from unittest.mock import patch
from functools import partialmethod
with patch('difflib.SequenceMatcher.__init__', partialmethod(difflib.SequenceMatcher.__init__, autojunk=False)):
old_new = list(difflib.unified_diff(
get_lines('small.external.old.json'),
get_lines('small.external.new.json')
))IMHO the autojunk option should be made available to all of difflib's utility functions including unified_diff, diff_bytes, ndiff, etc., or be made into a global setting in the difflib module, so one does not need to resort to patching SequenceMatcher to disable autojunk. Sxderp commented on Apr 23, 2024
IMHO the autojunk option should be made available to all of difflib's utility functions including unified_diff, diff_bytes, ndiff, etc., or be made into a global setting in the difflib module, so one does not need to resort to patching SequenceMatcher to disable autojunk.
This sounds like a reasonable ask. I concur. terryjreedy commented on Apr 23, 2024 Did either of you verify that autojunk=False actually solves the issue for the posted data?
@tim-one Proposal in #118150 (comment): make SequenceMatcher autojunk option available to utility functions that use SequenceMatcher. Or make option a module global. Reasonable? Which better? Better alternative? Sxderp commented on Apr 23, 2024
- It does solve the issue (and I'm using it for the time being)
1.a It is a fair bit slower.
1.b I find it strange that the autojunk errors are only triggering when lines are removed but it behaves when lines are added.
- I'm not sure about a global option. It is slower so I feel it could be situational. If someone knows their data isn't going to trigger the weird output they can use the speedup.
- I don't know much about how "junk" is determined and I know algorithms are hard but the ideal situation would be to speed up difflib without producing large diffs. I know Python is going to be slower then C, but when writing new files, using subprocess diff, and deleting the files is so much faster, I'm almost tempted to do that.
With my not-very-scientific tests
~ 5.46 autojunk = False (Unsure how much may be overhead from patch itself).
~ 0.02 default
~ 0.01 writing new files, diffing, deleting them
I don't expect to get anywhere close to diff speed and for my use-case 5 seconds doesn't matter (cron job). terryjreedy commented on Apr 23, 2024 For experiments, you should, depending on exact install type and location, be able to (temporarily) modify difflib.py itself. Sxderp commented on Apr 24, 2024 I copied the difflib.py from the system directory into my local directory and patched it. I'm still getting ~5s with autojunk = False. So patch was not providing a noticeable impact.
The speed, at least for my use case, isn't too big of a concern. Being able to specify autojunk=False, by some means, to difflib is the most important short-term goal. Lenormju commented on Jul 20, 2025 The SequenceMatcher expects two parameters : a (set_seq1) and b (set_seq2). It could seem like it is symmetric, but the implementation definitely is not : the b serves as baseline, for which several as can be compared to. With the autojunk on, I agree with the docs (Doc/library/difflib.rst) that it gives an output that human prefer. But this makes for a very surprising result : because it is only applied to only one side (B), it causes the diff to not be symmetric.
It could look like a bug if it was not the intended behavior. (is it ?)
At the minimum, I think the docs could make it clearer that it can cause asymmetrical diffs, possibly larger than expected.
As discussed above, the SequenceMatcher's autojunk argument is not supplied by any difflib function, so always at its default parameter value True. This can be a surprise, because the autojunk behavior is only explained in the SequenceMatcher doc (at the top of the module page), so there is no indication of that behavior in the doc of the others difflib's functions.
Moreover, ndiff and HtmlDiff for example already accepts both linejunk and charjunk, the other two SequenceMatcher parameters (also having a default value). So it looks to me that autojunk should be added to the other functions too.
I am working on a PR for these two facets. Lenormju commented on Jul 17, 2026 I ran a search for similar GitHub issues, and found out that the problem had already surfaced:
Citing Tim Peters from 2022 (#90825 (comment)):
We can't change defaults without superb reason - Python has millions of users, and changing the output of code "that works" is almost always a non-starter.
Improvements to the docs are welcome.
Which I agree with, so here is the plan I suggest:
- adding to the documentation an explanation of the non-commutativity, and the relation (knob) with speed and subjective quality/conciseness (cf Tim comment's: A warning should be added to difflib documentation about SequenceMatcher performance #106865 (comment))
- exposing the
autojunk parameter to ALL top-level functions or classes' methods that otherwise would not supply it and thus be True. This requires changing the public interface to the module, but in a non-breaking way (adding a kwarg parameter with a default value, still True).
The second issue (autojunk not being surfaced publicly) also has already been commented here:
Other related tickets:
added a commit that references this issue on Sep 4, 2026gh-118150: difflib: expose autojunk flag from SequenceMatcher to publ… encukou commented on Sep 7, 2026 Reacted by Tomasz Kazimierczak, Sxderp and Lenormand Julien
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|