x/tools/gopls: optimize didChange handling #45686

findleyr · 2021-04-22T03:27:15Z

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 · 2021-04-22T16:05:00Z

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

anton-kuklin · 2021-04-22T19:01:06Z

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

The existing implementation uses a lot of URI.Filename() calls, which are pretty expensive. Moreover, these calls are not necessary, as long as all the actions could be done with the raw URI string. This patch removes such calls and uses simple string casts. Updates golang/go#45686

gopherbot · 2021-04-22T20:12:53Z

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

The existing implementation uses a lot of URI.Filename() calls, which are pretty expensive. Moreover, these calls are not necessary, as long as all the actions could be done with the raw URI string. This patch removes such calls and uses simple string casts. Updates golang/go#45686

findleyr · 2021-04-23T19:35:21Z

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 · 2021-04-23T19:43:33Z

@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 · 2021-04-23T19:45:24Z

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

For large codebases, the cost of copying these maps can be fairly high, especially when it needs to repeatedly grow the map's underlying storage. Preallocate these to the size of the original snapshot maps to prevent the need to grow the storage during the clone. Updates golang/go#45686 Change-Id: I4cfcd5b7cba8110e4f7e706fd9ea968aaeb6ff0c Reviewed-on: https://go-review.googlesource.com/c/tools/+/312689 Trust: Robert Findley <[email protected]> Run-TryBot: Robert Findley <[email protected]> gopls-CI: kokoro <[email protected]> TryBot-Result: Go Bot <[email protected]> Reviewed-by: Rebecca Stambler <[email protected]>

findleyr · 2021-04-25T18:22:05Z

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

The existing implementation uses a lot of URI.Filename() calls, which are pretty expensive. Moreover, these calls are not necessary, as long as all the actions could be done with the raw URI string. This patch removes such calls and uses simple string casts. Updates golang/go#45686 Change-Id: Ibe11735969eaf0cfe33024f08418e14bf71e7fc4 GitHub-Last-Rev: 67a3ccd GitHub-Pull-Request: #306 Reviewed-on: https://go-review.googlesource.com/c/tools/+/312809 Reviewed-by: Rebecca Stambler <[email protected]> Trust: Rebecca Stambler <[email protected]> Trust: Suzy Mueller <[email protected]> Run-TryBot: Rebecca Stambler <[email protected]> gopls-CI: kokoro <[email protected]> TryBot-Result: Go Bot <[email protected]>

gopherbot · 2021-05-05T19:32:45Z

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

Add a benchmark for the processing of workspace/didChange notifications, attempting to isolate the synchronous change processing from asynchronous diagnostics. To enable this, add a new type of expectation that asserts on work that has been _started_, but not necessarily completed. Of course, what we really want to know is whether the current notification has been processed, but that's ~equivalent to knowing whether the next one has been started. Really, it's off-by-one, but amortized over e.g. the 100 iterations of a benchmark we get approximately the right results. Also change some functions to accept testing.TB, because in a first pass at this I modified the regtest framework to operate on testing.B in addition to testing.T... but that didn't work out as IWL is just too slow to execute the benchmarks outside of the environment -- even though we can ResetTimer, the benchmark execution is just too slow to be usable. It seems like a fine change to accept testing.TB is some places, though. For golang/go#45686 Change-Id: I8894444b01177dc947bbed56ec7df80a15a2eae9 Reviewed-on: https://go-review.googlesource.com/c/tools/+/317292 Trust: Robert Findley <[email protected]> Run-TryBot: Robert Findley <[email protected]> gopls-CI: kokoro <[email protected]> TryBot-Result: Go Bot <[email protected]> Reviewed-by: Rebecca Stambler <[email protected]>

gopherbot · 2021-05-25T21:59:00Z

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

