moonbitlang / core / 6829

89%

push

github

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

Same change as #4297 for the linked (insertion-ordered) `Set`.
`union`, `intersection`, `difference`, `symmetric_difference`,
`is_subset`, `is_disjoint` and `==` re-hashed every key through
`contains` / `add` and went through `each`/`for .. in` closures, and
`union` rebuilt from an 8-slot table.

- Private `contains_with_hash`; `contains` is a thin wrapper.
- `union` = `copy()` + `union_in_place`, which gives exactly the old
  order (`self`'s elements, then `other`'s new ones in order).
- The others walk the insertion list (`head` / `next`) and probe or
  insert with the stored hash, so result order is unchanged.

These operations, the `&` `|` `^` `-` impls and `Eq` now need only
`K : Eq` (the `Hash` bound became unused), matching `union_in_place`.
A new quickcheck checks every operation's result, order included,
with String keys.

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

| bench                    | native           | js               | wasm-gc          |
|--------------------------|------------------|------------------|------------------|
| union String             | 1.95ms -> 638us  | 2.12ms -> 765us  | 1.96ms -> 618us  |
| union Int                | 1.01ms -> 552us  | 1.23ms -> 676us  | 808 -> 513us     |
| intersection String      | 1.02ms -> 358us  | 1.27ms -> 397us  | 1.12ms -> 373us  |
| difference String        | 1.11ms -> 371us  | 1.26ms -> 361us  | 1.12ms -> 408us  |
| is_subset String (true)  | 598 -> 136us     | 843 -> 182us     | 861 -> 300us     |
| == String                | 598 -> 131us     | 834 -> 180us     | 876 -> 304us     |
| == Int                   | 158 -> 85us      | 301 -> 103us     | 198 -> 105us     |

Codex review: "No blocking issues found. Order and key representatives are preserved; copy() creates independent links, the self-union guard remains safe, and the relaxed Eq bounds match the implementation."

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

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

16535 of 18426 relevant lines covered (89.74%)

313988.0 hits per line