v0.4.0

Clustering: 3.7× less CPU on the many-small-groups shape, every byte the same

cluster_canonicals in the shape find-dup-defs
issues it — thousands of calls per repository, most of them two or three long canonical bodies, a
few of them hundreds. Every call of one such run (2 892 calls, 9 527 strings, 23 M characters,
threshold 0.5) replayed through the library alone:

	0.3.5	0.4.0
single thread	9.78 s	2.66 s
12 threads (M3 Pro, 6 P + 6 E)	1.30 s	0.38 s

Every cluster and every min_sim bit is identical to 0.3.5 on three such replays; the tool's ten
output modes were diffed against its 0.3.5 build on two corpora, and nothing moved. The library's
own gates (fast_matches_reference, qualifies_matches_ratio_threshold, the GPU parity test)
pass unchanged.

What changed

• Only the automata that are scanned get built. A pair scans one string against the other's
  automaton; a string that is never the automaton side of a surviving pair never needs one — in a
  group of two that is one build, not two.
• Only spanning edges are tested. Single-linkage needs the connected components, not every
  edge: candidates are visited most-similar-first in batches with a union-find between them, and a
  pair already connected is not tested. Edge tests on the replay: 104k → 32k.
• The cluster minimum runs under a shared cap. Every intra pair is computed against the
  cluster's running minimum; a common prefix or suffix, or a single long block found during the
  scan, proves a pair above it before the recursion starts; the pair that is the minimum is
  always computed exactly.
• Narrow windows skip the automaton. Recursion windows whose b side is a handful of
  characters go to a direct row-by-row comparison; wider windows are taken largest-first, which
  closes both early exits in fewer windows.
• A cheaper automaton to build and to walk: a per-thread builder with four inline transitions
  per state, endpos ranges laid out by two length-order passes instead of a tree walk, sorted
  copies only for the few states with large endpos sets instead of a merge-sort tree over every
  position, and a 32-byte scan slot whose inline transition continues along b.

Measured and rejected on the way: an interval bound on fmatch as an in-scan reject (never
fires on code), a per-position window bound carried down the recursion, interleaving several
scans to overlap their cache misses, and a 128-bit character set in the scan slot.

API

• gestalt::gestalt_qualifies_ms now takes (a, b, sam_b, …) instead of the two lengths.
• gestalt::Sam::nodes() returns a Vec<[u32; 4]> (assembled on request) instead of a slice.
• New: gestalt::gestalt_edge_bounded (the edge test with every early exit, no ratio).

ratio, ratio_many, cluster_canonicals, cluster_canonicals_lsh, Rationer, simjoin and
the Python package are unchanged in signature and output.

Install

cargo add difflib-fast
pip install difflib-fast        # first PyPI release; wheels for Linux (x86_64/aarch64), macOS (arm64/x86_64), Windows