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 three-way string comparisons #31187

Open
ashi009 opened this issue Apr 1, 2019 · 4 comments
Open

cmd/compile: Optimize three-way string comparisons #31187

ashi009 opened this issue Apr 1, 2019 · 4 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

@ashi009
Copy link

ashi009 commented Apr 1, 2019

As shown in strings.Compare's source code, three-way string comparisons can be optimized.

A few use cases are:

  • sorted slice merging
  • sorted slice intersection
  • sorted slice intersection detection

For the last use case my benchmark showed a over 10% improvement by using bytes.Compare instaed of strings.Compare.

@josharian josharian added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Apr 1, 2019
@agnivade
Copy link
Contributor

agnivade commented Apr 1, 2019

@rsc

@randall77
Copy link
Contributor

Currently we break string comparison ops into runtime calls during walk.
If we delayed that lowering until later in SSA, we could maybe detect the use of both s1 == s2 and s1 < s2 and use a single call in that case.

@randall77 randall77 added this to the Unplanned milestone Apr 1, 2019
@josharian
Copy link
Contributor

This would be another possible use for an rtcall SSA pass: #24926

But it’d be better indeed to leave these unlowered until much later. Which would require making it reasonable to manipulate and insert calls in SSA. Which is yet another reason to move parameter and result handling into ssa ops instead of SP writes and reads. (I’m pretty sure I’ve written this paragraph a dozen times. I should just go do it.)

@josharian josharian changed the title Optimize three-way string comparisons cmd/compile: Optimize three-way string comparisons Apr 1, 2019
@dsymonds
Copy link
Contributor

dsymonds commented May 11, 2020

This would also be nice so that strings.Compare can have that rsc comment removed entirely, since it can be clearer to use it instead of the builtin operators in some cases, such as building a higher level comparison func.

type key struct {
  f1, f2, f3 string
}

func (k key) Compare(o key) int {
  if c := strings.Compare(k.f1, o.f1); c != 0 {
    return c
  }
  if c := strings.Compare(k.f2, o.f2); c != 0 {
    return c
  }
  if c := strings.Compare(k.f3, o.f3); c != 0 {
    return c
  }
  return 0
}

I mean, I could always implement my own strCompare helper func if strings.Compare didn't exist, but this optimisation would merely apply to that instead of strings.Compare.

@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

6 participants