moonbitlang / core / 6831

89%

push

github

perf(deque): wrap ring indices with a compare instead of `%` (#4301)

A deque's capacity is not always a power of two (`Deque(xs)` and
`capacity=` size the buffer exactly), so every `push_front`,
`push_back`, `pop_front`, `unsafe_pop_front`, `back`/`pop_back`
(`tail_index`) and `get` paid an integer division with a runtime
divisor. On those paths the index is always below `2 * cap` (`head < cap`
whenever the buffer is non-empty, and the added offset is below `cap`),
so one compare-and-subtract does it, as Rust's `VecDeque::wrap_add`
does. `push_front` decrements with an explicit wrap at 0. Queue, a
wrapper over Deque, gets the same speedup.

Only these hot single-element paths change; the bulk loops (`insert`,
`remove`, `append`, blits) keep their `%`.

Release, 1000-element deque with a 1000-slot buffer, main -> this:

| bench                                   | native        | js            | wasm-gc       |
|-----------------------------------------|---------------|---------------|---------------|
| pop_front/push_back x100000             | 523 -> 412us  | 550 -> 393us  | 578 -> 417us  |
| pop_back/push_front x100000             | 550 -> 406us  | 617 -> 385us  | 558 -> 409us  |
| get x100000 (wrapped buffer)            | 795 -> 655us  | 988 -> 697us  | 976 -> 706us  |

Codex review: "Verified zero-capacity pushes reallocate and reset head; reads and pops guard empty deques. Each changed wrap argument remains below 2 * cap, including capacity 1."

Signed-off-by: Codex CLI <codex@openai.com>
Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>

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

16540 of 18431 relevant lines covered (89.74%)

313884.54 hits per line