rust-lang / rust-lang/rust-analyzer

Split symbol index into two

Open
#14,743 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-ide A-perf C-enhancement
Dominant language
Rust
Stars
16.9k
Forks
2.2k
Avg merge
1d 12h
Merged PRs (30d)
72

Description

I think this is a significant slowdown. If I try to fetch all symbols (including libraries, and without our limit) for rust analyser, I get the following status:

EDIT: the slowdown part is wrong, this is pre-existing, but I think this PR still elevates perf bug to architecture bug.

total number of results 98752 
computing symbol index for all libs: 3.64s
filtering by (trivial, empty) query: 16.70ms
converting resuults to : 98.54ms
handle_worskpace_symbol: 50.16s

I think this try_to_nav call is the single place where the the rest of 50 seconds went. (and this is unrelated to the PR, before the behavior was the same).

This is an essentially computationally hard problem -- this is a global search, and it's hard to make it lazy.

That's why the original design didn't use defs, but rather had a special data structure which materialized all parts of a def which is needed for rendering. That is, the intention of the code was to have impl TryToNav for FileSymbol to be O(1) and not triggering semantic analysis. So that we can compute LibrarySymbols once and then just never update them.

To clarify, this PR doesn't break it, because the code is slow even before the change. And it doesn't practically matter, because:

  • search in libraries is impossible to trigger anyway because LSP sucks
  • we have a limit on the number of items

However, while we had FileSymbol, we could fixed the bug. Without library symbols, you can't really just fix that.

Architectually, I think we really need two indexes here:

  • Name to Def, for semantic purposes like auto imports
  • Name to "JsonBlob", specifically for workspace/symbols query

Originally posted by @matklad in https://github.com/rust-lang/rust-analyzer/pull/14715#discussion_r1185944093

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by tracing the workspace/symbols path and the try_to_nav call described here, then compare the existing FileSymbol and LibrarySymbols representations. Review the discussion from PR #14715 and determine how separate Name-to-Def and workspace/symbols JsonBlob indexes should be structured. Done means the two indexing responsibilities are separated as described.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance, search
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.