moonbitlang / core / 6290

91%

push

github

perf(builtin): probe `Map` with unchecked array access

Every probe index in `Map` 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 18 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.

`Map` is a linked hash map, so unlike `hashset` and `hashmap` it also
stores slot indices in the list itself -- `prev`, `tail`, and the index
`retain` destructures out of an entry. Every access through one of those
keeps the checked form. Such indices are in bounds too, being former
probe indices in a table that never shrinks, but that argument rests on
the list being maintained correctly rather than on arithmetic alone, and
that is not a foundation to put unchecked access on.

`shift_back` is the deliberate exception. It is reachable from `retain`
with a stored index, but `retain` performs its own checked read
immediately before calling, so `shift_back` has a local caller-based
proof that does not depend on the list invariant at all. It carries that
proof at its definition, and that proof is also what makes the
`set_entry` call inside it sound.

Also adds `builtin/linked_hash_map_bench_test.mbt`, covering insertion,
hits, misses, set+remove, and insertion-ordered iteration.

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

| backend | op | main | this | change |
| ------- | -- | ---- | ---- | ------ |
| js      | `set`        | 3.97 ms | 3.14 ms | 21% faster |
| js      | `get` hit    | 1.30 ms | 1.02 ms | 22% faster |
| js      | `get` miss   | 1.37 ms | 1.17 ms | 15% faster |
| js      | `set+remove` | 5.70 ms | 4.54 ms | 20% faster |
| native  | all          |         |         | within noise |
| wasm-gc | all          |         |         | within noise |

This is the largest js gai... (continued)

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

16763 of 18446 relevant lines covered (90.88%)

306235.83 hits per line