Completion should take <16ms most of the time

[matklad]

Code completion performance is more important than it seems. Obviously, completion shouldn't take a second or two. But even for "almost instant" completion, theres' a huge difference in experience when going 300ms -> 150ms -> 50 ms -> 16ms. It's difficult to perceive such small differences by just eyeballing a single completion, but it does affect fluency of typing a lot.

Historically, we haven't payed much attention to completion, barring obvious regressions. It was, and it is, generally fast enough. But it seems like we are at the point where it makes sense to push performance here a bit.

The 16ms is the boundary such that it doesn't make much sense to go beyond it (as thats comparable to typing latency), and which should be achievable. The size of the result is small, and the work should be roughly linear in the size of the result.

The best way to start here is to set this config:

    "rust-analyzer.server.extraEnv": {
        "RA_PROFILE": "handle_completion>16",
    },

and check Code's output panel for profiling info, which looks like this:

   85ms - handle_completion
       68ms - import_on_the_fly @ 
           67ms - import_assets::search_for_relative_paths
                0ms - crate_def_map:wait (804 calls)
                0ms - find_path (16 calls)
                2ms - find_similar_imports (1 calls)
                0ms - generic_params_query (334 calls)
               59ms - trait_solve_query (186 calls)
            0ms - Semantics::analyze_impl (1 calls)
            1ms - render_resolution (8 calls)
        0ms - Semantics::analyze_impl (5 calls)

Keep in mind that rust-analyzer employes lazy evaluation. That means that if both f and g call s, and s is slow, then s time will be attributed to either f or g depending on their relative order.

Another place to look at is the end-to-end request flow in the main loop. Profiling captures only the computation, but it's important that completion is not blocked by other requests.

It would also be sweet to implement some maintainable benchmarks here. This would have high impact, but I don't know how to best approach this.

Other that that, just look at the core with the profiler and try to make slow things faster!

[SomeoneToIgnore]

Related issue about the benchmarks: #6633

A few comments on the interesting places in the handle_completion test profiling trace:

• import_on_the_fly @ shows that we look up imports for blank input, which we only do, when searching for the associated items' completion (autoimporting traits).
  We optimize away struct search, performing the actual search after the 3rd symbol in the completion input, but we cannot optimize the associated items this way: showing methods and functions not right away is awkward

• the time difference between import_assets::search_for_relative_paths and trait_solve_query is 8ms, but 6ms are not shown in the profiling info, a few more profile::span placed in the modules used inside the import_assets::search_for_relative_paths should help to locate them

• interesting to note, that it took only 2ms to look up all traits with at least one associated item in the project, as the find_similar_imports profile span tells.
  We can still improve it nonetheless, this might be beneficial for other import_on_the_fly completion cases such as struct completions, we can remove that "after the 3rd symbol" "optimisation", but this all requires a separate set of checks.

As an optimisation idea, we can use a better key in import_map
https://github.com/rust-analyzer/rust-analyzer/blob/2c735ed734be9b9041921478e0049fffd7160f78/crates/hir_def/src/import_map.rs#L161

There we have an fst (the index we store textual full path strings in) that does a blazingly fast fuzzy search on the completion input, for our test profiling case.
Now, we use a lowercased path string, as a weird idea, we can prepend the paths in keys with special symbols (©, Ѭ?), depending on the entity type, thus decreasing the number of checks we need to do after getting the search results from fst.

• trait_solve_query is called within the depth of the trait resolution, where we send all traits looked up on the previous step into chalk:

https://github.com/rust-analyzer/rust-analyzer/blob/342bf41022fa78856a48560b521ea32aa76f6f06/crates/ide_db/src/helpers/import_assets.rs#L267-L283

to retain only the traits that the completion receiver (some::path:: or struct.) implements.
We can limit the number of traits to check, but most probably not fully eliminate it.

There's a way to find a part of the traits that are implemented for a certain struct, which is used in the implementations code lens: https://github.com/rust-analyzer/rust-analyzer/blob/7967ce85cfc5fc2b1996425b44f2a45d0841c8ff/crates/ide/src/goto_implementation.rs#L41

Alas, it's limited and does not find some classes of trait impls entirely, and getting us there might be hard.
For example, one of those trait categories are the blanket trait impls: impl <T> MyTrait for T.
The following FIXME has two links with deeper ideas on the topic:
https://github.com/rust-analyzer/rust-analyzer/blob/342bf41022fa78856a48560b521ea32aa76f6f06/crates/ide_db/src/helpers/import_assets.rs#L177-L181

Yet, the fst lookup collects the all possible traits in the project for solving, including the ones that are not detected by the lens' code.
If we could come up with the way to filter out fst results to retain only the traits from such categories, we can reduce the number of trait solvings, optimising the slowest place in the current profile trace.
Additionally, we'll need to extract and profile the lens' code for finding the impls and add some code to filter out the traits, extract their associated item names and compare those to the fst search results (to reuse the approach for non-empty completion input)

[matklad]

Some more assorted thoughts:

• on the fly imports are fundamentally costlier than anything else in completion, so it makes sense to specifically optimize that
• the set of auto-imporatble items doesn't change between funcitons, so we might want to cache that
• more generally, completions for xs.f and xs.fo are virtually identical, we should ensure that the second one takes almost no time
• there's discontinuity in completion speed: it the completion is fast enough, code shows completion list without ctrl+space. We must always hit this breakpoint
• on the protocol/API level, it might be worthwhile to separate immediate completions and slow completions. Itis imrortant that, eg, snippets are always instant, but its ok if flyimport is async
• on the protocol level, we should measure the delay between the time we get a notification about a new char typed, and the time we get the completion request.

[matklad]

#8254 should help with perf optimization workflow.