Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

x/tools/gopls: optimize didChange handling #45686

Open
findleyr opened this issue Apr 22, 2021 · 18 comments
Open

x/tools/gopls: optimize didChange handling #45686

findleyr opened this issue Apr 22, 2021 · 18 comments

Comments

@findleyr
Copy link
Contributor

@findleyr findleyr commented Apr 22, 2021

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
Copy link

@gopherbot gopherbot commented Apr 22, 2021

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

Loading

@justplesh
Copy link
Contributor

@justplesh justplesh commented Apr 22, 2021

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

Loading

justplesh added a commit to justplesh/tools that referenced this issue Apr 22, 2021
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
Copy link

@gopherbot gopherbot commented Apr 22, 2021

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

Loading

justplesh added a commit to justplesh/tools that referenced this issue Apr 22, 2021
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 findleyr changed the title x/tools/gopls: optimize snapshot cloning x/tools/gopls: optimize didChange handling Apr 23, 2021
@findleyr
Copy link
Contributor Author

@findleyr findleyr commented Apr 23, 2021

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.

Loading

@justplesh
Copy link
Contributor

@justplesh justplesh commented Apr 23, 2021

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

Loading

@justplesh
Copy link
Contributor

@justplesh justplesh commented Apr 23, 2021

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

Loading

gopherbot pushed a commit to golang/tools that referenced this issue Apr 23, 2021
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 <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Rebecca Stambler <rstambler@golang.org>
@findleyr
Copy link
Contributor Author

@findleyr findleyr commented Apr 25, 2021

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

Loading

gopherbot pushed a commit to golang/tools that referenced this issue Apr 26, 2021
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 <rstambler@golang.org>
Trust: Rebecca Stambler <rstambler@golang.org>
Trust: Suzy Mueller <suzmue@golang.org>
Run-TryBot: Rebecca Stambler <rstambler@golang.org>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
@gopherbot
Copy link

@gopherbot gopherbot commented May 5, 2021

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

Loading

gopherbot pushed a commit to golang/tools that referenced this issue May 6, 2021
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 <rfindley@google.com>
Run-TryBot: Robert Findley <rfindley@google.com>
gopls-CI: kokoro <noreply+kokoro@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Rebecca Stambler <rstambler@golang.org>
@gopherbot
Copy link

@gopherbot gopherbot commented May 25, 2021

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

Loading

gopherbot pushed a commit to golang/tools that referenced this issue Jun 4, 2021
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 <rstambler@golang.org>
Run-TryBot: Rebecca Stambler <rstambler@golang.org>
gopls-CI: kokoro <noreply+kokoro@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
@stamblerre
Copy link

@stamblerre stamblerre commented Jun 28, 2021

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

Loading

@findleyr
Copy link
Contributor Author

@findleyr findleyr commented Jul 13, 2021

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.

Loading

@stamblerre stamblerre added this to To Do in gopls on-deck Jul 15, 2021
@findleyr findleyr self-assigned this Aug 5, 2021
@findleyr
Copy link
Contributor Author

@findleyr findleyr commented Aug 5, 2021

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.

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Aug 11, 2021

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

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Aug 11, 2021

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

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Aug 11, 2021

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

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Aug 11, 2021

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

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Aug 11, 2021

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

Loading

@gopherbot
Copy link

@gopherbot gopherbot commented Aug 11, 2021

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

Loading

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants