go/token: FileSet.AddExistingFiles is quadratic [freeze exception]

[adonovan]

The new FileSet.AddExistingFiles method is quadratic when called repeatedly (as intended), and this is a serious performance problem in gopls that cannot be fixed within gopls, since it cannot change the representation of FileSet. A performance problem of this magnitude is properly considered a bug. (My bug, but still.)

https://go.dev/cl/675736 is a fix: instead of a (repeatedly) sorted array of files, we use a tree. It's 1000x faster on the benchmark that most closely models the problematic case. I propose to merge it into go1.25.

@golang/release

[gabyhelp]

Related Issues

• go/token: AddFile induces heavy contention in parallel parsing [freeze exception] #53507 (closed)
• go/token: add (*FileSet).AddExistingFiles method to add files out of order #73205

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[findleyr]

For logistical reasons related to x/tools (because gopls currently pokes unsafe holes into the FileSet), we'd need to hold this change in representation until gopls can use the new (albeit slow) token.AddExistingFiles implementation.

Unfortunately, this means we also need to wait for the Google import of the Go toolchain to have https://go.dev/cl/672875, because Go and x/tools are imported into Google independently, and we want to avoid a version skew scenario where x/tools is unimportable because it is incompatible with the current Google toolchain.

But luckily, we do a toolchain import to Google pretty frequently, so this may be possible as early as late next week, provided we're all comfortable with this plan and the freeze exception is approved.

[mknyszek]

In the weekly release meeting, we don't think this needs a freeze exception. It's fixing a serious performance problem in a new feature that gopls already depends on it. That being said, approved.