Repository: go
Issue: go/types: slow type checking with thousands of methods on a type
Labels: Performance,NeedsInvestigation

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.

<details>
<summary> Trace profile checkPackage </summary>

<pre>
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
</pre>
</details>

_Originally posted by @jacobmischka in https://github.com/golang/go/issues/66647#issuecomment-2040075084_