A lot of the time spent for every file change is recomputing the set of known subdirectories in the workspace. We can easily memoize these known subdirectories and avoid recomputing them on every file change. Do that here and update the set as file creations and deletions come in. Updates golang/go#45686 Fixes golang/go#45974 Change-Id: Ide07f7c90f0cafc3a3cc7b89ba14ab82d4e3ab28 Reviewed-on: https://go-review.googlesource.com/c/tools/+/317410 Trust: Rebecca Stambler <[email protected]> Run-TryBot: Rebecca Stambler <[email protected]> gopls-CI: kokoro <[email protected]> Reviewed-by: Robert Findley <[email protected]> TryBot-Result: Go Bot <[email protected]>

stamblerre · 2021-06-28T19:48:48Z

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 · 2021-07-13T14:04:09Z

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 · 2021-08-05T15:28:17Z

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 · 2021-08-11T14:44:10Z

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

gopherbot · 2021-08-11T14:44:11Z

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

gopherbot · 2021-08-11T14:44:12Z

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

gopherbot · 2022-06-06T20:40:10Z

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

1. Avoid unnecessary intermediate map updates. 2. Avoid accumulating defers in a loop when the control is simple. Yield: -10% CPU, -37% allocs. Typical results: $ go test -v ./gopls/internal/regtest/bench -run=TestBenchmarkDidChange -didchange_dir=$HOME/w/kubernetes -didchange_file=pkg/util/hash/hash.go Before: BenchmarkStatistics 100 25932206 ns/op 11684109 B/op 75458 allocs/op After: BenchmarkStatistics 100 23294195 ns/op 11293472 B/op 47299 allocs/op Also, move profiling logic outside the loop so that later runs don't overwrite earlier runs. (This doesn't appear to be a problem in practice, presumably because the last run is the big one.) Updates golang/go#45686 Change-Id: I538ca6bb88cc18f1eefe35d2db29a62e5190280e Reviewed-on: https://go-review.googlesource.com/c/tools/+/410697 Run-TryBot: Robert Findley <[email protected]> gopls-CI: kokoro <[email protected]> Reviewed-by: Robert Findley <[email protected]> TryBot-Result: Gopher Robot <[email protected]>

In preparation for making metadata immutable, move metadata-related fields to a new MetadataGraph type. Other than instantiating this type when cloning, this CL contains no functional changes. For golang/go#45686 Change-Id: I7ad29d1f331ba7e53dad3f012ad7ecdae4f7d4b7 Reviewed-on: https://go-review.googlesource.com/c/tools/+/340730 Run-TryBot: Robert Findley <[email protected]> gopls-CI: kokoro <[email protected]> Reviewed-by: Alan Donovan <[email protected]> TryBot-Result: Gopher Robot <[email protected]>

gopherbot · 2022-06-09T20:50:00Z

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

gopherbot · 2022-06-09T21:50:34Z

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

This change replaces the single large map used for snapshot.goFiles by a map of 256 stripes, each of which becomes immutable once shared. This optimizes the common case in which the copy is nearly identical to the original. We still need to visit each map entry to see whether it needs to be deleted (which is rare) and to inherit the handle in the usual case. This is now done concurrently. Also, share the (logically immutable) []PackageIDs slices across old and new snapshots. This was worth 5% of CPU and 1/3 of allocations (all small). Benchmark on darwin/arm64 shows a 29% reduction for DidChange. $ go test -v ./gopls/internal/regtest/bench -run=TestBenchmarkDidChange -didchange_dir=$HOME/w/kubernetes -didchange_file=pkg/util/hash/hash.go Before: BenchmarkStatistics 100 22955469 ns/op 11308095 B/op 47412 allocs/op BenchmarkStatistics 100 23454630 ns/op 11226742 B/op 46882 allocs/op BenchmarkStatistics 100 23618532 ns/op 11258619 B/op 47068 allocs/op After goFilesMap: BenchmarkStatistics 100 16643972 ns/op 8770787 B/op 46238 allocs/op BenchmarkStatistics 100 17805864 ns/op 8862926 B/op 46762 allocs/op BenchmarkStatistics 100 18618255 ns/op 9308864 B/op 49776 allocs/op After goFilesMap and ids sharing: BenchmarkStatistics 100 16703623 ns/op 8772626 B/op 33812 allocs/op BenchmarkStatistics 100 16927378 ns/op 8529491 B/op 32328 allocs/op BenchmarkStatistics 100 16632762 ns/op 8557533 B/op 32497 allocs/op Also: - Add comments documenting findings of profiling. - preallocate slice for knownSubdirs. - remove unwanted loop over slice in Generation.Inherit Updates golang/go#45686 Change-Id: Id953699191b8404cf36ba3a7ab9cd78b1d19c0a2 Reviewed-on: https://go-review.googlesource.com/c/tools/+/410176 TryBot-Result: Gopher Robot <[email protected]> Reviewed-by: Robert Findley <[email protected]> gopls-CI: kokoro <[email protected]> Run-TryBot: Alan Donovan <[email protected]>

