GeezerVison is showing github.com — difflib.GestaltSequenceMatcher implementation · Issue #144132 · python/cpython
difflib.GestaltSequenceMatcher implementation #144132DescriptionFeature or enhancement
Proposal:
Increase quality of results by being able to run Longest Common Subsequence with autojunk=False with little to no degradation in performance.
Implemented GestaltSequenceMatcher by default gives equivalent results to SequenceMatcher(autojunk=False).
| case |
Myers |
difflib(aj=1) |
difflib(aj=0) |
New(aj=0) |
New+balancing=2/3 |
| [L] diff_key ( 15, 15) |
8 |
5 -3 |
5 -3 |
5 -3 |
8 0 |
| [L] diff_mid1 ( 28, 27) |
11 |
11 0 |
11 0 |
11 0 |
11 0 |
| [L] diff_mid2 ( 128, 128) |
73 |
72 -1 |
72 -1 |
72 -1 |
72 -1 |
| [L] diff_mid3 ( 131, 131) |
63 |
50 -13 |
50 -13 |
50 -13 |
57 -6 |
| [L] difflib.py ( 2041, 2334) |
1883 |
1878 -5 |
1879 -4 |
1879 -4 |
1879 -4 |
| [L] linux_sched.c (11373, 11832) |
10844 |
10793 -51 |
10837 -7 |
10837 -7 |
10844 0 |
| [L] react.js ( 3555, 3337) |
2631 |
2568 -63 |
2581 -50 |
2581 -50 |
2581 -50 |
| [L] three.js (36282, 36793) |
30688 |
25877 -4811 |
30588 -100 |
30588 -100 |
30656 -32 |
| [L] webpack.js ( 2327, 3429) |
929 |
772 -157 |
899 -30 |
899 -30 |
916 -13 |
| ----- |
|
|
|
|
|
| Total: |
47130 |
42026 -5104 |
46922 -208 |
46922 -208 |
47024 -106 |
| Avg % diff: |
0% |
10.58% |
7.25% |
7.25% |
1.61% |
| Total % diff: |
0% |
10.83% |
0.44% |
0.44% |
0.22% |
| Runtime (s): |
32.451 |
0.694 |
41.517 |
0.292 |
0.362 |
Table above shows the number of individual match points.
Which is not a definitive metric.
More definitive metric could be a number of alignment points sacrificed for the sake of quality.
However, it can be safely assumed that autojunk=False / new matcher produces higher quality diffs by not resorting to approximations. Luckily, it also increases number of match points.
New optional balancing argument can be turned on to reduce the chance of greedily committing to unbalanced matches. It produces more concise diffs with more lines matched, while retaining block-oriented nature.
For visual inspection, can see outputs of different algorithms for tailored case HERE!
Legacy
O(n) solution is not that complex - 100 of Python lines.
I hacked in initial implementation and ran context_diff on the difflib.py - the change itself.
import difflib, time
with open('/Users/Edu/lib/src/cx_amb/src/cx/cli/snd/diff/difflib.py') as f:
s1 = f.read().splitlines(keepends=True)
with open('/Users/Edu/lib/src/cx_amb/src/cx/cli/snd/diff/difflib_new.py') as f:
s2 = f.read().splitlines(keepends=True)
list(difflib.context_diff(s1, s2, fromfile='before.py', tofile='after.py'))
# 2.4 ms (Current)
# 2.9 ms (New)So 30% faster.
So 20% slower.
Also, this is a fairly rough plug-in - there is a chance that the gap can be bridged.
O(n) solution should avoid some of the user dissatisfaction:
Has this already been discussed elsewhere?
No response given
Links to previous discussion of this feature:
Made a couple of posts in unrelated thread.
Performance tables are there showing that this is faster even for sizes of 10.
https://discuss.python.org/t/include-time-and-space-complexity-in-documentation/105683/32
Linked PRs
ActivityZeroIntensity commented on Jan 22, 2026 A single iteration isn't really reliable enough for benchmarking. Could you provide benchmarks using at least several thousand iterations? tim-one commented on Jan 22, 2026 Give it some time? @dg-pb is very conscientious about timing things, but this is still at the "first prototype" stage. Timing stuff is about the worst use of his time for now 😉. tim-one commented on Jan 22, 2026 dg-pb commented on Jan 22, 2026 ContributorAuthor More actions
A single iteration isn't really reliable enough for benchmarking.
That was sloppy of me.
Unfortunately, the situation is not as straight forward as I initially hoped.
There is a slight performance degradation. dg-pb commented on Jan 23, 2026 ContributorAuthor More actions It is in a working state now. It selects the algorithm to use dynamically:
asize = ahi - alo
bsize = bhi - blo
automaton_cost = bsize * 6 + asize * 2
simple_cost = self._max_bcount * asize
use_automaton = simple_cost > automaton_cost Initially I set constants 5 and 2 by analysing what automaton does.
Then I did a bit of calibration - https://gist.github.com/dg-pb/ace3f01ba3e0560fd19df13ab3f6f662.
Which showed that I was quite on point with my initial guess.
Result seems to be in the right direction.
@tim-one's fibonacci example:
>>> f = fib()
... xs = [next(f)]
... while len(xs[-1]) < 1_000_000:
... xs.append(next(f))
... from time import perf_counter as now
... from difflib import SequenceMatcher
... k = SequenceMatcher(None, b=xs[-1], autojunk=False)
... for sub in xs:
... start = now()
... k.set_seq1(sub)
... print(k.find_longest_match(), now() - start)
...
DICT
Match(a=0, b=0, size=1) 0.2884995772037655
DICT
Match(a=0, b=1, size=1) 0.1572995709720999
DICT
Match(a=0, b=0, size=2) 0.2727880459278822
DICT
Match(a=0, b=2, size=3) 0.4081151830032468
DICT
Match(a=0, b=0, size=5) 0.675555185880512
DICT
Match(a=0, b=5, size=8) 1.0902111490722746
AUT
Match(a=0, b=0, size=13) 3.309705176856369
AUT
Match(a=0, b=13, size=21) 3.8286903873085976e-05
AUT
Match(a=0, b=0, size=34) 2.3780157789587975e-05
AUT
Match(a=0, b=34, size=55) 2.9445858672261238e-05
AUT Initially it refrains from using Automaton, however as a size increases it reaches the point when it says "Automaton time".
Then it constructs Automaton once and runs the rest blazingly fast.
(As blo/bhi don't change, Automaton is cached and doesn't need to be reconstructed, while construction is the major cost.)
Compared to the gist, automaton is now a bit simpler (and faster).
Instead of storing indices that point to nodes in a list, nodes now hold direct references. And only root node pointer is saved.
This change will not have any noticeable impact for default parameters (i.e. autojunk=True). However, once this is merged, new parameter can be added (e.g. exact=False) to functions that make use of this, so that users can choose to calculate exact result without "autojunk" heuristic and get results with appropriate performance.
Also, with autojunk=False, SequenceMatcher can now be used reliably to calculate exact Shortest Common Substring, which can run 2 sequences of 1M length in seconds. changed the title [-]Implement Suffix Automaton for difflib's Longest Common Substring[/-] [+]difflib.GestaltSequenceMatcher implementation[/+] on Feb 7, 2026dg-pb commented on Feb 21, 2026 ContributorAuthor More actions Closing this for now. This is quite a lot, to move forward need to go smaller increments.
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|