moonbitlang / core / 6571

89%

push

github

perf(quickcheck): build collection shrink candidates lazily

Getting the first shrink candidate from a collection walked the whole
collection twice. `Shrink for Array` and `Shrink for @list.List` both end
their candidate chain with `.concat(shr_sub_terms(..))`, and `concat` takes
its second iterator by value, so the per-element chain — an `O(n)` recursion
allocating an iterator per element — was built before a single candidate was
demanded. Structural candidates come first and usually settle the shrink, so
that work was almost always thrown away. `removes_array(n, n, xs)` then copied
all `n` elements into a prefix it immediately discarded, only to yield `[]`.

Wrap the per-element chain in `deferred` — a `@lazy.Lazy` cell behind an
`Iter`, so it is built on the first `next()` and memoised there — and return
the empty array directly when `k == n`. The candidate
sequences are unchanged: `xs[k:]` is empty exactly when `k == n`, so the old
code already yielded `[]` there. That also makes `removes_array`'s
`xs1.is_empty()` branch unreachable, so it goes, and the `n == xs.length()`
invariant both guards now depend on is written down.

First candidate from a 1,000-element collection, native release:

| Collection | Before    | After     |
| ---------- | --------: | --------: |
| Array      | 121.52 µs | 236.84 ns |
| List       | 287.79 µs | 147.79 µs |

End to end on `@quickcheck.check` with default settings, that is worth 20-25%
when the counterexample is large enough to shrink from and 0-4% when it is
small.

`List` keeps an `O(n)` first candidate because its ordering starts at `k = 1`,
so the candidate it has to produce is an `n - 1` element list; only the second
traversal goes away. The benchmark uses 1,000 rather than 10,000 elements
because `removes_list` recurses once per element, which overflows the stack on
js and wasm-gc at the larger size.

Based on #4152 by mizchi, restricted to the changes that do not alter the
candidate ordering, since the ord... (continued)

6 of 6 new or added lines in 3 files covered. (100.0%)

16313 of 18280 relevant lines covered (89.24%)

274746.52 hits per line