moonbitlang / core / 6827

89%

push

github

perf(hashset): reuse stored hashes in set algebra and equality

Every entry stores its key's hash, but `union`, `intersection`,
`difference`, `symmetric_difference`, `is_subset`, `is_disjoint` and
`==` re-hashed each key (O(len) per String key) through `contains` /
`add`, walked the set through `iter()` plus a closure, and `union`
rebuilt from an 8-slot table, regrowing about log2(n/8) times.

- Add a private `contains_with_hash`; `contains` is now a thin wrapper.
- `union` = `copy()` + `union_in_place` (which already reused hashes).
- The other operations loop over the entries directly and probe or
  insert with the stored hash (`add_with_hash`).

Both sets hash `K` with the same `Hash` impl, so a stored hash is
exactly what the old code recomputed. Results are unchanged; `union`'s
slot order and capacity follow `self` now (HashSet iteration order is
unspecified). A new quickcheck compares symmetric_difference,
is_subset/is_superset/is_disjoint, `==` and `union` with a model.

With no hashing left, these operations need only `K : Eq` (the
`Hash` bound became unused and fails `--deny-warn`), matching the
existing `union_in_place`. Relaxing a bound is source compatible.

Release, two 10k-element sets with 50% overlap, main -> this:

| bench                    | native           | js               | wasm-gc          |
|--------------------------|------------------|------------------|------------------|
| union String             | 3.51ms -> 668us  | 4.16ms -> 603us  | 3.81ms -> 595us  |
| union Int                | 2.91ms -> 578us  | 4.05ms -> 555us  | 2.77ms -> 472us  |
| intersection String      | 1.10ms -> 346us  | 1.28ms -> 314us  | 1.21ms -> 397us  |
| difference String        | 1.17ms -> 353us  | 1.27ms -> 349us  | 1.26ms -> 617us  |
| is_subset String (true)  | 528 -> 101us     | 876 -> 215us     | 932 -> 507us     |
| == String                | 553 -> 103us     | 818 -> 215us     | 962 -> 332us     |
| == Int                   | 128 -> 80us     ... (continued)

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

16524 of 18415 relevant lines covered (89.73%)

314391.76 hits per line