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

[pulkin]

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

• gh-119105: difflib: improve recursion for degenerate cases #119131
• gh-119105: difflib.py Differ.compare is too slow [for degenerate cases] #119376
• gh-119105: Differ.compare is too slow [for degenerate cases] #119492

[tim-one]

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.

[tim-one]

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)

[pulkin]

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

[tim-one]

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.

[tim-one]

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

[tim-one]

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

[pulkin]

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!

[tim-one]

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.

[pulkin]

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