Use the scope map for auto-import checks
perfloop/ruff · INEFFICIENT ALGORITHM
https://perfloop.ai/t/oss/case_ydxbe2gn1p
Verdict
VERIFIED · settled 2026-07-23 · merged as astral-sh/ruff#27159
What happened: Validated on the sealed cached auto-import completion matrix (C/M = 64/64, 256/256, and 512/1024): the co-measured median fell from 3,514,303 ns/request to 3,007,003 ns/request, a 14.4% reduction (Mann–Whitney U p=0.0000108). The completion-count support metric remained 859 on both arms, and both the 39-test auto-import suite and the 521-result large-workload check passed. Replacing the scan with the existing borrowed `FxHashMap` lookup reaches the direct O(1) lookup ceiling for the already materialized scope map; a further attempt would require a broader importer/completion design change outside this narrow measured mechanism.
Hypothesis
Targeted source inspection showed that `add_unimported_completions` calls `members.satisfies` for every eligible result returned by `all_symbols` before constructing an import action (`completion.rs:2224-2243`). `MembersInScope::new` materializes an `FxHashMap`, but `find_member` linearly iterates that map to compare every name (`importer.rs:331-373`); `satisfies` invokes it at `importer.rs:375-389`. The decisive code-index incoming-reference check for `crates/ty_ide/src.impl.find_member` identified that `satisfies` call, confirming the target-path chain. `all_symbols` accepts every nonempty fuzzy-match result across workspace and dependencies, while the 1,000-result collection limit is applied only after this eligibility work, so short queries can make C large; M grows with bindings visible at the cursor. This is a separate per-candidate lookup cost from the already-published workspace-symbol catalog change. No latency or CPU profile was measured, so end-to-end impact remains a hypothesis. A case session should benchmark LSP completion across a matrix of matching-candidate cardinality C and in-scope-binding cardinality M, record CPU samples or a comparison counter in `find_member`, and verify the before/after C×M versus expected C lookup shape. It should also differential-test exact lookup results for imported, non-imported, aliased, and absent names.
Change to test: Replace `MembersInScope::find_member`'s `map.iter().find(...)` scan with the existing borrowed-key `FxHashMap` lookup path, preserving exact name-equality and `None` behavior. The same map already accepts string-like lookups in `ImportRequest::avoid_conflicts`; retain that lookup semantics while avoiding a full scan for every auto-import eligibility check.
Where it lives
perfloop/ruff · crates/ty_server/src/server/api/requests/completion.rs