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

Jump to bottom

go/types,cmd/compile/internal/types2: shared type expressions are evaluated once per variable #46208

Open
mdempsky opened this issue May 17, 2021 · 8 comments
Open

go/types,cmd/compile/internal/types2: shared type expressions are evaluated once per variable #46208

mdempsky opened this issue May 17, 2021 · 8 comments
Assignees
@griesemer
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FeatureRequest NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Milestone
Go1.23

Comments

@mdempsky
Copy link
Member

If a VarDecl has an explicit type expression, it will get evaluated once for each declared variable. So if you have a VarDecl like var x, y interface { M() } you end up with two different *types2.Interface objects.

I ran into this because I wanted to map all types2.Type objects (that appeared in source) back to some syntactic element, so my initial approach was to just walk the AST looking for type expressions and then using Info.Types[expr].Type to get the types2.Type object and insert them into a map[types2.Type]syntax.Expr map.

However, this approach missed some types, because of VarDecls with multiple variables and an explicit type expression.

I don't think this is strictly a violation of the types2 API (you're supposed to use types2.Identical), but I think it would be nice and less surprising if there was a 1:1 correspondance.

I assume this also affects go/types.

/cc @griesemer @findleyr
@mdempsky mdempsky added NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. FeatureRequest labels May 17, 2021
@mdempsky mdempsky added this to the Go1.18 milestone May 17, 2021
@findleyr
Copy link
Contributor

Indeed this affects both go/types and types2. Here's the relevant TODO:
https://cs.opensource.google/go/go/+/master:src/cmd/compile/internal/types2/decl.go;l=464;drc=a9705e157beb51574233e23cc2e2a412d4681a15

I think this could be done, but we should probably handle decls with init exprs as well, which IIRC would be a non-trivial refactoring.

@findleyr findleyr changed the title cmd/compile/internal/types2: VarDecl type expression gets evaluated once per variable go/types, cmd/compile/internal/types2: VarDecl type expression gets evaluated once per variable May 17, 2021
@findleyr findleyr changed the title go/types, cmd/compile/internal/types2: VarDecl type expression gets evaluated once per variable go/types,cmd/compile/internal/types2: VarDecl type expression gets evaluated once per variable May 17, 2021
@mdempsky mdempsky changed the title go/types,cmd/compile/internal/types2: VarDecl type expression gets evaluated once per variable go/types,cmd/compile/internal/types2: shared type expressions are evaluated once per variable May 18, 2021
@mdempsky
Copy link
Member Author

mdempsky commented May 18, 2021 •
edited

I discovered this issue also affects struct fields (struct { a, b T }) and function signatures (func(a, b T)).

It presumably in theory also affects constant declarations, but if a constant declaration includes an explicit type expression, then it must be a defined type. So they'll always have a unique types.Type instance (right?).

Edit: Disregard. It appears that the problem I ran into with structs and signatures is that types2 evaluates the field type expressions just once each, but cmd/compile was evaluating them multiple times.

@mdempsky
Copy link
Member Author

For fun, I created these two test cases:

package p

var x struct {
a, b, c, d, e, f, g, h struct {
a, b, c, d, e, f, g, h struct {
a, b, c, d, e, f, g, h struct {
a, b, c, d, e, f, g, h struct {
a, b, c, d, e, f, g, h struct {
a, b, c, d, e, f, g, h struct {
a, b, c, d, e, f, g, h struct {
a, b, c, d, e, f, g, h struct {
}}}}}}}}}

package p

import "unsafe"

var a, b, c, d, e, f, g, h [unsafe.Sizeof(func() {
var a, b, c, d, e, f, g, h [unsafe.Sizeof(func() {
var a, b, c, d, e, f, g, h [unsafe.Sizeof(func() {
var a, b, c, d, e, f, g, h [unsafe.Sizeof(func() {
var a, b, c, d, e, f, g, h [unsafe.Sizeof(func() {
var a, b, c, d, e, f, g, h [unsafe.Sizeof(func() {
var a, b, c, d, e, f, g, h [unsafe.Sizeof(func() {
})]byte; b, c, d, e, f, g, h, a = a, b, c, d, e, f, g, h
})]byte; b, c, d, e, f, g, h, a = a, b, c, d, e, f, g, h
})]byte; b, c, d, e, f, g, h, a = a, b, c, d, e, f, g, h
})]byte; b, c, d, e, f, g, h, a = a, b, c, d, e, f, g, h
})]byte; b, c, d, e, f, g, h, a = a, b, c, d, e, f, g, h
})]byte; b, c, d, e, f, g, h, a = a, b, c, d, e, f, g, h
})]byte

cmd/compile and gccgo both appear to go exponential on the first test. go/types handles it instantly.

