Files
trs-80andClaude Opus 5 6880984b4a perf(relevance): order BM25 query terms once, not once per document (#3468)
## Description

`bm25_score` collected `query_freq.keys()` into a `Vec` and sorted it on
every call. That sort exists only to make matched-term output
deterministic, and the query is fixed for a whole batch — so
`score_batch` repeated the same allocation and sort once per document.

Closes # N/A

## Type of Change

- [ ] Bug fix (non-breaking change which fixes an issue)
- [ ] New feature (non-breaking change which adds functionality)
- [ ] Breaking change (fix or feature that would cause existing
functionality to change)
- [ ] Documentation update
- [x] Performance improvement
- [ ] Code refactoring (no functional changes)

## Changes Made

- `query_freq` is now a `BTreeMap<String, usize>` instead of a
`HashMap`. This **removes** the work rather than hoisting it: the map
already iterates in key order, so the collect-and-sort disappears
entirely and both `score` and `score_batch` benefit. Net effect on
`bm25_score` is fewer lines, not more.
- Added `benches/bm25_scoring.rs` (criterion, following the existing
three benches) varying document count and query length.
- Added `examples/bm25_query_prep_parity.rs`, the harness backing the
bit-identical claim below.
- New test
`matched_terms_are_lexicographic_regardless_of_context_order`. To be
clear, this does **not** fail on the base commit — the base sorts too.
It is a forward guard: swapping back to a `HashMap` without restoring
the sort would make matched-term order nondeterministic, and this
catches that.

**Why `BTreeMap` rather than a hoisted sorted `Vec`.** A `Vec` passed
down from `score_batch` would keep iteration contiguous, but it needs a
signature change, a second construction site in `score`, and leaves the
sort in the code. The `BTreeMap` deletes the sort outright, and it
measured faster in every shape tested, so the extra machinery was not
worth it.

## Testing

- [x] Unit tests pass (`pytest`)
- [x] Linting passes (`ruff check .`)
- [x] Type checking passes (`mypy headroom`)
- [x] New tests added for new functionality
- [x] Manual testing performed

### Test Output

```text
$ cargo test --release --lib
925 passed; 0 failed; 1 ignored

$ cargo test --release --lib relevance
49 passed; 0 failed

$ cargo clippy --release --all-targets     # no errors
$ cargo fmt --check                        # clean

# Python side, against a maturin build of THIS branch (see note below):
$ pytest tests/test_relevance.py tests/test_relevance_extra.py \
         tests/test_relevance_split.py tests/parity/ \
         tests/test_acceptance.py tests/test_issue_746_tool_search.py -q
124 passed, 4 skipped
```

## Real Behavior Proof

- Environment: macOS 15 (arm64), Rust release profile, criterion 0.8,
Python 3.13.11, worktree off `upstream/main` @ `e67b3c8a`.
- Exact command / steps: `cargo run --release --example
bm25_query_prep_parity > out.txt` on this branch and with
`src/relevance/bm25.rs` stashed, then `diff`. For timings, `cargo bench
--bench bm25_scoring` on each side, run twice in opposite order to
control for thermal drift. Python tests were run against a `maturin
build --release` wheel from this branch, not a copied `.so`.
- Observed result: **bit-identical output.** The parity harness prints
raw IEEE-754 score bits (not decimals), rankings, reasons and matched
terms for empty batches/contexts/documents, no-overlap, repeated query
terms, exact ties, the long-token bonus, and 3 configs x 5 document
counts x 3 query lengths. Baseline and candidate produce the same 3,739
lines, SHA `4e48098593e36aa1937e1629c4048e1280cfab47`. Timings,
candidate faster in all nine shapes:

  | shape | baseline | candidate | delta |
  |---|---|---|---|
  | 10 docs, 4-word query | 51.55 us | 50.22 us | -2.6% |
  | 10 docs, 16-word query | 60.72 us | 56.49 us | -7.0% |
  | 10 docs, 64-word query | 65.94 us | 61.39 us | -6.9% |
  | 100 docs, 4-word query | 515.4 us | 504.7 us | -2.1% |
  | 100 docs, 16-word query | 590.6 us | 553.2 us | -6.3% |
  | 100 docs, 64-word query | 597.6 us | 562.4 us | -5.9% |
  | 1000 docs, 4-word query | 5.184 ms | 5.133 ms | -1.0% |
  | 1000 docs, 16-word query | 5.926 ms | 5.639 ms | -4.8% |
  | 1000 docs, 64-word query | 5.975 ms | 5.631 ms | -5.8% |

The reverse-order confirmation run reproduced the 64-word column at
-5.5%, -4.4% and -5.9%.
- Not tested: real proxy or agent workloads — these are synthetic
documents from a fixed 16-word vocabulary, and no end-to-end latency
claim is made. Only x86-free Apple-silicon measurements. CJK content
takes a separate scorer in `text_crusher` and is unaffected.

## Runtime Rollout Safety

- Rollout-managed feature(s): none; no flag or channel gates this.
- Minimum rollout channel: N/A.
- Stable/default behavior changed: no. Scores are bit-identical, and
rankings, reasons and matched-term ordering are unchanged.
- Kill switch / disable path: none needed; there is no behavioral switch
to disable.
- Unsafe override required: none.
- Qualification impact: none. Scoring output is unchanged, so no
re-qualification of compression decisions is required.
- Rollback path: revert the commit. `bm25_score` is a pure function over
its inputs with no persisted state, so nothing needs migrating in either
direction.

## Review Readiness

- [x] I have performed a self-review
- [x] This PR is ready for human review

## Checklist

- [x] My code follows the project's style guidelines
- [x] I have performed a self-review of my code
- [x] I have commented my code, particularly in hard-to-understand areas
- [x] I have made corresponding changes to the documentation
- [x] My changes generate no new warnings
- [x] I have added tests that prove my fix is effective
- [x] New and existing unit tests pass locally with my changes
- [x] I did **not** edit `CHANGELOG.md`

## Additional Notes

- The comment above the loop was rewritten rather than deleted: it
explains why terms are visited alphabetically at all, which is still the
load-bearing reason the ordering is not an implementation detail.
- Documentation: no user-facing docs describe this internal scoring
path; the behavioral contract lives in that comment and in the new
ordering test.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

Co-authored-by: Claude Opus 5 (1M context) <noreply@anthropic.com>
2026-09-24 16:45:35 -05:00
..