From fd999fda5941f215ef082c6ef70e44e648db5485 Mon Sep 17 00:00:00 2001 From: Emma Haruka Iwao Date: Mon, 2 Oct 2023 17:32:28 +0000 Subject: strings: intrinsify and optimize Compare MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 Reviewed-by: Ian Lance Taylor LUCI-TryBot-Result: Go LUCI Auto-Submit: Ian Lance Taylor Reviewed-by: qiu laidongfeng2 <2645477756@qq.com> Reviewed-by: Keith Randall --- src/strings/compare.go | 23 ++++++----------------- 1 file changed, 6 insertions(+), 17 deletions(-) (limited to 'src/strings') 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) } -- cgit v1.3