cmd/compile handles the second one instantly. gccgo and go/types take somewhat longer, but still complete within a few seconds. (To be fair to gccgo, I'm running it from a network file system, and it takes a few seconds to compile even a file with just package p.)

I tried a few more minor variations on the idea, but couldn't figure out a way to make go/types go exponential.

@gopherbot
Copy link

Change https://golang.org/cl/320789 mentions this issue: [dev.typeparams] cmd/compile: avoid some redundant type construction

mdempsky added a commit to mdempsky/go that referenced this issue May 24, 2021
@mdempsky
[dev.typeparams] cmd/compile: avoid some redundant type construction
6ed7044 
This CL updates noder and typecheck to avoid a couple instances of
redundant evaluation of type expressions:

1. When noding struct fields or parameter tuples, check for
syntax.Type reuse between adjacent fields and then reuse the
corresponding ir.Node type expression. It would perhaps be even better
to avoid re-noding the type expression too, but noder's days are
numbered anyway, so I'd rather be minimally invasive here.

2. When importing an empty interface, reuse the same cached empty
interface instance that is used for empty interfaces that appear in
source. This matches types2's behavior, which uses a single
types2.Interface instance for all empty interfaces.

These changes are motivated by making it possible to migrate from
typecheck to types2 while passing toolstash -cmp.

Updates golang#46208.

Change-Id: Ia6458894494464d863181db356f3284630c90ffe
mdempsky added a commit to mdempsky/go that referenced this issue May 24, 2021
@mdempsky
[dev.typeparams] cmd/compile: avoid some redundant type construction
a8814bc 
This CL updates noder and typecheck to avoid a couple instances of
redundant evaluation of type expressions:

1. When noding struct fields or parameter tuples, check for
syntax.Type reuse between adjacent fields and then reuse the
corresponding ir.Node type expression. It would perhaps be even better
to avoid re-noding the type expression too, but noder's days are
numbered anyway, so I'd rather be minimally invasive here.

2. When importing an empty interface, reuse the same cached empty
interface instance that is used for empty interfaces that appear in
source. This matches types2's behavior, which uses a single
types2.Interface instance for all empty interfaces.

These changes are motivated by making it possible to migrate from
typecheck to types2 while passing toolstash -cmp.

Updates golang#46208.

Change-Id: Ia6458894494464d863181db356f3284630c90ffe
gopherbot pushed a commit that referenced this issue May 26, 2021
@mdempsky
[dev.typeparams] cmd/compile: avoid some redundant type construction
95748d1 
This CL updates noder and typecheck to avoid a couple of instances of
redundant evaluation of type expressions:

1. When noding struct fields or parameter tuples, check for
syntax.Type reuse between adjacent fields and then reuse the
corresponding ir.Node type expression. It would perhaps be even better
to avoid re-noding the type expression too, but noder's days are
numbered anyway, so I'd rather be minimally invasive here.

2. When importing an empty interface, reuse the same cached empty
interface instance that is used for empty interfaces that appear in
source. This matches types2's behavior, which uses a single
types2.Interface instance for all empty interfaces.

These changes are motivated by making it possible to migrate from
typecheck to types2 while passing toolstash -cmp.

Updates #46208.

Change-Id: Ia6458894494464d863181db356f3284630c90ffe
Reviewed-on: https://go-review.googlesource.com/c/go/+/320789
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
Trust: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
@ianlancetaylor
Copy link
Contributor

@mdempsky This is in the 1.18 milestone; time to move to 1.19? Thanks.

@mdempsky mdempsky modified the milestones: Go1.18, Go1.19 Jan 28, 2022
@ianlancetaylor
Copy link
Contributor

@mdempsky This is in the 1.19 milestone; time to move to 1.20? Or Backlog? Thanks.

@griesemer
Copy link
Contributor

Too late for 1.19. But we should probably look into this. Moving to 1.20.

@griesemer griesemer modified the milestones: Go1.19, Go1.20 Jun 24, 2022
@griesemer griesemer self-assigned this Jun 24, 2022
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
@findleyr findleyr modified the milestones: Go1.20, Go1.21 Nov 10, 2022
@griesemer griesemer modified the milestones: Go1.21, Go1.22 Jun 1, 2023
@griesemer
Copy link
Contributor

Too late for 1.22.

@griesemer griesemer modified the milestones: Go1.22, Go1.23 Nov 30, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@griesemer griesemer

Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FeatureRequest NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Projects
Go Compiler / Runtime
Status: Triage Backlog
Release Status & Release Blockers
Status: No status
Milestone
Go1.23
Development

No branches or pull requests
5 participants
@mdempsky @ianlancetaylor @griesemer @gopherbot @findleyr