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

cmd/compile: optimize map[T]bool set for the same code performance as map[T]struct{} set #64204

Closed
qiulaidongfeng opened this issue Nov 16, 2023 · 3 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime.

Comments

@qiulaidongfeng
Copy link
Member

See CL 541218 , map[T]bool set has the same function as map[T]struct{} set, and the standard library also has the use of map[T]bool set, but map[T]bool set has more memory allocation and worse performance, which is evidence to support compiler optimization of map[T]bool set.

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Nov 16, 2023
@qiulaidongfeng
Copy link
Member Author

@gopherbot, please remove label Proposal.

@mpx
Copy link
Contributor

mpx commented Nov 16, 2023

map[T]bool provides 3 states: missing, present-true, present-false.
map[T]struct{} only provides: missing, present

Hence they aren't equivalent and map[T]struct{} can't be used as a general replacement.

It might be possible to analyse non-exported code to prove that only the missing and present-true states are needed an the apply an optimisation. I'm not convinced it's worth it.

I suspect code will generally improve when Go provides a common Set[T] type - if it's more convenient than map[T]bool it is more likely to be used when it matters.

@mknyszek
Copy link
Contributor

Right, map[T]bool can contain boolean values that have nothing to do with map presence. The compiler would have to pattern-match and validate that all uses of the map conform to the following pattern:

x := make(map[T]bool)
...
x[t] = true
...
present := x[t]

I think that's difficult to do in general, though perhaps feasible within a package. It seems like an awfully specific thing to pattern-match for, though. A generic Set wrapper seems like possibly a better path forward here. (See #47331.)

Closing this issue for now, but perhaps someone from @golang/compiler wants to chime in.

@mknyszek mknyszek closed this as not planned Won't fix, can't repro, duplicate, stale Nov 20, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime.
Projects
None yet
Development

No branches or pull requests

4 participants