GeezerVison

@tim-one I know this is probably ancient code to you :) git blames you for working on the code 23 years ago. Could you maybe share some thoughts on the optimization? Thanks!

However, in real world scenario, it does not make much sense to diff/match two sequences with a giant vocabulary,

To the contrary, comparing lists of lines is by far the most common - and important intended - use case, where a "letter in the alphabet" is the entire content of a line. I don't know why you would want to compare text files as sequences of characters instead, but "so don't do that" comes to mind 😉.

Two common uses for comparing sequences of characters come to mind:

1. When a higher-level diff (by lines) wants to find the character-level differences between two mismatching lines. Indeed, lots of code inside difflib does that, to support its higher-level file-differencing functions. In that case, the sequences are typically quite short (under a hundred characters each).
2. Newbies comparing multi-megabyte DNA sequences, They'll never be happy with difflib, or with anything else short of highly specialized differencing algorithms designed for their domain.

So the patch looks good, but I'm skeptical of that it addresses a "real problem" that's common enough to be worth any slowdown in the actual common cases. The autojunk gimmick was added to address "very common" repeated lines, and it's good at speeding those cases, but it was A Big Mistake to enable it by default.

What would be welcome is a different algorithm specifically designed for "long sequences from a small alphabet" cases. SequenceMatcher works OK for those, provided the sequences aren't very long, but the core algorithm was really designed for "giant alphabet" cases (viewing text files as sequences of lines).

BTW, if you want to pursue this, there's an "optimization" I never bothered with because I didn't expect it would pay in the common cases (which I apparently have a different idea of than you have 😉): the one-at-a-time comparison of the j's to blo and bhi are obviously magnets for contrived bad cases. Instead, something along the lines of:

js = b2j[a[i]]  # this is assuming we know a[i] is in the dict
lo = bisect_left(js, blo)
hi = bisect_left(js, bhi, lo)
if lo or hi < len(js): # or maybe faster to always do the slice; it's correct either way
    js = js[lo : hi]

That finds all the j's in range efficiently regardless of how many are out of range, and regardless of how many are in range, materializes them in a list "at C speed" instead of appending one at a time "at Python speed". The result is the value of your cache, but computed in advance without Python-level looping.

Okay I might have misunderstood the usage of SequenceMatch. I agree that using lines would be a better way to do diffs.

If we do not expect duplicate items, then even the bisection may not be able to compensate the extra cost of creating lists and doing the bisection right? We might still slow down the cases where there's no duplicate.

I'll leave the decision to you, I'm okay if things keep the way they are. If you think this could be helpful when users use strings as the sequence instead of list of strings, I'll do the bisect optimization.