perf(vcs/score): apply_percentile is O(signals × n²) and re-paid on every cache hit and trend point

Chiusa
  • Qualcosa non va?
#1,267 2 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
3/5
Tempo stimato
1-2 giorni
Idoneità per principianti
72/100
Tipo di issue
Refactoring
Chiarezza
Specificata chiaramente
Stato di attività
Tranquilla
Stack tecnologico
rust
Ambito
performance

Direzione di ricerca

Start in src/vcs/score.rs at apply_percentile, where the quadratic nested scan lives; the issue's resolution plan prescribes replacing the per-element counts with a single sort_unstable_by(f64::total_cmp) per signal plus partition_point binary searches on v ± TIE_TOLERANCE, keeping mid-rank arithmetic untouched. Move the current quadratic implementation into src/vcs/score_tests.rs as a reference and A/B it bit-for-bit (f64::to_bits) over randomized inputs, including exact ties, ±1-ULP ratio ties, and a chained near-tie case. Done means unit tests pass, the doc comment reflects O(signals × n log n), make pre-commit passes, and a synthetic-repo run at 5k/10k files shows near-parity with --risk-formula weighted (no timing tests in the suite).

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

enhancement vcs

Summary

apply_percentile (src/vcs/score.rs) computes each file's per-signal mid-rank by scanning the whole value vector for every element:

for (i, &v) in values.iter().enumerate() {
    let less  = values.iter().filter(|&&o| o < v - TIE_TOLERANCE).count();
    let equal = values.iter().filter(|&&o| (o - v).abs() < TIE_TOLERANCE).count();
    …
}

That is two O(n) passes per element, per signal — O(signals × n²) with 10 extractors, so 20·n² float comparisons. A sort-based mid-rank is O(signals × n log n).

Measurements (verified on d86d3806, debug build, synthetic repo, --risk-formula percentile)

files ranked weighted percentile
5,000 ~0.15 s 3.1 s
10,000 0.2 s 12.5 s

4.0× per doubling — the ranking pass, not the walk, is the entire delta (the weighted run on the same repo is the walk baseline). Extrapolated: ~50 s at 20 k files, ~13 min at 100 k files (debug; release is faster by a constant, the quadratic stands).

Multipliers

apply_percentile runs inside replay::replay (src/vcs/replay.rs:268), so under percentile mode it is paid:

  • on every cache hit — the #334 design replays the event log per run, so the cache does not amortize this cost at all: an unchanged tree pays full quadratic on each invocation;
  • on every trend point — bca vcs trend replays per sample, multiplying by the point count.

Suggested shape

Per signal: argsort the values once, walk the sorted order grouping ties with the existing TIE_TOLERANCE (adjacent-difference grouping preserves the current absolute-tolerance semantics for the ratio-derived dilution signal), and assign each group its mid-rank. Same output, O(n log n).

RISK_SCORE_VERSION note: the doc requires a bump for changes to "the extractor set, the mid-rank scaling, or the normalization". A faithful reimplementation is value-identical (integer-derived signals compare bit-exact; tie groups are the same sets), so no bump should be needed — but the equivalence deserves a direct A/B test over randomized inputs comparing old vs new outputs bit-for-bit before deleting the old code. One caveat to check in review: chained near-ties (a ≈ b, b ≈ c, a ≉ c) are not transitive under the current pairwise tolerance, while sorted grouping is — construct that case and decide which behavior to keep (the current one can already count such a value as both less and equal for different partners; the clamp hides it).

Resolution Plan

  1. Reformulate the per-element counts as binary searches, not group assignment. The current pairwise counts are pure functions of the element's value and the signal's value multiset: less = #{o : o < v − TIE_TOLERANCE}, equal = #{o : |o − v| < TIE_TOLERANCE}. So per signal: copy the values, sort_unstable_by(f64::total_cmp) once (O(n log n)), then for each element compute less = sorted.partition_point(|o| *o < v − TIE_TOLERANCE) and equal = sorted.partition_point(|o| *o < v + TIE_TOLERANCE) − less — with care that the second predicate reproduces the open interval (v − TIE, v + TIE) exactly (strict < on both bounds matches, since |o − v| < TIE excludes both endpoints). Mid-rank arithmetic and clamp stay untouched.
  2. Why this beats the issue's suggested adjacent-difference grouping: grouping ties transitively changes behavior on chained near-ties (a ≈ b, b ≈ c, a ≉ c), forcing the review decision the issue flags. The binary-search form is bit-exact identical to the quadratic version for every input — including the non-transitive chained case, exact integer ties, and the ratio-derived dilution signal — so no RISK_SCORE_VERSION bump is needed, cached entries stay valid, and downstream scores are unchanged by construction.
  3. Equivalence test: move the current quadratic implementation into src/vcs/score_tests.rs as a test-only reference and A/B it bit-for-bit against the new code over randomized inputs (mixed magnitudes, exact ties, ±1-ULP ratio ties like 2/6 vs 1/3, and a constructed chained near-tie a ≈ b ≈ c with a ≉ c). Assert f64::to_bits equality on every risk_score. Also keep/extend the existing behavioral tests (ties share mid-rank, direction of dilution, n < 2 early return).
  4. NaN determinism: total_cmp gives sorted NaNs a defined position; signals are constructed non-negative/finite today (max(0.0) on both entropies, ownership share in [0, 1]), so add a one-line comment rather than runtime handling.
  5. Docs: update the apply_percentile doc comment (complexity note: O(signals × n log n); the tie-tolerance comment moves with the predicates) and the RISK_SCORE_VERSION doc stays untouched since the blend's observable output is unchanged.
  6. Validation: re-run the issue's synthetic-repo measurement at 5k/10k files to confirm the quadratic is gone (expect near-parity with --risk-formula weighted), then vcs test modules + make pre-commit. No perf assertion lands in the unit suite (timing tests are banned in this repo; the numbers go in the PR description).

Assessment

Dimension Rating
Difficulty Medium
Complexity Low
Priority Medium
Lingua principale
Rust
Stelle
32
Fork
3
Merge medio
1g 11h
PR unite (30g)
70

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di dekobon/big-code-analysis

Tutte le issue di dekobon/big-code-analysis

Issue simili

Altre issue su Rust

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.