moonbitlang / core / 6289

91%

push

github

perf(set): probe with unchecked array access

Every probe index in `Set` comes from `hash & capacity_mask` and is
re-masked as `(idx + 1) & capacity_mask` on each step, so it is always in
bounds for `entries`, whose length is `capacity`. The bounds check on
those accesses is provably redundant.

Convert the eleven masked-probe sites to `unsafe_get` / `unsafe_set`,
with the invariant stated once at the top of the file and a marker at
each loop head.

`Set` is a linked hash set, so as with `Map` its `entries` accesses take
indices from two places: masked probe indices, and slot indices stored in
the list itself (`prev`, `tail`, and the ones the copy path walks). Only
the first kind is converted; every access through a stored index keeps
the checked form, since their being in bounds rests on the list being
maintained correctly rather than on arithmetic alone.

`shift_back` is unchecked, but on a local caller-based proof rather than
on that invariant: both of its callers pass masked probe indices. `Set`
has no `retain`, so unlike `Map` there is no route reaching it with a
stored index at all. That proof is also what makes the `set_entry` call
inside it sound.

Also adds `set/linked_hash_set_bench_test.mbt`, covering insertion, hits,
misses and add+remove.

Measured against `main`, n=50000, interleaved in one session:

| backend | op | main | this | change |
| ------- | -- | ---- | ---- | ------ |
| js      | `add`           | 3.41 ms | 2.87 ms | 16% faster |
| js      | `contains` hit  | 1.20 ms | 1.02 ms | 15% faster |
| js      | `contains` miss | 1.40 ms | 1.16 ms | 17% faster |
| js      | `add+remove`    | 5.05 ms | 4.14 ms | 18% faster |
| native  | all             |         |         | within noise |
| wasm-gc | all             |         |         | within noise |

Same shape as the other three containers: the saving is the explicit
length comparison js emits per access, so js gains and the two backends
whose array access traps inherently do not. T... (continued)

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

16760 of 18443 relevant lines covered (90.87%)

305822.04 hits per line