moonbitlang / core / 6822

89%

push

github

perf(immut/hashset): return the same set when add/remove change nothing

- `add` of an element already present: the Leaf/Flat arms already
  returned `self`, but every Branch above them still copied its
  children array and allocated a new node. Now a Branch whose child is
  unchanged returns itself, and `HashSet::add` returns `self`.
- `remove` of an absent element: the same, through `remove_with_path`
  and `HashSet::remove`.
- `union` / `intersection` / `difference` return early for a subtree
  shared by both sets, so combining a set with a version derived from
  it (e.g. `s.union(s.add(x))`) touches only the changed paths.

Observable results are unchanged; no-op updates now also return the
physically same set, which keeps later `==` O(1). A new quickcheck runs
set operations between a set and versions derived from it under all
five collision regimes of the existing canonicity tests, checks them
against a model and canonical rebuilds, and checks the identity of
no-op updates.

Release, 100k-element set, main -> this:

| bench                          | native          | js              | wasm-gc         |
|--------------------------------|-----------------|-----------------|-----------------|
| add existing x1000             | 378 -> 42us     | 162 -> 66us     | 210 -> 34us     |
| remove absent x1000            | 289 -> 36us     | 118 -> 51us     | 156 -> 27us     |
| add new x1000 (control)        | 394 -> 377us    | 197 -> 201us    | 191 -> 193us    |
| union with a derived version   | 2.69ms -> 0.59us| 3.40ms -> 0.80us| 1.64ms -> 0.48us|

Codex review: "No blocking issues found. No-op identity propagation preserves canonical shapes; all three algebra shortcuts are correct, including collision buckets."

Signed-off-by: Codex CLI <codex@openai.com>
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

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

16509 of 18400 relevant lines covered (89.72%)

313957.4 hits per line