Implement Suffix Automaton for difflib's Longest Common Substring

[dg-pb]

Feature or enhancement

Proposal:

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:
#106865

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.