difflib.py Differ.compare is too slow [for degenerate cases]

Bug report

Bug description:

import difflib

a = ["0123456789\n"] * 1_000
b = ["01234a56789\n"] * 1_000
list(difflib.Differ().compare(a, b))  # very slow and will probably hit max recursion depth

The case is pathological in the sense of many lines with the same exact diff / ratio.

The issue is that in the current implementation _fancy_replace will take the first pair of lines (with the same ratio) as a split point and will call itself recursively for all lines starting at 2, then 3, 4, etc. This repeats 1_000 times resulting in a massive recursion depth and O(N^3) complexity scaling.

For an average random case it should split anywhere in the range of 1_000 with a complexity scaling of O(N^2 log N).

I personally encountered this in diffing csv files where one of the files has a column added which, apparently, results in all-same ratios for every line in the file.

Proposal

Fixing this is not so hard by adding some heuristics (WIP) pulkin@31e1ed0

The idea is very straightforward: while doing the _fancy_replace magic, if you see many diffs with the same exact ratio, pick the one closest to the middle of chunks rather than the first one (which can be the worst possible choice). This is done by promoting the ratios of those pairs of lines that are closer to the middle of the chunks.

The _drag_to_center function turns line number into the weight added to the ratio (twice: for a and for b). The weight is zero for both ends of chunks and maximal in the middle (quadratic poly was chosen for simplicity). The magnitude of the weight "_gravity" is small enough to only affect ratios that are exactly the same: it relies on the assumption that we probably have less than 500k symbols in the line such that the steps in the ratio are greater than 1e-6. If this assumption fails some diffs may become different (not necessarily worse).

Performance impact for non-pathological cases is probably minimal.

CPython versions tested on:

3.9, 3.12

Operating systems tested on:

Linux

Linked PRs

Changed label from "type-bug" to "performance" and "type-feature". difflib doesn't make any promises about speed, and finding "bad cases" is expected - that's not "bug" territory.

In your proposal. please add some high-level comments about the meaning of "_gravity" and what range of values might be useful. The name on its own is just a mystery.

BTW, I agree this class of inputs is worth addressing 😄. Please open a Pull Request?

Offhand, it seems to me that this would be a faster and much more obvious way to get a value that's 0 at i=0 and i=hi-1, and a maximum of 0.5 at the midpoint:

min(i - lo, hi - 1 - i) / (hi - lo)

Sure that will probably do as well; was just avoiding function calls.

Micro-optimizations like that are increasingly out of style in core Python code. They generally don't help (or even hurt) when running under PyPy, and CPython is making real progress at speeding the common cases too.

Relatedly, nobody ever abuses the default-argument mechanism to add local_name=some_global_name_or_const "arguments" anymore, unless it's absolutely time-critical in a very heavily used library.

Else clarity is valued more.

Let's stay away from hard-coded constants, too - especially ones with "mystery names" 😉. Constants frequently bite us later, and are rarely needed.

In this case, .ratio() is defined to return 2.0*M / T, where M is the number of matches and T is the total number of characters. So code like this, once at the start, is cheap to determine what's actually required:

lena = ahi - alo
lenb = bhi - blo
smallest_ratio_delta = 2 * 0.99 / (lena + lenb)

Defining lena and lenb locals may also simplify later code. Multiplying by 0.99 is to make this a lower bound, to be on the safe side. Again resist micro-optimization: while years ago it helped a little bit to avoid the multiply and type in "1.98" by hand, those days are long over. Even CPython does that arithmetic at compile-time now.

Then if you have two "midrange bonus" functions that max out at 0.5 for i and j being at the midpoints of their ranges,

midrange_total_bonus = (midrange_a_bonus + midrange_b_bonus) * smallest_ratio_delta

