go/types: slow type checking with thousands of methods on a type

[findleyr]

In a discussion of gopls performance issues on #66647, a user is reporting difficulty working in a package that has a very large (140K lines) amount of code gen. Tracing showed that type checking that package was taking 2s.

Looking at their profile, it seems that almost almost all the time is spent in the assignableTo predicate. I'm guessing that the generated code assigns a lot of values of the same type. I wonder if we should consider caching predicates during the type checking pass. In this case it appears that may reduce type checking by an order of magnitude. Would this be an overfit solution?

This project has quite a lot of generated code, yes (much to my dismay). Some of the generated files are quite large (almost 140k lines, lol), and there are a fair number of large dependencies in the project.

Here's the profile, let me know if you'd like me to run it again or for longer duration.

Trace profile checkPackage

File: gopls
Type: cpu
Time: Apr 5, 2024 at 10:13am (CDT)
Duration: 10.11s, Total samples = 11.82s (116.95%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top 50 -cum checkPackage
Active filters:
   focus=checkPackage
Showing nodes accounting for 4.70s, 39.76% of 11.82s total
Dropped 87 nodes (cum <= 0.06s)
Showing top 50 nodes out of 73
      flat  flat%   sum%        cum   cum%
         0     0%     0%      5.35s 45.26%  go/types.(*Checker).Files (inline)
         0     0%     0%      5.35s 45.26%  go/types.(*Checker).checkFiles
         0     0%     0%      5.35s 45.26%  go/types.(*Checker).funcBody
         0     0%     0%      5.35s 45.26%  go/types.(*Checker).funcDecl.func1
         0     0%     0%      5.35s 45.26%  go/types.(*Checker).processDelayed
     0.01s 0.085% 0.085%      5.35s 45.26%  go/types.(*Checker).stmt
         0     0% 0.085%      5.35s 45.26%  go/types.(*Checker).stmtList
         0     0% 0.085%      5.35s 45.26%  golang.org/x/sync/errgroup.(*Group).Go.func1
         0     0% 0.085%      5.35s 45.26%  golang.org/x/tools/gopls/internal/cache.(*Snapshot).forEachPackageInternal.func2
         0     0% 0.085%      5.35s 45.26%  golang.org/x/tools/gopls/internal/cache.(*typeCheckBatch).checkPackage
         0     0% 0.085%      5.35s 45.26%  golang.org/x/tools/gopls/internal/cache.(*typeCheckBatch).handleSyntaxPackage
         0     0% 0.085%      5.28s 44.67%  go/types.(*Checker).rawExpr
         0     0% 0.085%      5.27s 44.59%  go/types.(*Checker).exprInternal
         0     0% 0.085%      5.22s 44.16%  go/types.(*Checker).callExpr
         0     0% 0.085%      5.02s 42.47%  go/types.(*Checker).arguments
         0     0% 0.085%      4.98s 42.13%  go/types.(*Checker).assignment
         0     0% 0.085%      4.96s 41.96%  go/types.(*Checker).implements
     0.02s  0.17%  0.25%      4.96s 41.96%  go/types.(*Checker).missingMethod
         0     0%  0.25%      4.96s 41.96%  go/types.(*operand).assignableTo
     0.03s  0.25%  0.51%      4.85s 41.03%  go/types.lookupFieldOrMethodImpl
         0     0%  0.51%      3.62s 30.63%  go/types.(*Checker).multiExpr
         0     0%  0.51%      3.44s 29.10%  go/types.(*Checker).initVars
         0     0%  0.51%      3.35s 28.34%  go/types.(*Checker).shortVarDecl
     0.04s  0.34%  0.85%      2.54s 21.49%  runtime.growslice
     0.50s  4.23%  5.08%      2.36s 19.97%  runtime.mallocgc
     0.03s  0.25%  5.33%      1.93s 16.33%  go/types.(*Named).lookupMethod
     0.99s  8.38% 13.71%      1.93s 16.33%  go/types.lookupMethod
     1.83s 15.48% 29.19%      1.83s 15.48%  runtime.memclrNoHeapPointers
         0     0% 29.19%      1.18s  9.98%  go/types.(*Checker).expr
         0     0% 29.19%      0.97s  8.21%  go/types.(*Checker).unary
     0.88s  7.45% 36.63%      0.94s  7.95%  go/types.(*object).sameId
         0     0% 36.63%      0.91s  7.70%  runtime.(*mcache).nextFree
         0     0% 36.63%      0.91s  7.70%  runtime.(*mcache).refill
         0     0% 36.63%      0.91s  7.70%  runtime.(*mcentral).cacheSpan
         0     0% 36.63%      0.91s  7.70%  runtime.(*mcentral).grow
         0     0% 36.63%      0.89s  7.53%  runtime.(*mspan).initHeapBits
         0     0% 36.63%      0.77s  6.51%  go/types.(*Checker).simpleStmt (inline)
         0     0% 36.63%      0.76s  6.43%  go/types.concat (inline)
         0     0% 36.63%      0.29s  2.45%  go/types.(*Checker).assignVars
     0.25s  2.12% 38.75%      0.25s  2.12%  runtime.memmove
         0     0% 38.75%      0.20s  1.69%  go/types.(*Checker).rangeStmt
         0     0% 38.75%      0.17s  1.44%  go/types.consolidateMultiples
         0     0% 38.75%      0.16s  1.35%  go/types.(*Checker).genericExprList
     0.05s  0.42% 39.17%      0.14s  1.18%  go/types.(*comparer).identical
         0     0% 39.17%      0.14s  1.18%  go/types.Identical (partial-inline)
         0     0% 39.17%      0.14s  1.18%  go/types.lookupType
     0.07s  0.59% 39.76%      0.14s  1.18%  runtime.mapassign
         0     0% 39.76%      0.11s  0.93%  go/types.(*Checker).exprOrType
         0     0% 39.76%      0.11s  0.93%  runtime.newobject (partial-inline)
         0     0% 39.76%      0.09s  0.76%  go/types.(*Checker).selector

Originally posted by @jacobmischka in #66647 (comment)

[findleyr]

CC @adonovan @griesemer @mdempsky @timothy-king

I'm not sure if this is worth doing, unless we can prove that it has benefits in the common case. However, it may be worth some investigation.

@jacobmischka can you confirm that the codegen assigns a bunch of values of the same type?

[adonovan]

I suspect (without data) that most assignableTo operations are fast, and that the worst case only occurs when assigning a concrete type to an interface type of many methods. (It would help to know how many there are in your code). So it wouldn't make sense to memoize the entire operation, but only the slow path for large interfaces. We would also need a way to asynchronously clear the cache, as the elements could otherwise pin very large data structures indefinitely.

It would be nice to get a repro before we talk more about caching. The ideal solution is always to make the predicate fast enough that no cache is necessary.

[findleyr]

In the go/types benchmarks, assignableTo is ~1-2% of type checking time (ignoring imports) across a stratified collection of standard library packages. Not sure how much of that could be cached, but in any case this suggests that this optimization will probably not be very helpful for most packages.

I'll try to investigate more thoroughly at some point.

[jacobmischka]

This is the library we're using that I suspect is the issue: https://gqlgen.com/

It's a graphql server library which relies on codegen. I am skimming the generated files and I don't believe there are a lot of assignments of the same type, rather it seems like there's one very large struct type with a lot of instance methods. I don't see much uses of interfaces but I definitely could be missing it. We're going to try looking through suggestions in discussions for that package in particular and see if we can find a good work around. Splitting the one large file into multiple files in a sub-package didn't seem to help, unfortunately. Will try an entirely separate package if possible to see if that helps.

[findleyr]

It's a graphql server library which relies on codegen. I am skimming the generated files and I don't believe there are a lot of assignments of the same type, rather it seems like there's one very large struct type with a lot of instance methods. I don't see much uses of interfaces but I definitely could be missing it. We're going to try looking through suggestions in discussions for that package in particular and see if we can find a good work around. Splitting the one large file into multiple files in a sub-package didn't seem to help, unfortunately. Will try an entirely separate package if possible to see if that helps.

Thanks, that's interesting. Approximately how many methods are there?

Splitting into separate files may help for parsing, but won't help for type checking, which considers all package files. Moving to a different package will help, although if you then import that type with thousands of methods, you may pay a significant cost type checking code that uses it.

[jacobmischka]

Thanks, that's interesting. Approximately how many methods are there?

About 4500.

Moving to a different package will help, although if you then import that type with thousands of methods, you may pay a significant cost type checking code that uses it.

Yeah, I've realized/confirmed now that it's definitely packages that import the generated package that are slow and everything else is quite fast.

[findleyr]

Thanks. It sounds like a cache wouldn't really help much in this case, or in general, so I've retitled this issue to more generally describe the symptoms you observe. There still may be room for improvement in our lookupMethod algorithms.

[adonovan]

Thanks, that's interesting. Approximately how many methods are there?
About 4500.

While our tools could certainly do better, creating a type with this many methods (and then generating very large files file of assignability conversions) is likely to push a lot of algorithms into poor performance. I wonder how many of those methods are necessarily methods, and how many might be more neatly expressed as standalone functions with more focussed lists of parameters.

[griesemer]

This sounds to me like a possibly (implicit) quadratic algorithm because we look up methods sequentially. Keeping them in a map (or perhaps adding them to a map as a cache as needed) might help here.

[jacobmischka]

If it's helpful, as a note, some coworkers use goland and they don't experience the same issue.