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

Jump to bottom

strings, x/exp/slices: strings.Compare is more useful than its docs say, but also slow #58142

Closed
greatroar opened this issue Jan 30, 2023 · 6 comments
Closed

strings, x/exp/slices: strings.Compare is more useful than its docs say, but also slow #58142

greatroar opened this issue Jan 30, 2023 · 6 comments
Labels
Documentation NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone
Backlog

Comments

@greatroar
Copy link

What version of Go are you using (go version)?

go version devel go1.21-4f467f1082 Wed Jan 25 21:16:32 2023 +0000 linux/amd64

What did you do?

I benchmarked two binary searches on an array of strings:

sort.Search(len(strs), func(i int) bool { return key <= strs[i] })
slices.BinarySearchFunc(strs, key, strings.Compare)

Turns out the former can be significantly faster. Seeing how strings.Compare is implemented, I get why:

go/src/strings/compare.go

Lines 7 to 28 in d42c08a

// Compare returns an integer comparing two strings lexicographically.
// The result will be 0 if a == b, -1 if a < b, and +1 if a > b.
//
// Compare is included only for symmetry with package bytes.
// It is usually clearer and always faster to use the built-in
// string comparison operators ==, <, >, and so on.
func Compare(a, b string) int {
// NOTE(rsc): This function does NOT call the runtime cmpstring function,
// because we do not want to provide any performance justification for
// using strings.Compare. Basically no one should use strings.Compare.
// As the comment above says, it is here only for symmetry with package bytes.
// If performance is important, the compiler should be changed to recognize
// the pattern so that all code doing three-way comparisons, not just code
// using strings.Compare, can benefit.
if a == b {
return 0
}
if a < b {
return -1
}
return +1
}

Should the decision to not optimize strings.Compare be reconsidered? Even if not, should its comments be changed to not recommend against its use? Because it appears to me as the sane way to work with strings and x/exp/slices.
@mknyszek mknyszek added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jan 30, 2023
@mknyszek mknyszek added this to the Backlog milestone Jan 30, 2023
@mknyszek
Copy link
Contributor

CC @rsc who wrote the original note against optimizing strings.Compare, and @ianlancetaylor for x/exp/slices.

@go101
Copy link

go101 commented Jan 31, 2023

related: #50167

@go101 go101 mentioned this issue Aug 3, 2023
Closed
@rhcarvalho
Copy link
Contributor

With slices in the standard library as of Go 1.21, I noticed a few places in our code base where we use the new generic cmp.Compare function in places where strings.Compare would also work.

Since strings.Compare and cmp.Compare are similarly implemented, I would expect the two to have similar performance characteristics, inline with the note within the strings.Compare source code.

@ncruces
Copy link
Contributor

ncruces commented Sep 28, 2023

cmp.Compare will have worse performance for strings.

cmp.Compare is implemented in such a way that the comparisons necessary to place NaNs before all other numbers are optimized away for types that are not floats.

strings.Compare takes advantage of the fact that == is fast for strings of unequal length.

@go101
Copy link

go101 commented Apr 6, 2024

This is done for #61725

@ianlancetaylor
Copy link
Contributor

Thanks for pointing that out.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Documentation NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Milestone
Backlog
Development

No branches or pull requests
7 participants
@rhcarvalho @mknyszek @ianlancetaylor @ncruces @gopherbot @go101 @greatroar