x/tools/internal/gopathwalk: regression in module cache scan performance

[findleyr]

As described in the discussion of https://go.dev/cl/508506, simplifying gopathwalk to use filepath.WalkDir had the unfortunate consequence of significantly slowing performance when starting from a cold module cache, as would be the case when running goimports from the command line. This is also very noticeable when gopls is initially started. On my laptop, with a 19GB module cache, warming up goimports went from ~6s to ~30s.

Because this latency was already a concern for gopls (see #44863), I don't think we can afford such a significant regression. With that said, the regression is probably possible to mitigate with alternative concurrency strategies. A benchmark is added in https://go.dev/cl/561436 which we can use for revisiting the simplification. For now, I think we need to temporarily revert CL 508506.

CC @bcmills

[gopherbot]

Change https://go.dev/cl/561655 mentions this issue: Revert "internal/gopathwalk: use filepath.WalkDir instead of internal/fastwalk"

[gopherbot]

Change https://go.dev/cl/561675 mentions this issue: internal/gopathwalk: walk directories concurrently

[findleyr]

A comparison of reverting vs fixing forward, in a relatively stable development environment. For lack of better names, "fastwalk.txt" is the revert, and "bryan.txt" is the fix forward :).

goarch: amd64
pkg: golang.org/x/tools/internal/imports
cpu: AMD EPYC 7B12
                              │ fastwalk.txt │              bryan.txt              │
                              │    sec/op    │   sec/op     vs base                │
ModuleResolver_InitialScan-48    366.0m ± 5%   403.2m ± 1%  +10.17% (p=0.000 n=20)

Limiting concurrency of the fix forward to 4 (the nominal concurrency limit of fastwalk), and results were noticeably worse:

goarch: amd64
pkg: golang.org/x/tools/internal/imports
cpu: AMD EPYC 7B12
                              │ fastwalk.txt │     bryan-limitconcurrency.txt      │
                              │    sec/op    │   sec/op     vs base                │
ModuleResolver_InitialScan-48    366.0m ± 5%   698.0m ± 2%  +90.72% (p=0.000 n=20)

However, CPU profiling indicated that the fix forward only uses 25% more CPU than fastwalk, so we can perhaps just say this is due to differences in scheduling, and run with the default concurrency of GOMAXPROCS.

Notably, the fix forward is still 4x faster than the non-concurrent implementation:

goos: linux
goarch: amd64
pkg: golang.org/x/tools/internal/imports
cpu: AMD EPYC 7B12
                              │  before.txt  │              bryan.txt              │
                              │    sec/op    │   sec/op     vs base                │
ModuleResolver_InitialScan-48   1620.8m ± 2%   403.2m ± 1%  -75.13% (p=0.000 n=20)

Therefore, I think we should fix forward. I'd rather get this fix into the gopls prerelease, so that it can get some exposure.

[bcmills]

Limiting concurrency of the fix forward to 4 (the nominal concurrency limit of fastwalk), and results were noticeably worse

Ah, turns out that I misread the old code. 4 goroutines was the minimum; runtime.NumCPU() was the old default. (But runtime.GOMAXPROCS(0) seems like a better maximum, since the user may intentionally decrease that to prevent tools like gopls from oversaturating their system.)

[findleyr]

Ah, turns out that I misread the old code. 4 goroutines was the minimum; runtime.NumCPU() was the old default. (But runtime.GOMAXPROCS(0) seems like a better maximum, since the user may intentionally decrease that to prevent tools like gopls from oversaturating their system.)

Oh, I misread it too! Then everything makes sense.