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

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

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

Comments

@mdempsky
Copy link
Member

@mdempsky mdempsky commented May 17, 2021

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

@findleyr
Copy link
Contributor

@findleyr findleyr commented May 17, 2021

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 mdempsky commented May 18, 2021

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

@mdempsky mdempsky commented May 18, 2021

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

@gopherbot gopherbot commented May 18, 2021

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
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
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
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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
3 participants