strings: intrinsify and optimize Compare

slices.SortFunc requires a three-way comparison and we need an
efficient strings.Compare to perform three-way string comparisons.
This new implementation adds bytealg.CompareString as a wrapper of
runtime_cmpstring and changes Compare to use bytealg.CompareString.

The new implementation of Compare with runtime_cmpstring is about
28% faster than the previous one.

Fixes #61725

                           │ /tmp/gobench-sort-cmp.txt │    /tmp/gobench-sort-strings.txt    │
                           │          sec/op           │   sec/op     vs base                │
SortFuncStruct/Size16-48                   918.8n ± 1%   726.6n ± 0%  -20.92% (p=0.000 n=10)
SortFuncStruct/Size32-48                   2.666µ ± 1%   2.003µ ± 1%  -24.85% (p=0.000 n=10)
SortFuncStruct/Size64-48                   1.934µ ± 1%   1.331µ ± 1%  -31.22% (p=0.000 n=10)
SortFuncStruct/Size128-48                  3.560µ ± 1%   2.423µ ± 0%  -31.94% (p=0.000 n=10)
SortFuncStruct/Size512-48                 13.019µ ± 0%   9.071µ ± 0%  -30.33% (p=0.000 n=10)
SortFuncStruct/Size1024-48                 25.61µ ± 0%   17.75µ ± 0%  -30.70% (p=0.000 n=10)
geomean                                    4.217µ        3.018µ       -28.44%

Change-Id: I2513b6f8c1b9b273ef2d23f0a86f691e2d097eb6
Reviewed-on: https://go-review.googlesource.com/c/go/+/532195
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Ian Lance Taylor <iant@golang.org>
Reviewed-by: qiu laidongfeng2 <2645477756@qq.com>
Reviewed-by: Keith Randall <khr@google.com>

1 files changed, 6 insertions, 17 deletions

diff --git a/src/strings/compare.go b/src/strings/compare.go
index 2bd4a243db..b3c01fddc1 100644
--- a/src/strings/compare.go
+++ b/src/strings/compare.go
@@ -4,25 +4,14 @@
 
 package strings
 
+import "internal/bytealg"
+
 // 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.
+// Use Compare when you need to perform a three-way comparison (with
+// slices.SortFunc, for example). 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
+	return bytealg.CompareString(a, b)
 }