moonbitlang / core / 6196

91%

push

github

perf(sorted_set): probe fallback for strongly asymmetric difference/intersection

Follow-up to the split-based rewrite (#3315). Benchmarking old vs new
showed the split-based merge regressed small.difference(large) by
~350-560x: its upfront copy_tree of both operands is a Theta(n + m)
floor, while the old probe loop was O(n log m) — 2.7us vs 1.5ms for
100 vs 100K elements on native.

difference now falls back to the probe loop when self.size is below
src.size / 16, and intersection (whose key set is symmetric and fits
in the smaller side) probes with the smaller side under the same
cutoff. When the probing side is src, each match inserts the value
looked up in self, preserving self's stored representative for types
whose Compare inspects only part of the value — the same semantics as
the split path, which always emits self's va. The 1/16 cutoff is
worst-case-safe on all four backends: at the boundary (n=6000,
m=100K, disjoint sets so every probed element is inserted) the probe
loop still beats the split merge on native (0.88ms vs 1.60ms), js
(0.66 vs 0.78), wasm-gc (0.55 vs 0.68) and wasm (3.6 vs 4.0), while
at n = m/8 the split merge already wins the same worst case (native
1.70ms vs 1.93ms). symmetric_difference needs no guard: both sides
land in the result, so the copies are inherent.

Measured effect (guarded API vs old loop, native / js / wasm-gc / wasm):
- difference 100 vs 100K: parity at 2.2us / 2.3us / 1.8us / 11.5us
  (was 1.5ms / 0.87ms / 0.69ms / 3.8ms through the unguarded merge)
- intersection 100K vs 100: 10us vs 1.25ms / 7us vs 2.3ms /
  6us vs 1.2ms / 34us vs 3.7ms — beats even the old code, which
  always iterated self
- equal-size 100K, 50% overlap: unchanged split path, 2.4-9.1x
  faster than the old loops across backends

Tests: a quickcheck property forcing the asymmetric fallback in all
operand orders against the filter model; whitebox invariant scenarios
at 30-vs-3000 sizes; and a key-only-Compare payload test proving all
three... (continued)

15 of 15 new or added lines in 1 file covered. (100.0%)

16293 of 17960 relevant lines covered (90.72%)

333951.39 hits per line