gopherbot · 2022-06-15T23:37:47Z

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

Now that we preserve stale metadata, we can derive workspace packages entirely from known metadata and files. This consolidates the logic to compute workspace packages into a single location, which can be invoked whenever metadata changes (via load or invalidation in clone). Additionally: - Precompute 'HasWorkspaceFiles' when loading metadata. This value should never change for a given Metadata, and our view.contains func is actually quite slow due to evaluating symlinks. - Track 'PkgFilesChanged' on KnownMetadata, since we don't include packages whose package name has changed in our workspace. Also introduce a few debug helpers, so that we can leave some instrumentation in critical functions. For golang/go#45686 Change-Id: I2c994a1e8ca05c3c42f67bd2f4519bea5095c54c Reviewed-on: https://go-review.googlesource.com/c/tools/+/340735 Run-TryBot: Robert Findley <[email protected]> TryBot-Result: Gopher Robot <[email protected]> Reviewed-by: Alan Donovan <[email protected]> gopls-CI: kokoro <[email protected]>

Introduce a metadataGraph.Clone method that can be used to clone a metadata graph, applying a set of updates. During clone, ids and imports are recomputed from scratch based on the known metadata. Also refine the check for "real" packages when determining whether a command-line-arguments package should be kept as a workspace package: if all other packages are invalid, but the command-line-arguments package is valid, we should keep the command-line-arguments package. Updates golang/go#45686 Change-Id: Iea8d4f19c1d1c5a2b0582b9dda5f9143482a34af Reviewed-on: https://go-review.googlesource.com/c/tools/+/340851 Reviewed-by: Alan Donovan <[email protected]> TryBot-Result: Gopher Robot <[email protected]> gopls-CI: kokoro <[email protected]> Run-TryBot: Robert Findley <[email protected]>

Rather than updating metadata directly in snapshot.clone, build a set of updates to apply and call metadata.Clone. After this change, metadata is only updated by cloning, so we can eliminate some code that works with mutable metadata. In the next CL we'll only update the metadata if something changed, but this is intentionally left out of this CL to isolate the change. Benchmark (didChange in kubernetes): ~55ms->65ms, because it is now more work to compute uris. For golang/go#45686 Change-Id: I048bed65760b266a209f67111c57fae29bd3e6f0 Reviewed-on: https://go-review.googlesource.com/c/tools/+/340852 gopls-CI: kokoro <[email protected]> TryBot-Result: Gopher Robot <[email protected]> Run-TryBot: Robert Findley <[email protected]> Reviewed-by: Alan Donovan <[email protected]>

We with immutable metadata, we don't need to clone if nothing was invalidated. Benchmark (didChange in k8s): 65ms->45ms For golang/go#45686 Change-Id: I6b5e764c53a35784fd8c7b43bc26361f4ee8d928 Reviewed-on: https://go-review.googlesource.com/c/tools/+/340853 Run-TryBot: Robert Findley <[email protected]> Reviewed-by: Alan Donovan <[email protected]> gopls-CI: kokoro <[email protected]> TryBot-Result: Gopher Robot <[email protected]>

