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: add variable length [N]T algs, for T in {string, float32, float64, iface} #41776

josharian opened this issue Oct 4, 2020 · 5 comments


Copy link

@josharian josharian commented Oct 4, 2020

See discussion in for more discussion.

I threw together a very crude prototype in to start playing with it. It has many obvious flaws and todos (I didn't even bother fixing typos), but it might be helpful for someone wanting to work on this.

cc @randall77 @martisch

@josharian josharian added Suggested help wanted binary-size labels Oct 4, 2020
@josharian josharian added this to the Unplanned milestone Oct 4, 2020
Copy link

@martisch martisch commented Oct 4, 2020

For string hashes the direction looks a lot like what I had in mind with an early working version of which wasn’t liked back then when send for review.

The new scope seems to be broader and generate wrappers for specific lengths on demand to deduce them but the direction of thought seems basically the same.

I’m happy to rework algs generation in that direction again by continuing the original intent of my CL linked above (and taking improvements from josh into account) into a new cl with more types and generating wrappers for specific lengths on demand to dedupe.

With Register based calling convention the additional call needed will also be cheaper so could be a better binary size and speed tradeoff.

For discussion of general approach: To generate code inside other types algs wont using a direct call to a type array alg with additional length argument be better then a closure?

Copy link
Contributor Author

@josharian josharian commented Oct 4, 2020

On the larger question of direction, I guess let's let @randall77 weigh in.

To generate code inside other types algs wont using a direct call to a type array alg with additional length argument be better then a closure?

Definitely. The CL I linked is missing that and more, like the optimization to check all string lengths before checking any of their contents, and calling bytealg.Equal directly to compare contents.

Copy link

@randall77 randall77 commented Oct 4, 2020

Using a helper in runtime for arrays of common types seems fine. I think the objection in CL 148177 is that there were 2 changes, doing the previous sentence, and manually inlining strhash. It would be nice to split those up into 2 separate CLs so we can see the effect of each individually.

We'll still need to use a closure for functions which will be directly assigned to runtime._type.equal or runtime.maptype.hasher.

You've probably already seen this, but note the one possible complication for these optimizations is that for hashes, any optimized hashing needs to still match runtime.typehash exactly. See #37716.

@martisch martisch self-assigned this Oct 6, 2020
@martisch martisch removed Suggested help wanted labels Oct 6, 2020
Copy link

@martisch martisch commented Oct 13, 2020

Algs generally seem to be a good part of the compiler/runtime where more can be done. I will focus on them again (assigned this issue to me) and besides general cleanup and refactoring will look into:

  • introducing functions processing arrays (also multiple struct fields) of hashes and equals (this issue)
  • replacing use of strhash with memhash (will be easier for array algs and already done for equals)
  • dereferencing types that wrap simple types e.g. [1]string and struct { string } into just the field type for hashes and equals. This avoids building or calling an extra alg function for single element arrays. single element arrays may come up in creation of backing arrays used for initialization of slice values.

I refactor my earlier to take into account other improvements here and split out the dereferencing part.

After the above I think we can see whats left on the table and potentialy also look into masked memequals as a general concept to be used in the runtime/compiler: #41774

Copy link

@martisch martisch commented Aug 23, 2021

This issue has not been forgotten and is back on my list to be tackled for go1.18. Working on updating and syncing my existing CLs to HEAD.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
None yet

No branches or pull requests

3 participants