Skip to content

AdamDawidKrol/rangeset

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

1 Commit
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

rangeset (0.4.0) — quadratic in-place set-ops fix

A minimal fork of the rangeset crate (0.4.0, from tlsnotary/tlsn-utils) with a performance fix to the in-place set operations.

What changed

RangeSet::union_mut and RangeSet::difference_mut were O(set size) per call (the stock versions extend+sort_merge the whole vector, or rebuild the set from an iterator, on every call). Calling them once per item against a growing set — e.g. mpz's zk-core memory View unioning a range per allocation while proving a large transcript — is therefore O(N^2).

This fork exploits the maintained sorted/disjoint/non-adjacent invariant:

  • union_mut: O(1) append/coalesce at the tail; full sort_merge only as a fallback when an incoming range lands out of order.
  • difference_mut: binary-search the overlapping window and splice the trimmed pieces in place (O(log m + affected)), instead of a full rebuild.

All upstream unit tests (36) still pass. The upstream home for this fix is tlsnotary/tlsn-utils/rangeset; this standalone repo exists so it can be referenced as a git dependency from the tlsn-mpc-hang proxy-repro reproducer.

About

rangeset 0.4.0 with an O(N^2)->O(log m) fix to union_mut/difference_mut (tlsn proxy-repro)

Resources

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT

Stars

Watchers

Forks

Releases

No releases published

Packages

 
 
 

Contributors

Languages