Since ids is derived from metadata, we should not have to walk ids to see which metadata is still active. Just compute metadata updates directly. Benchmark (didChange in k8s): ~45ms->41ms For golang/go#45686 Change-Id: Id557ed3f2e05c903e4bb3f3f6a4af864751c4546 Reviewed-on: https://go-review.googlesource.com/c/tools/+/340854 TryBot-Result: Gopher Robot <[email protected]> Run-TryBot: Robert Findley <[email protected]> Reviewed-by: Alan Donovan <[email protected]> gopls-CI: kokoro <[email protected]>

Now that the entire metadata graph and workspace packages are derived from metadata, there should be no need to validate coherency. This results in a small improvement to didChange benchmarking (within statistical noise). For golang/go#45686 Change-Id: I32683e025f42d768d62864683e55d4c00146a31c Reviewed-on: https://go-review.googlesource.com/c/tools/+/340855 TryBot-Result: Gopher Robot <[email protected]> gopls-CI: kokoro <[email protected]> Reviewed-by: Alan Donovan <[email protected]> Run-TryBot: Robert Findley <[email protected]>

…pshot Use treap (https://en.wikipedia.org/wiki/Treap) as a persistent map to avoid copying s.goFiles across generations. Maintain an additional s.parseKeysByURIMap to avoid scanning s.goFiles on individual file's content invalidation. This on average reduces didChange latency on internal codebase from 160ms to 150ms. In a followup the same approach can be generically extended to avoid copying s.files and s.packages. Updates golang/go#45686 Change-Id: Ic4a9b3c8fb2b66256f224adf9896ddcaaa6865b1 GitHub-Last-Rev: b211d6c GitHub-Pull-Request: golang#382

…pshot Use treap (https://en.wikipedia.org/wiki/Treap) as a persistent map to avoid copying s.goFiles across generations. Maintain an additional s.parseKeysByURIMap to avoid scanning s.goFiles on individual file's content invalidation. This on average reduces didChange latency on internal codebase from 160ms to 150ms. In a followup the same approach can be used to avoid copying s.files, s.packages, and s.knownSubdirs. Updates golang/go#45686 Change-Id: Ic4a9b3c8fb2b66256f224adf9896ddcaaa6865b1 GitHub-Last-Rev: 0abd257 GitHub-Pull-Request: #382 Reviewed-on: https://go-review.googlesource.com/c/tools/+/411554 Reviewed-by: Robert Findley <[email protected]> gopls-CI: kokoro <[email protected]> Reviewed-by: Alan Donovan <[email protected]> Run-TryBot: Robert Findley <[email protected]> TryBot-Result: Gopher Robot <[email protected]>

gopherbot · 2022-06-22T21:51:11Z

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

gopherbot · 2022-06-22T21:51:12Z

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

gopherbot · 2022-06-22T21:51:13Z

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

This on average reduces latency from 34ms to 25ms on internal codebase. Updates golang/go#45686 Change-Id: I57b05e5679620d8481b1f1a051645cf1cc00aca5 Reviewed-on: https://go-review.googlesource.com/c/tools/+/413654 TryBot-Result: Gopher Robot <[email protected]> Reviewed-by: Robert Findley <[email protected]> gopls-CI: kokoro <[email protected]> Reviewed-by: Alan Donovan <[email protected]> Run-TryBot: Alan Donovan <[email protected]>

findleyr · 2022-06-28T18:16:46Z

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 🎉

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).

…apshot This on average reduces latency from 25ms to 12ms on internal codebase. Updates golang/go#45686 Change-Id: I49c8f09f8e54b7b486d7ff7eb8f4ba9f0d90b278 Reviewed-on: https://go-review.googlesource.com/c/tools/+/413655 gopls-CI: kokoro <[email protected]> Run-TryBot: Robert Findley <[email protected]> TryBot-Result: Gopher Robot <[email protected]> Reviewed-by: Robert Findley <[email protected]> Reviewed-by: Alan Donovan <[email protected]>

This on average reduces latency from 12ms to 4ms on internal codebase. Updates golang/go#45686 Change-Id: Id376fcd97ce375210f2ad8b88e42f6ca283d29d3 Reviewed-on: https://go-review.googlesource.com/c/tools/+/413657 Reviewed-by: Robert Findley <[email protected]> Reviewed-by: Alan Donovan <[email protected]>

findleyr added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Apr 22, 2021

findleyr added this to the gopls/v1.0.0 milestone Apr 22, 2021

gopherbot added Tools This label describes issues relating to any tools in the x/tools repository. gopls Issues related to the Go language server, gopls. labels Apr 22, 2021

anton-kuklin mentioned this issue Apr 22, 2021

internal/lsp/cache: improve snapshot clone perfomance golang/tools#306

Closed

findleyr changed the title ~~x/tools/gopls: optimize snapshot cloning~~ x/tools/gopls: optimize didChange handling Apr 23, 2021

findleyr mentioned this issue May 5, 2021

x/tools/gopls: memoize allKnownSubdirs on the snapshot #45974

Closed

findleyr self-assigned this Aug 5, 2021

findleyr added this to the gopls/v0.9.0 milestone May 18, 2022

findleyr unassigned dle8 May 18, 2022

findleyr mentioned this issue Jun 8, 2022

x/tools/gopls: add ability to avoid scanning an entire workspace #53278

Closed

euroelessar mentioned this issue Jun 15, 2022

internal/lsp/cache: use persistent map for storing gofiles in the snapshot golang/tools#382

Closed

findleyr closed this as completed Jun 28, 2022

golang locked and limited conversation to collaborators Jun 28, 2023

gopherbot added the FrozenDueToAge label Jun 28, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

x/tools/gopls: optimize didChange handling #45686

x/tools/gopls: optimize didChange handling #45686

findleyr commented Apr 22, 2021

gopherbot commented Apr 22, 2021

anton-kuklin commented Apr 22, 2021

gopherbot commented Apr 22, 2021

findleyr commented Apr 23, 2021

anton-kuklin commented Apr 23, 2021

anton-kuklin commented Apr 23, 2021

findleyr commented Apr 25, 2021

gopherbot commented May 5, 2021

gopherbot commented May 25, 2021

stamblerre commented Jun 28, 2021

findleyr commented Jul 13, 2021

findleyr commented Aug 5, 2021

gopherbot commented Aug 11, 2021

gopherbot commented Aug 11, 2021

gopherbot commented Aug 11, 2021

gopherbot commented Jun 6, 2022

gopherbot commented Jun 9, 2022

gopherbot commented Jun 9, 2022

gopherbot commented Jun 15, 2022

gopherbot commented Jun 22, 2022

gopherbot commented Jun 22, 2022

gopherbot commented Jun 22, 2022

findleyr commented Jun 28, 2022

x/tools/gopls: optimize didChange handling #45686

x/tools/gopls: optimize didChange handling #45686

Comments

findleyr commented Apr 22, 2021

gopherbot commented Apr 22, 2021

anton-kuklin commented Apr 22, 2021

gopherbot commented Apr 22, 2021

findleyr commented Apr 23, 2021

anton-kuklin commented Apr 23, 2021

anton-kuklin commented Apr 23, 2021

findleyr commented Apr 25, 2021

gopherbot commented May 5, 2021

gopherbot commented May 25, 2021

stamblerre commented Jun 28, 2021

findleyr commented Jul 13, 2021

findleyr commented Aug 5, 2021

gopherbot commented Aug 11, 2021

gopherbot commented Aug 11, 2021

gopherbot commented Aug 11, 2021

gopherbot commented Jun 6, 2022

gopherbot commented Jun 9, 2022

gopherbot commented Jun 9, 2022

gopherbot commented Jun 15, 2022

gopherbot commented Jun 22, 2022

gopherbot commented Jun 22, 2022

gopherbot commented Jun 22, 2022

findleyr commented Jun 28, 2022