will yield a score bonus less than the difference between any two distinct raw scores (the sum of the two bonuses can't be greater than 1.0).

"Strength reduction" looks like a worthwhile optimization. Short course: all function calls, and even multiplies, can be removed from the inner loop, by keeping the bonus as a running total, and adjusting it near the top of the loop like so:

                bonus += a_inc if i <= ihalf else -a_inc

where the other names are function-level invariants:

        ihalf = (alo + ahi - 1) / 2
        a_inc = smallest_ratio_delta / lena

So the bonus keeps going up around the loop, until the midpoint is reached, after which it keeps going down.

Similarly for the outer loop. Some details may be tricky. Better names could be picked 😉.

If you don't want to bother, let me know here, and I'll open a pull request.

Unfortunately, smallest_ratio is not about alo or ahi: it is about the smallest difference across unrelated comparisons (thus, I was also wrong with my 500k symbol estimation). It has to be much smaller; this one is probably a correct (upper bound):

len_a = max(map(len, a))
len_b = max(map(len, b))
smallest_ratio_delta = 2 * 0.99 / (lena + lenb) ** 2

I plan to play around and open PR. My first one here!

Wow - I was hallucinating badly, wasn't I ☹️?

It's all yours - I look forward to the PR 😄

Unless I'm still hallucinating, the square in the new expression isn't needed, is it? If the longest elements ever compared have lengths len_a and len_b, the smallest non-zero .ratio() possible is 2 over their sum.

No problem: I often skip over large chunks and forget to come back and to explain.

Given the ratio 2 * some_integer / (len(ai) + len(bj)),

the differences between two arbitrary ratios are simply

  2 * some_integer / (len(ai1) + len(bj1))
- 2 * other_integer / (len(ai2) + len(bj2)) =

2 * [some_integer * (...) - other_integer * (...)]
/ [(len(ai1) + len(bj1)) * (len(ai2) + len(bj2))] =

2 * still_some_integer
/ [(len(ai1) + len(bj1)) * (len(ai2) + len(bj2))]

Trying to minimize the above by the absolute value (and requiring it to be non-zero) we just discard whatever the details of the numerator except that it is a non-zero integer: thus, we take it still_some_integer = 1. For the denominator we should technically take largest and next-largest len(ai) + len(bj) but we just take it the largest possible sum len(ai) + len(bj) twice to simplify computations and slightly worsen our lower bound.

Example (rather my rough understanding than the actual computation):

a1, b1 = "abc", "a"
a2, b2 = "abcd", "a"
ratio_1 = 2 * 1/4
ratio_2 = 2 * 1/5
ratio_1 - ratio_2 = 2 * 1/20  # our estimation is 2 * 1/25 instead

Thanks! Got it now. The smallest delta between .ratio()s of two sequences of the same lengths may indeed be much larger than the delta between .ratio()s of sequences with different (but no larger) lengths.

Your more careful analysis looks right. Using the square to simplify reasoning is fine. It's not like we're pushing the limits of float precision here 😉.

Here's a different case that's still cubic-time, and blows the recursion stack. The first line pair has a unique best ratio, and the same is true at each recursion level:

import difflib
a = []
b = []
N = 1000
for i in range(N):
    s = "0" * (N - i)
    s2 = s + "x"
    a.append(s + "\n")
    b.append(s2 + "\n")
list(difflib.Differ().compare(a, b))

I don't have a slick idea to get around that while preserving current results (well, for this specific input, sure - I mean "in general").

Half-baked: for each j, remember the smallest i (if any) achieving the highest ratio above the cutoff. By construction, a list of such (i, j) pairs is increasing in the 2nd index. Then pick a longest-possible subsequence (not necessarily contiguous) of those that's strictly increasing in the 1st index too.

Wouldn't always eliminate non-trivial recursive calls. In this test case, and in the original, it would. How it may affect current results is clear as mud to me 😄.

EDIT: why not build the list with strictly increasing i to begin with (as is done now)? Suppose the first line of b is similar to the last line of a. Then the first pair added would be (ahi - 1, blo), and we could never add another (we already maxed out the 1st index position).

Yes I was aware about this one. It is special in a sense of arbitrary long strings: if you limit string length then asymptotically it is still O(N^2). Frankly speaking, for the application I am looking into I will probably try implementing the fast ONP one keeping string comparison intact because O(N^2) is still very slow for 500 Mb text files.

Over my head 😉. I don't know what "ONP" means(*), or "keeping string comparison intact".

In general, I don't know of a worst-case sub-quadratic algorithm for "longest common subsequence" problems. Suffix trees can, in theory, solve "longest contiguous common subsequence" problems in linear time, but are exceedingly delicate with high constant factors.

That said, it's easy to believe difflib isn't suitable for your application. It was aimed at human-friendly output, pretty much regardless of cost. "Shortest edit script" sucks at the "human-friendly" part.

BTW, you can avoid _fancy_replace() entirely by using SequenceMatcher directly. You can get an "edit script" much faster then, but no attempt is made to identify "similar" lines. They're identical or they aren't.

(*) As in "An O(NP) Sequence Comparison Algorithm" by Wu, Manber, & Myers?

you can avoid _fancy_replace() entirely by using SequenceMatcher directly

And seems possible that's what you really wanted all along. If you're thinking of implementing a Myers diff algorithm, then you don't care about intraline markup. That can make a huge difference..

Here's your original test, but with a million lines in each input:

>>> import difflib
>>> a = ["0123456789\n"] * 1_000_000
>>> b = ["01234a56789\n"] * 1_000_000
>>> s = difflib.SequenceMatcher(None, a, b) # appears instantaneous
>>> list(s.get_matching_blocks()) # also very  fast
[Match(a=1000000, b=1000000, size=0)] # see the docs - this always has a size-0 dummy at the end
>>> for x in s.get_opcodes(): # and here's your "edit script"
...     print(x)
('replace', 0, 1000000, 0, 1000000)
>>>

Any kind of "bad case" you make up for _fancy_replace() is most likely to run in linear time under SequenceMatcher.

Under the covers, Differ.compare() does the same thing, but goes on to replace SequenceMatcher's "replace" opcode with its own _fancy_replace output,

One final "speed hint": PyPy generally runs diffllib functions much faster than CPython does. In your original test, using difflib's original code, PyPy finishes in about 5 seconds on my box, without overflowing the stack. I don't know all the reasons for that (in part, function inlining cuts recursion depth).

FYI, in the latest PR, _fancy_replace() is no longer recursive, and the number of ratios it computes is worst-case O(min(bhi - blo, ahi - alo)). It's certainly possible to contrive cases where it delivers different results, but so far none that I care about. But it's still much faster to use SequenceMatcher directly if you don't care about intraline markup.

Yes: thinking about using SequenceMatcher. I did not look into it but it is tempting for sure. In a way that I can abstract out dealing with different dimensions (characters in the line, lines in the file but maybe also files in the folder even).

But the straightforward implementation that you showed is not something very useful in my case: I do care about close but not exact matches. Roughly speaking I would like to simplify it to this:

@dataclass
class CloseIsEqualWrapper:
    token: Any
    
    def __eq__(self, other):
        assert isinstance(other, CloseIsEqualWrapper)
        return difflib.SequenceMatcher(a=self.token, b=other.token).ratio() >= .75

a = list(map(CloseIsEqualWrapper, a))
b = list(map(CloseIsEqualWrapper, a))

print(list(difflib.SequenceMatcher(None, a, b).get_matching_blocks()))

Then, if SequenceMatcher is not fast enough I will be able to isolate the performance problems to the sequence comparison without worrying whether it is line or file comparison.

Alas, I doubt that can be made to work. Dicts are critical to how matching works, and defining __eq__ as "close to" breaks just about every precondition dicts rely on. For example, any two values that compare equal must have the same hash code. Which you can always satisfy by, e.g., defining __hash__ to return some constant - but then all keys collide, and dict lookup becomes an especially slow way of doing linear search.

There's also that "close to" doesn't define an equivalence relation, because it's not transitive. That A is close to B, and B is close to C, doesn't imply that A is close to C.

ABCDE close_to VBCDE close_to VWCDE close_to VWXDE close_to VWXYE close_to VWXYZ

Any two strings of sufficient length can be transformed to the other via such a chain.

And there's also - as the docs note - that .ratio() on its own isn't even symmetric. Order can matter. For example, compare "taste" to "tease". In that order, the ratio is 0.8; swap them & it falls to 0.4. This is a consequence of the documented way in which "longest matching block" is defined, and then the "very high wall" between "before and after" portions of the block kicks in.

I expect you'd do better by not trying to trick SequeneceMatcher. Copy (or subclass) the Differ class and supply your own idea of _fancy_replace.

Of course if you're coding a Meyers-style algorithm from scratch, none of the above matters. Then I'd recommend the classic Levenshtein distance (which is symmetric) as a measure of similarity (or a wrapper around .ratio() can be made so, by, e.g., trying both orders and returning the larger (or smaller) ratio, or doing it just once with the lesser (or greater) input first).

gh-119105: Differ.compare is too slow [for degenerate cases] (#119492)

pythongh-119105: difflib: improve recursion for degenerate cases (pyt…

pythongh-119105: difflib.py Differ.compare is too slow [for degenerat…

pythongh-119105: Differ.compare is too slow [for degenerate cases] (p…

Navigation Menu

Repository navigation

difflib.py Differ.compare is too slow [for degenerate cases] #119105

Bug report

Bug description:

Proposal

CPython versions tested on:

Operating systems tested on:

Linked PRs

26 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

difflib.py Differ.compare is too slow [for degenerate cases] #119105

Description

Bug report

Bug description:

Proposal

CPython versions tested on:

Operating systems tested on:

Linked PRs

Activity

tim-one commented on May 16, 2024

tim-one commented on May 16, 2024

pulkin commented on May 16, 2024

tim-one commented on May 16, 2024

tim-one commented on May 16, 2024

tim-one commented on May 17, 2024

pulkin commented on May 17, 2024

tim-one commented on May 17, 2024

pulkin commented on May 17, 2024

tim-one commented on May 17, 2024

26 remaining items

tim-one commented on May 23, 2024

pulkin commented on May 23, 2024

tim-one commented on May 23, 2024

tim-one commented on May 23, 2024

tim-one commented on May 24, 2024

pulkin commented on May 24, 2024

tim-one commented on May 24, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions