The LoRAs page search ran difflib.SequenceMatcher over every token of every
cached entry. Matching entries exit at the substring check, so the cost was
paid entirely by the entries that do not match - exactly the state the list is
in while a word is still being typed. At 100k entries one non-matching query
took 1.7-3.2s, and the handler runs that work on the event loop.
Gate the matcher with two exact necessary conditions instead of a heuristic:
2*min(len_a,len_b)/(len_a+len_b) is an upper bound on the ratio, and so is
twice the character-multiset intersection (a matching block can only use
characters present in both strings). Pairs that fail either bound provably
cannot reach the threshold, so every result is unchanged.
A non-matching query now takes 0.28-0.36s at 100k entries (6-9x faster) and
54-72ms at 20k (was 0.32-0.62s). Add a Hypothesis equivalence test against the
previous implementation, a regression test proving obvious misses never reach
the matcher, and a library-scale benchmark.
Fixes#1179
Will Miao
f50cc8cc62