Difflib creates unreasonably large diffs · Issue #118150 · python/cpython · GitHub

Bug 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

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?

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?

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.

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.

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?

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).

For experiments, you should, depending on exact install type and location, be able to (temporarily) modify difflib.py itself.

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.

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.

I ran a search for similar GitHub issues, and found out that the problem had already surfaced:

SequenceMatcher.ratio() noncommutativity not well-documented #81185 (closed): non-commutativity issue raised for the ratio method, but it is unrelated to autojunk behavior, and the documentation for the ratio method received a patch to indicate this (commit 7dafbe8).
SequenceMatcher & autojunk - false negative #90825 (open): autojunk surprising behavior raised, and both suggesting a documentation change, and allowing to pass the autojunk arg explicitely (instead of being implicitely always True).
Better explain "junk" concept in difflib doc #58540 (closed): another person was surprised of the charjunk/linejunk (distinct from autojunk) behavior, and contributed a doc clarification for them (commit c51da2b).
A warning should be added to difflib documentation about SequenceMatcher performance #106865 (open): another example of autojunk surprising behavior, and suggesting at the end to clarify its role regarding performance and subjective quality.
misleading output from difflib unified_diff #84868 (open): the diff was not the one expected because the autojunk arg was not set to False, maybe making it clearer in the docs would have prevented the error?

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:

SequenceMatcher & autojunk - false negative #90825 (comment) (open): fixing the issue currently requires to mock or apply a local patch to the standard library.
gh-106865: Improve difflib.find_longest_match performance with cache #106877 (comment) (closed): Tim agreeing the autojunk argument should not have been True by default, but it is too late to change it
difflib.HtmlDiff produces different output from difflib.ndiff #71896 (open): the different handling of trailing \n between HtmlDiff (strips them) and ndiff() (does not) caused the unexpected autojunk=True to produce large outputs
- maybe the EOL-stripping is another issue? I'm not digging into that now.
bpo-2986: Allow disabling difflib's automatic junk heuristic #17082 (closed): the autojunk issue was already discussed between 2008 and 2010 on BPO (https://bugs.python.org/issue2986), and then a PR landed on GitHub in 2019 (BPO migration?), but got closed because its author did not sign the CLA.

Other related tickets:

difflib.GestaltSequenceMatcher implementation #144132 (closed, not planned): offered to improve the performance (such that autojunk=False would be as fast as autojunk=True), but moved as a smaller increment in Composability of difflib #145209 (open). It has been stale for a few months now. This is a different, competing, way to solve the same issue.
Add a C accelerator for difflib.SequenceMatcher #150184 (closed, not planned): offered to move to C for speedup, but was rejected.
Provide a way for potentially long runtime difflib algorithms to be aborted by the caller (and report progress?) #69092 (open): suggested in 2015 to add a timeout, and changed course in 2022 to be callback-based instead, without any activity since.
difflib.SequenceMatcher not matching long sequences #47235 (closed): added the autojunk parameter in 2010, while fixing some bugs.

pythongh-118150: difflib - fix NEWS issue with ref. not found

pythongh-118150: difflib - fix NEWS doc for ReST

pythongh-118150: difflib - remove template notes from NEWS

pythongh-118150: update NEWS again

pythongh-118150: fix for sphinx linter

pythongh-118150: Merge branch 'main' into pythongh-118150-expose-auto…

pythongh-118150: clean whitespaces for lint

Merge branch 'main' into pythongh-118150-expose-autojunk

pythongh-118150: difflib - update doc

Merge branch 'main' into pythongh-118150-expose-autojunk

pythongh-118150: difflib - update doc

pythongh-118150: warn in doc about results asymmetry for difflib junk (…

pythongh-118150: difflib - update doc

gh-118150: difflib: expose autojunk flag from SequenceMatcher to publ…

Thank you @Sxderp for the research, and @Lenormju & @faithlesstomas for the fixes!

pythongh-118150: difflib: expose autojunk flag from SequenceMatcher t…

force unified_diff to accept autojunk=False

Difflib creates unreasonably large diffs · Issue #118150 · python/cpython · GitHub

Repository navigation

Difflib creates unreasonably large diffs #118150

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Linked PRs

13 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Difflib creates unreasonably large diffs · Issue #118150 · python/cpython · GitHub

Repository navigation

Difflib creates unreasonably large diffs #118150

Description

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Linked PRs

Activity

terryjreedy commented on Apr 22, 2024

Sxderp commented on Apr 22, 2024

blhsing commented on Apr 23, 2024

Sxderp commented on Apr 23, 2024

terryjreedy commented on Apr 23, 2024

Sxderp commented on Apr 23, 2024

terryjreedy commented on Apr 23, 2024

Sxderp commented on Apr 24, 2024

Lenormju commented on Jul 20, 2025

Lenormju commented on Jul 17, 2026

13 remaining items

encukou commented on Sep 7, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions