Rain bbb9e3bb4a libtest: use binary search for --exact test filtering ...

The test array is sorted by name at compile time. When `--exact` is
passed in, use binary search for O(f log n) lookups instead of an O(n)
linear scan, under the assumption that f << n (which is true for the
most relevant cases).

This is important for Miri, where the interpreted execution makes the
linear scan very expensive.

I measured this against a repo with 1000 empty tests, running
`cargo +stage1 miri nextest run test_00` (100 tests) under hyperfine:

* Before (linear scan): 49.7s ± 0.6s
* After (binary search): 41.9s ± 0.2s  (-15.7%)

I also tried a few other variations (particularly swapping matching tests to the front of the list + truncating the list), but the index + swap_remove approach proved to be the fastest.

Questions:

- [ ] To be conservative, I've assumed that test_main can potentially receive an unsorted list of tests. Is this assumption correct?

2026-04-05 21:11:49 -07:00

..

src

libtest: use binary search for --exact test filtering

2026-04-05 21:11:49 -07:00

build.rs

Revert "library/test: always enable unstable features for miri"

2026-03-05 22:00:14 +01:00

Cargo.toml

Update getopts to remove unicode-width dependency

2025-08-29 15:08:51 +00:00