strings: optimize Count for amd64

Move optimized Count implementation from bytes to runtime. Use in
both bytes and strings packages.
Add CountByte benchmark to strings.

Strings benchmarks:
name                       old time/op    new time/op    delta
CountHard1-4                 226µs ± 1%      226µs ± 2%      ~     (p=0.247 n=10+10)
CountHard2-4                 316µs ± 1%      315µs ± 0%      ~     (p=0.133 n=9+10)
CountHard3-4                 919µs ± 1%      920µs ± 1%      ~     (p=0.968 n=10+9)
CountTorture-4              15.4µs ± 1%     15.7µs ± 1%    +2.47%  (p=0.000 n=10+9)
CountTortureOverlapping-4   9.60ms ± 0%     9.65ms ± 1%      ~     (p=0.247 n=10+10)
CountByte/10-4              26.3ns ± 1%     10.9ns ± 1%   -58.71%  (p=0.000 n=9+9)
CountByte/32-4              42.7ns ± 0%     14.2ns ± 0%   -66.64%  (p=0.000 n=10+10)
CountByte/4096-4            3.07µs ± 0%     0.31µs ± 2%   -89.99%  (p=0.000 n=9+10)
CountByte/4194304-4         3.48ms ± 1%     0.34ms ± 1%   -90.09%  (p=0.000 n=10+9)
CountByte/67108864-4        55.6ms ± 1%      7.0ms ± 0%   -87.49%  (p=0.000 n=9+8)

name                      old speed      new speed       delta
CountByte/10-4             380MB/s ± 1%    919MB/s ± 1%  +142.21%  (p=0.000 n=9+9)
CountByte/32-4             750MB/s ± 0%   2247MB/s ± 0%  +199.62%  (p=0.000 n=10+10)
CountByte/4096-4          1.33GB/s ± 0%  13.32GB/s ± 2%  +898.13%  (p=0.000 n=9+10)
CountByte/4194304-4       1.21GB/s ± 1%  12.17GB/s ± 1%  +908.87%  (p=0.000 n=10+9)
CountByte/67108864-4      1.21GB/s ± 1%   9.65GB/s ± 0%  +699.29%  (p=0.000 n=9+8)

Fixes #19411

Change-Id: I8d2d409f0fa6df6d03b60790aa86e540b4a4e3b0
Reviewed-on: https://go-review.googlesource.com/38693
Reviewed-by: Keith Randall <khr@golang.org>

5 files changed, 45 insertions, 5 deletions

diff --git a/src/strings/strings.go b/src/strings/strings.go
index a01eb698c4..d3bfe1f729 100644
--- a/src/strings/strings.go
+++ b/src/strings/strings.go
@@ -72,9 +72,8 @@ func hashStrRev(sep string) (uint32, uint32) {
 	return hash, pow
 }
 
-// Count counts the number of non-overlapping instances of substr in s.
-// If substr is an empty string, Count returns 1 + the number of Unicode code points in s.
-func Count(s, substr string) int {
+// countGeneric implements Count.
+func countGeneric(s, substr string) int {
 	// special case
 	if len(substr) == 0 {
 		return utf8.RuneCountInString(s) + 1
diff --git a/src/strings/strings_amd64.go b/src/strings/strings_amd64.go
index 8f6ac1de74..33771480a6 100644
--- a/src/strings/strings_amd64.go
+++ b/src/strings/strings_amd64.go
@@ -8,8 +8,10 @@ package strings
 
 // indexShortStr returns the index of the first instance of c in s, or -1 if c is not present in s.
 // indexShortStr requires 2 <= len(c) <= shortStringLen
-func indexShortStr(s, c string) int // ../runtime/asm_$GOARCH.s
-func supportAVX2() bool             // ../runtime/asm_$GOARCH.s
+func indexShortStr(s, c string) int  // ../runtime/asm_$GOARCH.s
+func supportAVX2() bool              // ../runtime/asm_$GOARCH.s
+func supportPOPCNT() bool            // ../runtime/asm_$GOARCH.s
+func countByte(s string, c byte) int // ../runtime/asm_$GOARCH.s
 
 var shortStringLen int
 
@@ -93,3 +95,12 @@ func Index(s, substr string) int {
 	}
 	return -1
 }
+
+// Count counts the number of non-overlapping instances of substr in s.
+// If substr is an empty string, Count returns 1 + the number of Unicode code points in s.
+func Count(s, substr string) int {
+	if len(substr) == 1 && supportPOPCNT() {
+		return countByte(s, byte(substr[0]))
+	}
+	return countGeneric(s, substr)
+}
diff --git a/src/strings/strings_generic.go b/src/strings/strings_generic.go
index 873d75ee1c..5429a74a22 100644
--- a/src/strings/strings_generic.go
+++ b/src/strings/strings_generic.go
@@ -45,3 +45,9 @@ func Index(s, substr string) int {
 	}
 	return -1
 }
+
+// Count counts the number of non-overlapping instances of substr in s.
+// If substr is an empty string, Count returns 1 + the number of Unicode code points in s.
+func Count(s, substr string) int {
+	return countGeneric(s, substr)
+}
diff --git a/src/strings/strings_s390x.go b/src/strings/strings_s390x.go
index 32520459be..ccf2da632d 100644
--- a/src/strings/strings_s390x.go
+++ b/src/strings/strings_s390x.go
@@ -96,3 +96,9 @@ func Index(s, substr string) int {
 	}
 	return -1
 }
+
+// Count counts the number of non-overlapping instances of substr in s.
+// If substr is an empty string, Count returns 1 + the number of Unicode code points in s.
+func Count(s, substr string) int {
+	return countGeneric(s, substr)
+}
diff --git a/src/strings/strings_test.go b/src/strings/strings_test.go
index 58314a6868..869be9c477 100644
--- a/src/strings/strings_test.go
+++ b/src/strings/strings_test.go
@@ -1457,6 +1457,24 @@ func BenchmarkCountTortureOverlapping(b *testing.B) {
 	}
 }
 
+func BenchmarkCountByte(b *testing.B) {
+	indexSizes := []int{10, 32, 4 << 10, 4 << 20, 64 << 20}
+	benchStr := Repeat(benchmarkString,
+		(indexSizes[len(indexSizes)-1]+len(benchmarkString)-1)/len(benchmarkString))
+	benchFunc := func(b *testing.B, benchStr string) {
+		b.SetBytes(int64(len(benchStr)))
+		for i := 0; i < b.N; i++ {
+			Count(benchStr, "=")
+		}
+	}
+	for _, size := range indexSizes {
+		b.Run(fmt.Sprintf("%d", size), func(b *testing.B) {
+			benchFunc(b, benchStr[:size])
+		})
+	}
+
+}
+
 var makeFieldsInput = func() string {
 	x := make([]byte, 1<<20)
 	// Input is ~10% space, ~10% 2-byte UTF-8, rest ASCII non-space.