code review 16070045: go.tools/go/types: use a map for cycle detection in IsI...

go.tools/go/types: use a map for cycle detection in IsIdentical

[gri, 2013-10-23 21:39:35]

Hello adonovan@google.com (cc: golang-dev@googlegroups.com), I'd like you to review this change to https://code.google.com/p/go.tools

[adonovan, 2013-10-23 21:45:13]

LGTM https://codereview.appspot.com/16070045/diff/50001/go/types/predicates.go File go/types/predicates.go (right): https://codereview.appspot.com/16070045/diff/50001/go/types/predicates.go#new... go/types/predicates.go:232: It would be even more efficient if you establish the invariant seen != nil, with seen pointing to a map reference, initially nil, in the frame of the toplevel caller. Then, the first time you need to execute: (*seen)[p] = true you first do: if *seen == nil { *seen = make(map[ifacePair]bool) } that way, if you encounter pairs of types descending one subtree, you don't throw them away and do them again when you encounter them again after backtracking and descending another subtree.

[gri, 2013-10-23 21:52:54]

https://codereview.appspot.com/16070045/diff/50001/go/types/predicates.go File go/types/predicates.go (right): https://codereview.appspot.com/16070045/diff/50001/go/types/predicates.go#new... go/types/predicates.go:232: On 2013/10/23 21:45:14, adonovan wrote: > It would be even more efficient if you establish the invariant seen != nil, with > seen pointing to a map reference, initially nil, in the frame of the toplevel > caller. > > Then, the first time you need to execute: > (*seen)[p] = true > you first do: > if *seen == nil { > *seen = make(map[ifacePair]bool) > } > that way, if you encounter pairs of types descending one subtree, you don't > throw them away and do them again when you encounter them again after > backtracking and descending another subtree. But it comes at the cost of an (implicit) heap allocation of an uninitialized map at the top for every call to IsIdentical. Maybe it doesn't matter. I will hold off with this CL for now. These are clearly esoteric cases.

[gobot, 2013-12-20 16:26:01]

Replacing golang-dev with golang-codereviews.

[gobot, 2014-12-19 05:14:35]

R=close To the author of this CL: The Go project has moved to Gerrit Code Review. If this CL should be continued, please see the latest version of https://golang.org/doc/contribute.html for instructions on how to set up Git and the Go project's Gerrit codereview plugin, and then create a new change with your current code. If there has been discussion on this CL, please give a link to it (golang.org/cl/16070045 is best) in the description in your new CL. Thanks very much.