moonbitlang / core / 7990

88%

push

github

fix(hashset,set): don't grow when adding a key that is already present (#4759)

* fix(hashset,set): don't grow when adding a key that is already present

HashSet and Set checked `size >= grow_at` before probing, so adding a key
that was already in a full table doubled it for nothing. Check the threshold
only once the key is known to be absent (before any slot is mutated), as
builtin Map and HashMap already do. Set::add_and_check now delegates to the
same probe instead of duplicating it.

Part of #4636.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

* chore: add license headers to new whitebox tests

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

* perf(hashset,set): place the new entry directly after growing

The previous commit restarted the probe after growing, re-running key
comparisons on a key already known to be absent. Probe without mutating
instead, then either grow and place the entry with `rehash_place_entry`,
or displace and insert as before. This also drops the duplicated grow check
from the two insertion branches.

A whitebox test with all-colliding keys pins that adding the key that
triggers growth compares each existing key once.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

* perf(hashset,set): keep the probe loop; grow and add directly

The previous commit made the probe return a (slot, displaced) tuple and
inserted after the loop. That avoided re-probing after growth but cost
HashSet::add ~3-5% on the common path (native bench, n=50000). Restore the
original loop shape and, only in the two branches that would grow, call
`grow_and_add`, which grows and places the entry via `rehash_place_entry`
without comparing keys again. HashSet::add and Set::add are now at parity
with main.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

* revert(hashset,set): go back to restarting the probe after growing

Reverts 63e217f1e and 3d30e6d78. After growing, `rehash_place_entry` walks
the same probe chain the r... (continued)

10 of 10 new or added lines in 2 files covered. (100.0%)

25245 of 28534 relevant lines covered (88.47%)

418738.5 hits per line