Index cross-file identifier candidates

perfloop/ruff · INEFFICIENT ALGORITHM

https://perfloop.ai/t/oss/case_zxdp4mbx2e

Verdict

VERIFIED · settled 2026-08-12

What happened: The paired measurements met the required improvement.

Hypothesis

A static outgoing-call check from `crates/ty_ide/src.references` reported calls to `ruff_db::source_text` at line 128 and `contains_identifier` at line 129. The source read confirms that, after collecting every project file except the origin, the cross-file branch invokes that byte prefilter for every file before deciding whether to parse and semantically inspect it. `contains_identifier` uses `memchr::memmem::find_iter` over the source bytes, so text-negative files still require a full negative search. This is source evidence of the access shape, not a runtime measurement; cache residency, index-build cost, and whether this segment dominates request latency remain unmeasured.

The removed delta is one project-wide source-byte prefilter over text-negative files per eligible request, shifted to incremental index construction/update when source files change. Its growth axis is total workspace source bytes and file count; the relevant trigger is a large project where the requested identifier occurs in few or no files. Preserve the current semantic pass for candidates, including alias behavior and parameter keyword-label handling, so the index only narrows candidates rather than deciding references.

Proof target: benchmark the TyLspCrossFileReferences workload across workspace byte sizes and rare versus common identifiers, with repeated eligible references/rename requests and source edits. A CPU profile or counter must show baseline `contains_identifier`/memmem work scaling with text-negative workspace bytes, while the indexed version lowers scanned bytes and end-to-end LSP latency without false negatives; also record update latency and memory after file edits.

Change to test: Replace the per-request all-file source-text prefilter with an incrementally invalidated identifier-to-file candidate index that preserves the current identifier-boundary rule, then run the existing parallel semantic validation only for indexed candidates. Charge index maintenance and invalidation to changed files rather than treating it as free.

Where it lives

perfloop/ruff · crates/ty_server/src/server/api/requests/references.rs

Evidence

TyLspCrossFileReferences/references/cold/rare/256-files-64KiB · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 35292007 36666561 +3.7% (+1309653) −2842858 to +2417841 ≤ 5000000 PASSED
prefilter_B/op 16777216 16777216 0 0 to 0 ≤ 0 PASSED
candidate_cache_B 0 7491 +7491 +7491 to +7491 > 1 PASSED
salsa_B 16880497 16880585 +88 +88 to +88 ≤ 65536 PASSED

TyLspCrossFileReferences/references/steady/rare/64-files-4KiB · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 200264 45500 −76.4% (−153030) −164035 to −149531 < −10000 PASSED
prefilter_B/op 262144 0 −100% (−262144) −262144 to −262144 < −65536 PASSED
candidate_cache_B 0 2307 +2307 +2307 to +2307 > 1 PASSED
salsa_B 306865 306953 +88 +88 to +88 ≤ 65536 PASSED

TyLspCrossFileReferences/references/steady/rare/256-files-64KiB · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 286614 63932 −78.1% (−223888) −238501 to −209789 < −100000 PASSED
prefilter_B/op 16777216 0 −100% (−16777216) −16777216 to −16777216 < −8388608 PASSED
candidate_cache_B 0 7491 +7491 +7491 to +7491 > 1 PASSED
salsa_B 16880497 16880585 +88 +88 to +88 ≤ 65536 PASSED

TyLspCrossFileReferences/references/steady/common/64-files-1MiB · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 1233991 691731 −44.8% (−553307) −563572 to −522371 < −500000 PASSED
prefilter_B/op 67108864 0 −100% (−67108864) −67108864 to −67108864 < −33554432 PASSED
candidate_cache_B 0 2307 +2307 +2307 to +2307 > 1 PASSED
salsa_B 68675333 68675421 +88 +88 to +88 ≤ 65536 PASSED

TyLspCrossFileReferences/references/edit/rare/256-files-64KiB · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 730519 246944 −65.7% (−480253) −501631 to −465886 < −100000 PASSED
prefilter_B/op 16777216 65536 −99.6% (−16711680) −16711680 to −16711680 < −8388608 PASSED
candidate_cache_B 0 7491 +7491 +7491 to +7491 > 1 PASSED
salsa_B 16880497 16880585 +88 +88 to +88 ≤ 65536 PASSED

TyLspCrossFileReferences/references/edit/common/64-files-2MiB · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 5276143 3714569 −29.8% (−1569712) −1644041 to −1407233 < −1000000 PASSED
prefilter_B/op 134217728 209715 −99.8% (−134008013) −134008013 to −134008013 < −67108864 PASSED
candidate_cache_B 0 2307 +2307 +2307 to +2307 > 1 PASSED
salsa_B 135784197 135784285 +88 +88 to +88 ≤ 65536 PASSED

TyLspCrossFileReferences/rename/steady/rare/256-files-64KiB · 10 sample pairs

metric baseline candidate paired median change confidence range required result
ns/op 291874 61048 −78.8% (−229941) −239116 to −219262 < −100000 PASSED
prefilter_B/op 16777216 0 −100% (−16777216) −16777216 to −16777216 < −8388608 PASSED
candidate_cache_B 0 7491 +7491 +7491 to +7491 > 1 PASSED
salsa_B 16880497 16880585 +88 +88 to +88 ≤ 65536 PASSED

Checks: 4 of 4 passed. Verification: no defect found.

Timeline