LSP Indexing
This page explains how eulix-lsp builds its workspace index: how it scans files, parses them, and commits them into the index that cross-file features read. It also explains why the commit used to slow down quadratically, and how a small change to call-site deduplication made indexing grow linearly with workspace size.
Crate / path:
eulix-lsp/src/backend.rs(spawn_scan),eulix-lsp/src/scan.rs,eulix-lsp/src/index.rs,eulix-lsp/src/state.rsLanguage: Rust Status: the dedupe fix is in the working tree onfix/lsp-148-syncand not committed yet Last verified against:bb695d1plus the working-tree changes Benchmark:eulix-lsp/bench/bench_lsp.py, results ineulix-lsp/bench/results/
Overview
When an editor starts the server, it sends initialized, and the server indexes the workspace in the background. Until that finishes, cross-file features have nothing to look up: go-to-definition into another file, references, call hierarchy, workspace symbol search, completion and rename. So the time to index is the time the user waits before the server is fully useful.
Indexing has three phases:
| Phase | Where | Threads | What it does |
|---|---|---|---|
| Walk | scan::collect_source_files |
the ignore crate’s walker |
Finds supported files. Honours .gitignore and .euignore, skips ignoreDirs and files over maxFileBytes, and stops at maxScanFiles (default 50,000). |
| Parse | scan::parse_all |
up to 4 blocking threads | Reads and parses each file into a ParsedFile. Files that fail are counted, not fatal. |
| Commit | ServerState::commit_disk_batch |
1, holding the index write lock | Adds every ParsedFile to the name index and the workspace cache in one pass, so nobody sees a half-built index. |
The index
Index (index.rs) stores names, not types. It holds two maps, each with a reverse map so a file can be removed without scanning the whole workspace:
defs: name → path → definitions. ADefis a name, kind, path, line range and optional container class.calls: callee name → list ofCallRef(path and line). This is what references, incoming calls, rename and the unresolved-call diagnostics read.defined_names/called_names: path → names, used byremove_file.
index_file(path, parsed) first calls remove_file(path), then adds the file’s definitions and call sites. That makes reindexing a file idempotent: indexing the same content twice gives the same index as indexing it once.
Why the commit was quadratic
Before the fix, each call site was added like this:
let sites = self.calls.entry(callee.to_string()).or_default();
if !sites.contains(&entry) { // walks every call to `callee` already recorded
sites.push(entry);
}
contains is a linear scan of every call site recorded so far for that name, across the whole workspace. Real code has names that are called from almost everywhere: len, unwrap, new and get, and in the kernel kfree and spin_lock. For a name with k call sites, adding them one by one costs about k²/2 comparisons. Doubling the workspace doubles k and quadruples the cost.
The check only exists to drop duplicates within one file, which can appear when call ranges overlap. Duplicates from other files can’t happen, because index_file has already called remove_file(path), so no entry for this path is left in any list.
The same cost appeared outside the scan too. Every open, reparse after an edit and watcher event runs index_file, and the scan holds the index write lock for the whole commit. So every request that needs the index waited for the entire commit.
The fix
Deduplicate within the file, in O(1), and push without scanning:
let mut seen: HashSet<(&str, usize)> = HashSet::new();
...
// remove_file ran above, so duplicates can only come from this file.
if callee.is_empty() || !seen.insert((callee, line)) {
continue;
}
self.calls.entry(callee.to_string()).or_default().push(CallRef { path: path.to_path_buf(), line });
The result is the same set of call sites, built in linear time. Two tests guard it: call_sites_are_deduplicated_and_sorted (duplicates within one file are dropped) and same_call_line_in_two_files_is_kept_and_reindex_does_not_duplicate (the same line in different files is kept, and reindexing a file adds nothing).
Measured results
Synthetic workspaces from bench_lsp.py: Python, Rust and TypeScript files, each defining helper and calling it 9 times, so one name has 9 call sites per file.
| Files | Scan before | Scan after | 100-file watcher batch before → after | Open → diagnostics before → after |
|---|---|---|---|---|
| 500 | 0.44 s | 0.06 s | 229 → 86 ms | 2.3 → 0.9 ms |
| 1,000 | 1.64 s | 0.11 s | 405 → 107 ms | 3.9 → 1.0 ms |
| 2,000 | 6.43 s | 0.24 s | 753 → 144 ms | 7.5 → 1.5 ms |
| 4,000 | 25.3 s | 0.41 s | 1,479 → 192 ms | 15.0 → 2.2 ms |
Before the fix, each doubling multiplied scan time by 2^1.97: quadratic. After it, by 2^1.0: linear.
On the Linux kernel (50,000 of its 64,531 supported files, under an 8 GB memory cap):
| Before | After | |
|---|---|---|
| Scan | 396 s | 49 s |
| Longest wait of an index request during the scan | 348 s | 2.1 s |
| CPU | 539 s | 190 s |
| Memory after scan | 2.47 GB | 2.48 GB |
Before the fix, about 340 of the 396 seconds ran on one thread inside the commit. After it, the commit takes about 3 seconds and parsing dominates.
The fix changes time, not memory.
Known limits and next steps
These were measured by the same benchmark and are not fixed yet:
- Parsing uses at most 4 threads.
ConfigcapsscanThreadsat 4 (.min(4)), even when the user sets more. On the kernel, CPU time grew by exactly 4 s per second while parsing, on a 12-core machine. - The index doubles memory. On the kernel, memory was about 1.25 GB after parsing and 2.49 GB after the commit. Each
DefandCallRefstores its ownPathBuf; interning paths as file ids would shrink this. - The memory budget is not enforced.
scanBudgetMb(default 500) andlazyScanare parsed but never read. The kernel run used five times the budget. remove_filestill walks the callers of hot names.sites.retain(|c| c.path != path)is linear in the callers of every name the file calls. That is why the watcher batch still grows with workspace size (86 → 192 ms). Storingcallsas name → path → lines, likedefs, would make removal proportional to the file.- Large results are not capped. References and incoming calls on
helperat 4,000 files return about 36,000 results (170 ms and 470 ms), and ten such requests raised peak memory from 122 MB to 434 MB. - Shutdown waits for a running commit. A
shutdownsent during the commit was answered only after the commit finished (6 s at 2,000 files, before the fix). - C coverage. Structs and macros are not indexed. On the kernel, 11 of 20 opened files had an empty outline, and go-to-definition found nothing on 49 of 60 call sites.
Correctness issues found alongside this work, also open:
- Rename of a name with no workspace definition, such as
len, edits every call to it in every open file and language. It should refuse. - Buffers are keyed by the editor’s URI string, while the index rebuilds URIs with
Url::from_file_path. With VS Code’s encoded URIs (c%3A,c%2B%2B), rename skips call sites and go-to-definition selects the whole line. Ignored tests ineulix-lsp/src/backend/uri_tests.rsreproduce both.
Reproducing the numbers
cd eulix-lsp
bench/build.sh <commit> # builds target/bench/eulixlsp-<commit>
python3 bench/bench_lsp.py target/bench/eulixlsp-<commit> --workspace ..
# a very large tree, with the server memory-capped:
systemd-run --user --scope -p MemoryMax=8G -p MemorySwapMax=0 \
python3 bench/bench_lsp.py <binary> --files '' --workspace /path/to/linux --scan-timeout 900
The before numbers are in bench/results/eulixlsp-bb695d1.json and eulixlsp-bb695d1-linux.json.