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: introduce masked memeq #41774

Open
josharian opened this issue Oct 3, 2020 · 0 comments
Open

cmd/compile: introduce masked memeq #41774

josharian opened this issue Oct 3, 2020 · 0 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone

Comments

@josharian
Copy link
Contributor

josharian commented Oct 3, 2020

This is an idea to experiment with. I don't know whether it'll yield enough fruit to be worth the added code.

Consider this type:

type T struct {
	x uint64
	b bool
}

Arrays of T require generated alg routines. This is because x has a required alignment of 8, so there's a 7 byte gap between Ts in the array, so we can't use one big memeq call.

We could, however, introduce a masked memeq, to which the compiler passes not only the length of the memory to compare but also a repeating mask, probably of a fixed size. For T, the mask would be something like 1111111110000000 (nine 1s, seven 0s). When comparing memory the routine would load bytes from memory, mask out some of the bytes, and then do the comparison. This is the kind of thing that SIMD instructions excel at on many platforms.

This would also work for structs containing blank fields (fields named _).

This could also work for hash routines: Mask out bytes before feeding them to the regular hash routine.

We could also use this as the first step in other alg routines. For example, [8]string's equality function could start by calling memeqmask with a size of 8*8*2 (on 64 bit systems) and a mask of 1111111100000000 (eight 1s, eight 0s), to compare all the lengths. Then it could do its second loop to compare all the contents.

cc @martisch @randall77

@josharian josharian added this to the Unplanned milestone Oct 3, 2020
@dmitshur dmitshur added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Oct 13, 2020
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
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. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Development

No branches or pull requests

3 participants