Noticed while looking into a regression that caused deep completions to run spuriously (#62665): there appeared to be a lot of low-hanging fruit to optimize the performance of deep completions. For example, I analyzed one of our completion benchmarks on Kubernetes, and observed that type checking was only 65ms, while deep completion took an additional 100-200ms. I think we can get completion latency much closer to type checking latency, even while scanning many deep candidates.

The potential optimizations I see are very similar to what we did for workspace/symbol requests:

1. Add concurrency: completion is single-threaded at present.
2. Avoid pre-building strings, by performing fuzzy match before assembling the fully qualified symbol path.
3. Use a faster fuzzy matcher (and fix ranking edge cases)
4. Exclude deep candidates earlier, once their score is too low (we only ever serve 3 candidates!). If we make scores only decrease throughout 'addCandidate', and exit early, we can likely avoid a lot of unnecessary type inference.

Originally posted by @findleyr in #62665 (comment)