moonbitlang / core / 6825

89%

push

github

perf(immut/hashmap): return the same map when remove changes nothing

Same change as #4299, for the persistent HashMap:

- `remove` of an absent key: every Branch on the way down copied its
  children array and allocated a new node even though nothing below it
  changed. A Branch whose child is unchanged now returns itself, and
  `HashMap::remove` returns `self`.
- `union` / `intersection` / `difference` return early for a subtree
  shared by both maps (same keys and values, so the right-hand-side
  preference of union/intersection is moot), so combining a map with a
  version derived from it touches only the changed paths.

`add` always stores the new value, so it does not take a no-op
shortcut, and `union_with` / `intersection_with` still call `f` on
every shared key; both are unchanged.

A new quickcheck runs these operations between a map and versions
derived from it under the five collision regimes of the existing
canonicity tests, checks them against a model and canonical rebuilds,
and checks that removing an absent key returns the same map.

Release, 100k-entry map, main -> this:

| bench                              | native           | js               | wasm-gc          |
|------------------------------------|------------------|------------------|------------------|
| remove absent x1000                | 268 -> 39us      | 113 -> 52us      | 166 -> 29us      |
| remove present x1000 (control)     | 375 -> 388us     | 223 -> 230us     | 218 -> 219us     |
| union with a derived version       | 3.58ms -> 0.68us | 4.17ms -> 1.09us | 4.98ms -> 0.50us |
| intersection with a derived version| 2.50ms -> 0.68us | 3.37ms -> 1.01us | 1.91ms -> 0.46us |

(js control: three runs each, 222-224us before vs 226-234us after.)

Codex review: "No blocking issues found. The shortcuts preserve canonical shapes and right-hand value preference; the five collision-regime tests provide appropriate model and identity coverage."

Signed-off-by: Codex CLI <codex@opena... (continued)

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

16518 of 18409 relevant lines covered (89.73%)

314571.16 hits per line