difflib.GestaltSequenceMatcher implementation

[dg-pb]

Feature 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

• gh-144132: Implement Suffix Automaton for difflib's Longest Common Substring #144164

[ZeroIntensity]

A single iteration isn't really reliable enough for benchmarking. Could you provide benchmarks using at least several thousand iterations?

[tim-one]

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]

Noting that "Fibonacci strings" run massively faster with this approach:

https://discuss.python.org/t/include-time-and-space-complexity-in-documentation/105683/36

[dg-pb]

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]

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.