Algorithmic complexity of difflib

[tim.one (Tim Peters)]

@dg-pb

I consider seq1 as base and seq2 as version, thus getting earlier match in seq2 is somewhat desirable. Meaning checking h of seq1 in table of seq2 first.

I don’t know that makes any real difference. I just like to define the result of ambiguous cases ,.

In the absence of cyclic extensions, I can see one “reason” to favor matching “earliest in version” when the lengths are equal: base is usually shorter than version (many kinds of files grow much more often than they shrink), so you want to advance to the end of base as early as possible. Incrementing its current index by the match length is “better” for that purpose than incrementing some earlier index in base.

But that’s too glib to convince even me .

[dg-pb]

@tim.one

implications of “k-cyclic” extensions

Did some quick testing:

CODE: `delta_burns_rec

def delta_burns_rec(seq1, seq2, nrec=2, **kwds):
    assert nrec > 0
    all_matches = []
    while 1:
        matches = delta_burns(seq1, seq2, **kwds)
        all_matches.append(matches)
        nrec -= 1
        if nrec:
            if not isinstance(seq1, list):
                seq1 = list(seq1)
            seq2 = list(seq2)
            for i, j, k in matches:
                seq2[j:j+k] = [_VOID] * k
        else:
            break
    it = iter(all_matches)
    matches0 = next(it)
    for matches in it:
        matches0.extend(matches)
    if len(all_matches) != 1:
        matches0.sort(key=lambda x: x[1])
    return matches0

	Delta Size (B)	Time (µs)	Peak (kB)
Reichenberger	1200	92,392	280
Git	1700	15,603	130
Single	2700	5,601	130
Burns	3045	5,181	85
Burns Cyclic	3045	5,181	85
Burns Rec2	2700	16,248	170
SAM	1200	6,060 / 13,229	1412 / 546

Minor quality improvement.
Doesn’t seem to be worth it.

---

Much better would be to find new ways to further reduce SAM’s memory.
E.g. with 32bit ints. SAM’s memory becomes 376 kB.

[tim.one (Tim Peters)]

Another possibility for the non-cyclic linear-time version: if matches are found of sufficient length in both sequences, record them both. Set the new i to the max new i either of them suggest, and likewise for j.

Fraught with dangers, which I’ll gloss over, but in the example it would record both the b and the c blocks correctly on the same outer-loop iteration.

@dg-pb

Much better would be to find new ways to further reduce SAM’s memory.
E.g. with 32bit ints. SAM’s memory becomes 376 kB.

The killer attraction of the linear-time version is bounded memory use regardless of sequence length (the hash tables are the only large data structures, and they can never grow to hold more entries than the Rabin-Karp modulus),

But giant files are niche cases I don’t expect CPyhon will ever cater to out of the box. So, yes, cutting SAM’s RAM use is the only thing of real value here But your test cases apparently barely crack a megabyte even using boxed CPython ints - and using flat lists of ints was a great improvement over the earlier schemes that built per-node collections of ints. Exploiting that most nodes only have one transition gave another great improvement (most nodes don’t need the memory burden of “a dict” at all).

I doubt there are other similarly straightforward big wins to be had, and at some point you have to say “good enough!” and leave it be, lest the code become incomprehensible. If it’s that important, recode it in C, where using native machine ints is dead easy and obvious. Or maybe in Rust? That would be a hoot for sure .

[dg-pb]

@tim.one

if matches are found of sufficient length in both sequences, record them both. Set the new i to the max new i either of them suggest, and likewise for j.

Nice one! again.

1. If same match found, pick whichever
2. if non-overlapping, take both
3. if overlapping, pick longest one and trim the other. If trimmed match >= nprfx, take the trimmed as well

For case at hand +1 match for both cyclic and not:

>>> seq1 = "aaaabbbbccccdddd"
>>> seq2 = "ddddccccbbbbaaaa"
>>> delta_burns(seq1, seq2, cyclic=False)
[(8, 4, 4), (4, 8, 4)]
>>> delta_burns(seq1, seq2, cyclic=True)
[(8, 4, 4), (4, 8, 4), (0, 12, 4)]

Not a common thing in real applications, but nice to have.

[tim.one (Tim Peters)]

Ya - that’s the idea. If’s a lot of fiddly checking, though, and I don’t want to bother with it.

As an aside, my favorite bot has a repeated track record of failing to find very simple counter-examples to its optimistic speculations (although I ask it to speculate, as that sometimes leads in interesting directions). In this case it thought there may “be reasons” for why partial overlaps couldn’t occur.

I found it annoying to think about , but found a very simple one quickly enough. With prefix length 2,

S: bab
T: aba

When i=j=0, ba is added to S’s table and ab to T’s. When they advance to 1, ab is added to S’s table and ba to T’s. S’s new prefix ab is found in T at index 0, and T’s new prefix ba in S’s at index 0. So the matches are (0, 1, 2) and (1, 0, 2). Partial overlap already!

I swear the bot laughed

[tim.one (Tim Peters)]

Another twist for the linear-time approach.

Hash functions aren’t perfect, and collisions will happen. The paper realized that, but didn’t offer a coherent solution, and I think gave up too soon on an obvious, practical approach: map a hash to a list of indices at which that hash appears.

And it’s worse than the paper seems to acknowledge. It’s not just false positives that can hurt. Even with perfect hashing, only the first instance of a given prefix will be recorded in a table. You match starting there, or not at all.

Which is sold as “a feature”, but is really more a consequence of ensuring worst-case O(1) memory consumption.

But it’s still O(1) if collision lists are capped at a fixed max length, or even recorded in a fixed capacity deque, discarding the oldest entry as needed (deque’s maxsize=). With a Rabin-Karp modulus near a million, restricting to just one entry is a minor memory burden.

When matching, the first entry in a list that gives a “good enough” match can be taken, or probably better the longest match found across all entries. So long as the lists have a max length, still linear time. Gonzo complications could include fancy schemes to find the best overall match length across all non-overlapping possibilities across both sequences.

Anyway, the bare idea is easy to code and can help. I haven’t pursued it seriously, though, and probably won’t. In my fiddling with applying this to files of Python code (viewed as sequences of lines), with prefix len 4, the largest (unrestricted-length) list seen had 6 entries (so 5 collisions).

None of these were due to false positives. All were due to repetitions of the same prefix within a sequence.

CORRECTION: there were two false positives total.in a different run. Because hash() is used to feed Rabin-Karp “an int” to work with when sequence elements are strings, it’s not consistent across runs (“hash randomization” for strings).

[dg-pb]

@tim.one

map a hash to a list of indices at which that hash appears.

This is what original Reichenberg’s does, just without cap.

And as far as I have gathered, what git uses is original Reichenberg with lists capped at 64. Prioritising early matches.
Which makes it linear as well.

---

I have the same parameter for Burns & Long.
I suppose it should help a bit - haven’t tested.

@tim.one

discarding the oldest entry as needed

Oldest or newest?

[tim.one (Tim Peters)]

@dg-pb

@tim.one

map a hash to a list of indices at which that hash appears.

This is what original Reichenberg’s does, just without cap.

In part, yes. Gemini tells me git’s binary diff is based on XDelta, and for files of byte sizes M and N:

• Time complexity O(M + N)
• Space complexity O(M)

And as far as I have gathered, what git uses is original Reichenberg with lists capped at 64. Prioritising early matches.
Which makes it linear as well.

As before, it’s not linear-time that’s the killer advantage of Burns & Long, but bounded memory use regardless of input sizes. There are a lot of algorithms now that produce copy/insert binary delta “patches”, but they may or may not have much else in common with Reichenberg’s early effort.

I suppose it should help a bit - haven’t tested.

Neither have I. But we’re not in the delta business, while tools like git are. I take it on faith that they’ve had many more eyeballs looking at the problem space, over much more time, and with far more testing data, than we’ll ever have.

But, surprise: I didn’t know what the “git” line referred to when it showed up in one of your recent tables. But it was one of the slowest, despite that it was competing with Python code.

Mysteries abound

discarding the oldest entry as needed

Oldest or newest?

In context, oldest. I was talking about a deque then. One of the tradeoffs. A minor advantage of deques is that you can pass a max size to the constructor and then forget about it. For example, my Rabin-Karp class never explicitly pops anything. The outgoing int is retrieved via d[0], and is discarded by magic when the incoming int is appended.

[tim.one (Tim Peters)]

@tim.one

None of these were due to false positives. All were due to repetitions of the same prefix within a sequence.

And there’s “a reason” for that. The two biggest files were collections of Python code I’ve collected over the years, one for Python2 and another for Python3. It’s often the case that a snippet is refined over time, with older versions not removed but preserved in if 0: blocks (which the compiler throws away).

Quirky but useful So the same lines of code can appear over and over in the same file. There’s very little duplication between the two files, but repeated partial blocks are common within a file.

So it never actually helped to check against all prefixes sharing the same hash (and, indeed, the same prefix). They overwhelmingly never matched cross-file at all.

There were a few cross-file duplicates, like

    def gcd(a, b):
        while b:
            a, b = b, a%b
        return a

Tiny stuff like that. But I was surprised to find a substantial block of 73 duplicated lines. I have no memory of writing that code even once - or of what it’s trying to accomplish .

[dg-pb]

@tim.one

it’s not linear-time

I think it is, just higher constants.

1. Compute hashes of seq1. Store lists up to 64 length for same hash value
2. Iterate through seq2 and when match, pick the best one from list found in hashtable of seq1

So (1) is clearly a single pass.

For 2. We have O(length2 + 64 length1).

So not in the same sense as Burns and Long, but theoretically linear time.

@tim.one

I didn’t know what the “git” line referred to

It referred to Reichenberg with hashlists of length 64. Exactly the above.

I probed AI, it found me constants in source.
Not sure how accurate this is, but this was a best rough estimate to what they do. This isn’t actually running git’s code, same pure Python code.

@tim.one

A minor advantage of deques

In spirit of Long & Burn, which doesn’t override if it already exists, I instead did:

if len(entry) < hash_max:
    entry.append(i)

It kind of makes sense from POV that earlier matches have higher probability of catching longer runs as they start earlier. But keeping recent ones might result in more of them.

Again, would need to test it. But for now I will follow Long and Burns (and git) - as you said, they should have reasons.

[tim.one (Tim Peters)]

@dg-pb

@tim.one

it’s not linear-time

I think it is, just higher constan

Miscommunication - I wasn’t disputing that. More context:

As before, it’s not linear-time that’s the killer advantage of Burns & Long, but bounded memory use regardless of input sizes

It wasn’t saying anything wasn’t linear-time, just that linear-time isn’t the strongest selling point for Burns & Long - O(1) memory use is.

As to memory use, the scheme you have in mind can be considered as O(1) space too, although it may be a stretch.

I appreciate the clarification that the “git” line was actually referring to an informed guess about git’s approach to large binary files, but coded in Python. That explains a whole lot about the results

And I have no real guess about whether tossing older or newer hash collisions would give better results overall. I’m personally sticking to lists (toss newer ones), just because they’re lighter-weight data structures in Python, and overheads add up when there’s one for each hash code seen.

[tim.one (Tim Peters)]

An observation:

Full-blown Reichenberg takes a sequence, and for every contiguous subsequence of length nprfx maps its hash code to a list of all the starting indices that have the same prefix hash code.

What if nprfx is 1? Then the “rolling hash” machinery is pointless, and it’s just mapping a sequence element’s hash code on its own to a list of all indices who elements’ hash codes are the same. And if the elements are themselves hashable by Python, it can be made exact (no false positives) just by using the element itself as the dict key. Python’s dict machinery then ensures that unequal elements with the same internal hash code resolve to different internal dict entries.

Which, if you squint just a little, is exactly what difflib is currently doing with its b2j dict: mapping an element to a list of all indices at which it appears.

They’re still not the same, but they rhyme

It’s interesting how pragmatics can drive decisions. Reichenberg just wouldn’t be used with such small nprfx. It’s aimed at byte-level differencing, and a “copy 1 byte” output would consume more space than just including the byte verbatim in a block “insert these bytes” output. “Minimum match length” makes sense for them.

With larger alphabets, difflib very much wants not to preclude matching on a single element - indeed, at the limit, “element appears uniquely” is a high-value synch point for human eyes, and “appears rarely” is the heart of git’s “patience” and “histogram” higher-level text difference partitioning.

difflib pretty much sucks at byte-level differencing, for “can become very slow” reasons (often “fixed” by autojunk, but at high cost in diff quality). It’s mondo cool that SAM has no “very slow” cases regardless of alphabet size.

[dg-pb]

@tim.one

It’s mondo cool that SAM has no “very slow” cases regardless of alphabet size.

SAM is a structure that keeps on giving.

It can do multi-pattern string search in at least 3 different ways. Two forward (compile patterns) and one reverse (compile text and search anything in it).

Taking minimum between these ends up in line (or in extreme cases much better) than Aho Corasick with similar optimisation level.

Furthermore, without additional structures it can be optimised along the lines of DAWG-MATCH.
Aho needs additional mini DAWG structure, while SAM can take the role of both components. This gets complex and isn’t worth to do for pure Python implementation, but just a peek into possibilities.

---

To get back to difflib work.
I think extensibility PR is valuable on its own.
However, I am thinking whether new class is needed for Automaton-based Gestalt.

Another possibility would be to use Automaton for autojunk=False - no one uses it with this parameter turned off now anyway (or isn’t this true?).
It would be cleaner in a sense that there is 1 class that does Gestalt.
Creating a new one that gives exactly same results as current matcher with autojunk=False does feel a bit… excessive (for single methodology).

This would also solve the issue where people try to turn autojunk off.

[dg-pb]

Update.

Table below for various diff cases represents scores based on scoring function

f(blocks) = \sum_i^n \text{len}(block_i)^{1.3}

Thus, it is not a sheer individual matched line count (for which naturally exact LCS algorithm delivers optimal result), but a metric biased towards retaining large blocks, which is the main idea behind readable diffs by using difflib’s Gestalt pattern matching approach.

Results would look much better for greedy Gestalt methodology with higher powers in the formula above – without quality improvements Gestalt’s optimization function can be thought of as f(blocks) = \sum_i^n \text{len}(block_i)^{p\rightarrow\infty}. While p=1.3 is adequately conservative and captures the real quality benefit by keeping the balance between amount of data matched and large block bias. It can be interpreted according to this equality: c^p == (0.9c)^p + (0.2c)^p - i.e. block of size c has the same value as 2 blocks: one of size 0.9c and another of size 0.2c.

Table explanation:

1. case column: name (length_of_seq1, length_of_seq2)
2. algorithm column: values are scores according to f(blocks) = \sum_i^n \text{len}(block_i)^{1.3}. Number on the right of it is difference of this score compared to the one Base.
3. avg % diff = \frac{\sum \frac{f(alg_i) - f(Base_i)}{f(Base_i)}}{\text{number of cases}}
4. total % diff is percentage difference of aggregate summed scores compared to Base

6 Algorithms:

1. base - standard exact LCS (implementation - bit vector)
2. Patient Myer - runs patience/histogram and defaults to (1) when runs out of options
3. difflib(aj=1) - SequenceMatcher(autojunk=True)
4. difflib(aj=0) - SequenceMatcher(autojunk=True)
5. Gestalt2 - O(n) time / O(n) space optimization of difflib(aj=0). As it can be seen, its results are identical are identical to difflib(aj=0).
6. Gestalt2B - (5), but with balancing=True, which is an integrated and improved “Skew Fix” feature from earlier discussion which aims to amend issues of greedy commitment. So far it seems that it manages to retain complexity while delivers bigger quality improvement compared to initial version.

case	Base	Patient Myer	difflib(aj=1)	difflib(aj=0)	Gestalt2	Gestalt2B
[L] diff_key ( 30, 30)	32	32 0	28 -4	28 -4	28 -4	28 -4
[L] diff_mid1 ( 56, 54)	34	34 0	34 0	34 0	34 0	34 0
[L] diff_mid2 ( 256, 256)	297	301 4	240 -57	298 1	298 1	298 1
[L] diff_mid3 ( 262, 262)	224	226 2	105 -119	132 -92	132 -92	226 2
[L] difflib.py ( 4082, 4650)	16865	16865 0	16874 9	16876 11	16876 11	16880 15
[L] linux_sched.c (22746, 23664)	92266	92266 0	92349 83	92486 220	92486 220	92494 228
[L] react.js ( 7110, 6674)	16602	16602 0	16510 -92	16541 -61	16541 -61	16542 -60
[L] three.js (72564, 73586)	288327	288354 27	147526 -140801	288779 452	288779 452	288883 556
[L] webpack.js ( 4654, 6858)	3020	3020 0	2679 -341	2996 -24	2996 -24	3012 -8
[L] difflib PR ( 4206, 4582)	13352	13352 0	13347 -5	13623 271	13623 271	13625 273
Total:	431019	431052 33	289692 -141327	431793 774	431793 774	432022 1003
Avg % diff:	0%	0.22%	-14.54%	-5.19%	-5.19%	-0.93%
Total % diff:	0%	0.01%	-32.79%	0.18%	0.18%	0.23%
Runtime (s):	2.582	2.489	1.719	138.369	0.761	0.903

---

Performance

Here are aggregate timings for datasets above scaled by a factor of 4 (difflib(aj=0) is removed as it is uncertain when it would complete):

Algorithm	Runtime (s)
Base (Bit Vector LCS)	27.757
Patient Myer	37.997
difflib(aj=1)	27.527
Gestalt2	3.383
Gestalt2B	3.989

---

Quality improvement of Gestalt2B.

It is rather simple idea, which surprisingly manages to improve results in some properly tricky cases.

The core issue that it solves is likely best represented by this:

seq1 = 'aaaa+bbbb+cccc+dddd+eeee+ffff'
seq2 = 'bbbb-cccc-dddd-eeee-ffff-aaaa'
print(gestalt2(seq1, seq2, balancing=0, aligns=False))
# [(0, 25, 4)]
print(gestalt2(seq1, seq2, balancing=1, aligns=False))
# [(5, 0, 4), (10, 5, 4), (15, 10, 4), (20, 15, 4), (25, 20, 4)]

It also covers (to a reasonable degree) cases where the problem at hand is pure LCS:

seq1 = '_a___a_bcd_____a_ef_g__'
seq2 = 'cb+e+d+++af+g++'
print(gestalt2(seq1, seq2, balancing=0, aligns=False))
# [(1, 9, 1), (18, 10, 1), (20, 12, 1)]
print(gestalt2(seq1, seq2, balancing=1, aligns=False))
# [(7, 1, 1), (9, 5, 1), (15, 9, 1), (18, 10, 1), (20, 12, 1)]

---

To sum up

I have been working on more complex methods to achieve quality. However, I am content with what I have arrived here – it is unlikely that quality improvements of more complex methods would justify needed complexity and inevitable difference in performance – the above delivers reasonable and reliable quality with incredible performance. No fallbacks, no hybrid strategies, just original gestalt pattern matching with a bit of situational awareness. Implementation is manageable – (not counting SuffixAutomaton and some general utilities) it is roughly 300LOC (of which ~30% is “skew_fix” quality improvement).

I am pleased with the results.

Thank you to everyone who participated and followed - this was one of the most enjoyable discussions over my time here.

[pf_moore (Paul Moore)]

@dg-pb

Thank you to everyone who participated and followed - this was one of the most enjoyable discussions over my time here.

Cool. For those of us who have been following with interest, but haven’t understood all the technical details, do you intend to publish the resulting code as a library on PyPI and/or submit it as a PR to the stdlib?

No pressure - I don’t have an immediate need for this, I’m just curious

[dg-pb]

@pf_moore

do you intend to publish the resulting code as a library on PyPI and/or submit it as a PR to the stdlib?

Intent was always to improve difflib. There is a standing PR which adds composability so that new matchers can be used with all utilities there. So that is the 1st step. After that is done, I had 2 trajectories:

1. PR1 for improved utilities and a bit of preparation, then PR2 with SAM based matcher above.
2. Improving existing SequenceMatcher so that the issues with default matcher are reduced to a minimum. See Improvement on current `difflib.SequenceMatcher` algorithm

Will see how this goes. From my experience things are moving rather slowly when it comes to algorithms.

[dg-pb]

TLDR: Quality adjustment is doing its job quite well.

---

Ran comparisons against exact algorithm O(n^3) that optimizes exact f(p)=\sum \text{len}(\text{block}_i)^p with different powers.

Used 2 different metrics to determine closest matching power in terms of achieved results:

1. Order-oblivious distribution comparison
2. actual sum(size^p for size in blocks)

I looked at averages across 14 datasets.
And both metrics agree on a flat optimum spanning roughly p≈1.3–1.75.
This is where exact_optimizer(p) results match gestalt2’s results best.

Exact peaks at:

closest matching powers	distribution ratio	sum(len^p)
balancing=False	p=6.0	p=100.0 (max in the test)
balancing=True	p=1.4	p=1.75

It is reassuring that despite balancing being a correction mechanism that largely stays dormant, its actions have an intended effect. It uses power=1.3 to make decisions and the fact that it has such global effect means that it chooses good time to act.

Of course, given the nature of methodology it will inevitably have variance in its effect and even the odd extreme fail case, but all in all I think this suggests strong possibility of this being worthwhile.