x/tools/gopls: optimize didChange handling

findleyr commented 3 years ago

Recent profiling has shown that, particularly on large codebases, snapshot cloning can significantly impact gopls' responsiveness.

Snapshot cloning is not optimized: there are lots of opportunities for performance improvement. For example:

URI.Filename() is a huge source of unnecessary cost; almost all URI manipulations could be done directly with the URI string rather than converting to file paths (which involves URI parsing).
Most of the maps in the snapshot could be replaced with an alternative data structure, optimized for fast cloning. For example, with an overlay that is occasionally compactified.
The import graph doesn't need to be rebuilt from scratch.
Known directories could be memoized.
The explicit inheritance of cache keys could probably instead be achieved with an asynchronous sweep.

Not sure which of these we'll do. Filing this as an umbrella issue to track improving performance.

CC @heschi @stamblerre

gopherbot commented 3 years ago

Change https://golang.org/cl/312689 mentions this issue: internal/lsp/cache: preallocate internal maps when cloning snapshots

anton-kuklin commented 3 years ago

Working on unnecessary URI.Filename() usage in snapshot reduction

gopherbot commented 3 years ago

Change https://golang.org/cl/312809 mentions this issue: internal/lsp/cache: improve snapshot clone perfomance

findleyr commented 3 years ago

Extending this more generally to didChange handling, as snapshot.clone is only one of the problems. There is some other stuff in e.g. didModifyFiles that's quite slow.

@justplesh thanks very much for your contribution, and interest. Right now we're still trying to figure out the best path forward for some of these optimizations. Hopefully we'll have a better sense of what needs to be prioritized next week. If you'd like, we can keep you in mind for anything that is relatively self-contained.

anton-kuklin commented 3 years ago

@findleyr Sure, please mention me or assign any lsp issue that I may work on. I'll be happy to work on it on some +- regular basis.

anton-kuklin commented 3 years ago

@findleyr will we merge my PR then or will we wait for some more fundamental approach?

findleyr commented 3 years ago

@justplesh we can proceed with your CL; it should be an improvement.

gopherbot commented 3 years ago

Change https://golang.org/cl/317292 mentions this issue: internal/lsp/regtest: add a benchmark for didChange

gopherbot commented 3 years ago

Change https://golang.org/cl/317410 mentions this issue: internal/lsp: memoize allKnownSubdirs instead of recomputing

stamblerre commented 3 years ago

We will probably focus next on:

URI.Filename() is a huge source of unnecessary cost; almost all URI manipulations could be done directly with the URI string rather than converting to file paths (which involves URI parsing).

findleyr commented 3 years ago

I spent some time analyzing our didChange performance last night. I've come to the opinion that using a map datastructure that is optimized for cloning is really just working around the lack of modularity in the snapshot. I think we should instead try to:

Separate data associated with overlays from data associated with on-disk files. We can share on-disk file state across snapshots if changes are restricted to overlays (the common case when typing in a buffer). @stamblerre and I paired on this, and mostly got it working for snapshot.files.
Move file parsing out of the generational cache. The overhead of inheriting all the handles is too high, and we already have a coherent definition of the file set for a snapshot, so we should be able to invalidate the set of parsed files without relying on the cache. This is subtle though.
Move metadata (and the import graph, etc) into a separate abstraction. Most changes do not invalidate metadata, and its accounting on each change is costly, specifically rebuilding the import graph. It's also a large source of complexity in snapshot.Clone, and hard to test.

I think doing these three things will take a huge chunk of CPU (and complexity) out of clone. There are still more optimizations to be had.

findleyr commented 3 years ago

I'm currently working on this, and think I'll be able to significantly reduce the cost via the following two changes:

Move all of our maps tracking metadata into an immutable data structure, that gets recomputed when metadata is loaded or invalidated not when the snapshot is cloned.
- Move everything that is pinned to a file (file handles, parsed files, symbol sets, etc) into a filesystem tree that can be either copy-on-write or locked at the directory level (either one is probably fine). This avoids work that is O(# files).

These two improvements take care of the majority of change processing CPU time; there are other improvements to be made, but they are all of second-order.

gopherbot commented 3 years ago

Change https://golang.org/cl/340735 mentions this issue: internal/lsp/cache: derive workspace packages from metadata

gopherbot commented 3 years ago

Change https://golang.org/cl/340853 mentions this issue: internal/lsp/cache: only clone metadata if something changed

gopherbot commented 3 years ago

Change https://golang.org/cl/340852 mentions this issue: internal/lsp/cache: use metadataGraph.Clone in snapshot.clone

gopherbot commented 3 years ago

Change https://golang.org/cl/340855 mentions this issue: internal/lsp/cache: delete checkSnapshotLocked

gopherbot commented 3 years ago

Change https://golang.org/cl/340730 mentions this issue: internal/lsp/cache: move metadata fields to a new metadataGraph type

gopherbot commented 3 years ago

Change https://golang.org/cl/340854 mentions this issue: internal/lsp/cache: don't walk URIs to invalidate metadata

gopherbot commented 2 years ago

Change https://go.dev/cl/410697 mentions this issue: internal/lsp/cache: two minor optimizations

gopherbot commented 2 years ago

Change https://go.dev/cl/410176 mentions this issue: internal/lsp/cache: optimize Snapshot.clone

gopherbot commented 2 years ago

Change https://go.dev/cl/340851 mentions this issue: internal/lsp/cache: build a new metadata graph on load

gopherbot commented 2 years ago

Change https://go.dev/cl/411554 mentions this issue: internal/lsp/cache: use persistent map for storing gofiles in the snapshot

gopherbot commented 2 years ago

Change https://go.dev/cl/413657 mentions this issue: internal/lsp/cache: persist known subdirs

gopherbot commented 2 years ago

Change https://go.dev/cl/413654 mentions this issue: internal/lsp/cache: use persistent map for storing files in the snapshot

gopherbot commented 2 years ago

Change https://go.dev/cl/413655 mentions this issue: internal/lsp/cache: use persistent map for storing packages in the snapshot

findleyr commented 2 years ago

I'm going to tentatively mark this issue as complete. There's more we can do here (and in fact, more CLs still pending), but we've largely succeeded :tada:

The benchmark I use for didChange latency (typing in Kubernetes) has already decreased from ~55ms->1.5ms. Since repositories significantly larger than Kubernetes are going to bump up against other limitations of gopls, I think we can reasonably say that didChange processing time is no longer a major issue.

(for record keeping we can continue to submit CLs against this issue, even though I am closing it now).

golang / go

x/tools/gopls: optimize didChange handling #45686