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

[greatroar]

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]

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

[zigo101]

related: #50167

[rhcarvalho]

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]

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.

[zigo101]

This is done for #61725

[ianlancetaylor]

Thanks for pointing that out.