Graphtage Files

Graphtage 0.5.0 is a performance release. The diff engine now prices string comparisons in batch and builds character-level edit lattices only for the edits it actually renders, which makes typical diffs 2.6x to 5.3x faster end to end, string-heavy ones up to 25x, and rendered diffs of wide dictionaries up to 64x. Getting there required changing how a string edit reports its cost, which changes the semantics of StringEdit's bounds and makes its edit_distance read-only, and it fixes a crash that made the pickle filetype unusable on any two files with differing binary payloads.

Breaking changes

No names were removed from the public API. The changes below are to behavior, and to one attribute that became read-only.

• StringEdit derives from ConstantCostEdit rather than AbstractEdit, and its cost is exact at construction. bounds() and tighten_bounds() are still there, inherited rather than overridden, but their semantics changed: bounds() returns a definitive range on the first call, and tighten_bounds() is a no-op that always returns False. A while edit.tighten_bounds(): loop still terminates; it now exits immediately (#197).
• StringEdit.edit_distance is a read-only property that builds the character-level lattice on first access, rather than an instance attribute assigned in __init__. Reading it yields the same EditDistance and the same edit script as before. Assigning to it now raises AttributeError (#197).
• EditDistance.__init__ takes a new keyword-only preprice: bool = True argument (#198).
• StringNode.calculate_total_size() returns a character count, so StringNode(b"hello").total_size is 5 rather than 8, matching what StringNode("hello") already reported. Inserting or removing a byte costs 1 rather than the 1 to 3 that the old len(str(byte_value)) charged (#194).
• graphtage.multiset.MATCHING_SIZE_WARNING_THRESHOLD rose from 400 to 250,000. The "this matching is large" warning on STDERR effectively no longer fires, because matchings of that size are no longer slow (#198).
• Diffs of unordered collections may select a different set of matches among equally optimal ones, because the pre-priced matcher breaks ties differently. The total edit cost is unchanged in all 24 tested cases, and ordered containers and all nine output formats render byte-identically (#198).

Performance

• make_distinct() hashes intervals on data identity rather than on span, which keeps colliding intervals apart. Rendered diffs are 5.5x faster on a 16-key dictionary and 63.9x faster on a 40-key one, 126.9s to 1.985s (#193).
• String edits compute their cost arithmetically and build the character-level lattice only when a formatter renders them. A diff prices many more pairs of strings than it prints: 33x to 113x faster on string-heavy inputs (#197).
• graphtage.batch_distance answers a whole cross product of Levenshtein distances in one batched min-plus scan over numpy arrays, about 15x faster than pricing the pairs one at a time (#195).
• EditDistance and MultiSetEdit pre-price their candidate pairs through that kernel and answer later cost queries from a cached block, and the matcher skips make_distinct when every edge is already definitive. End to end this is 2.6x to 5.3x on typical inputs and 24.8x on 60 long strings, 30.42s to 1.23s (#198).

New features

• graphtage.batch_distance computes exact all-pairs Levenshtein distances for two collections of strings. It ships python and numpy backends and picks between them by batch size; set GRAPHTAGE_BATCH_BACKEND to python or numpy to pin the choice (#195, [#200]).
• graphtage.levenshtein.exact_string_distance() returns the Levenshtein distance between two str or bytes without building an edit lattice (#197).
• graphtage.bounds.IdentityInterval (#193).

Bug fixes

• Diffing two bytes values with differing payloads no longer aborts with a traceback. Any two pickles whose binary payloads differed hit this (#194).
• A stray b no longer appears before the closing quote when a bytes diff is rendered (#194).

Packaging and infrastructure

• No new runtime dependencies: numpy and scipy were already required, and the batch kernel reuses them.
• Graphtage no longer starts a multiprocessing helper process when it draws a progress bar. tqdm's default write lock registered a semaphore, which started multiprocessing.resource_tracker; Graphtage is single-process, so it now installs a threading lock instead (#201).
• Dependency bumps for tqdm, ruff, sphinx_rtd_theme, and setup-uv (#188, [#191], [#199]).

Full changelog: https://github.com/trailofbits/graphtage/compare/v0.4.0...v0.5.0