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

runtime: map[int64]struct{} requires 16 bytes per slot #71368

Open
prattmic opened this issue Jan 21, 2025 · 5 comments
Open

runtime: map[int64]struct{} requires 16 bytes per slot #71368

prattmic opened this issue Jan 21, 2025 · 5 comments
Labels
BugReport Issues describing a possible bug in the Go implementation. compiler/runtime Issues related to the Go compiler and/or runtime. NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. Performance
Milestone

Comments

@prattmic
Copy link
Member

With swissmaps in 1.24, a map[int64]struct{} requires 16 bytes of space per slot, rather than the expected 8 bytes.

This is an unfortunate side effect of the way the storage is defined internally https://cs.opensource.google/go/go/+/master:src/cmd/compile/internal/reflectdata/map_swiss.go;l=30

	// type group struct {
	//     ctrl uint64
	//     slots [abi.SwissMapGroupSlots]struct {
	//         key  keyType
	//         elem elemType
	//     }
	// }

elemType is struct{}. The struct size rules in the compiler say that if struct ends in a zero-size type, that field is given 1 byte of space (in case someone creates a pointer to the last field, we don't want that to point past the end of allocation).
Then, keyType needs 8-byte alignment, so the last field actually ends up using a full 8-bytes.

This is the most extreme case of KVKVKVKV wasting space due to alignment requirements. We could probably fix this specific case by deconstructing the array+struct in this internal definition, then we'd only need the extra 8 bytes for the last slot.

Note that #70835 considers changing the layout entirely (putting all keys together), which would also fix this.

@prattmic prattmic added compiler/runtime Issues related to the Go compiler and/or runtime. NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. labels Jan 21, 2025
@prattmic prattmic added this to the Go1.25 milestone Jan 21, 2025
@gabyhelp gabyhelp added the BugReport Issues describing a possible bug in the Go implementation. label Jan 21, 2025
@thediveo
Copy link
Contributor

Is this basically "as bad" as the also common map[X]bool, where the bool actually isn't used but just because is easier to type/read than struct{}?

@prattmic
Copy link
Member Author

Yes, both now allocate exactly the same amount of memory.

@zigo101
Copy link

zigo101 commented Jan 22, 2025

Will

struct {
	elem elemType
	key  keyType
}

fix this?

@valyala
Copy link
Contributor

valyala commented Jan 24, 2025

This may be the reason of performance drop for map[uint64]struct{} maps with millions of items when migrating from Go1.23 to Go1.24 - https://x.com/valyala/status/1879988053076504761

@jub0bs
Copy link

jub0bs commented Jan 24, 2025

Relevant discussion on Gophers Slack: https://gophers.slack.com/archives/C0VP8EF3R/p1737383438473369

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
BugReport Issues describing a possible bug in the Go implementation. compiler/runtime Issues related to the Go compiler and/or runtime. NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. Performance
Projects
Development

No branches or pull requests

6 participants