bytes,strings: in generic Index, use mix of IndexByte and Rabin-Karp

Use IndexByte first, as it allows us to skip lots of bytes quickly.
If IndexByte is generating a lot of false positives, switch over to Rabin-Karp.

Experiments for ppc64le
bytes:
name                             old time/op  new time/op  delta
IndexPeriodic/IndexPeriodic2-2   1.12ms ± 0%  0.18ms ± 0%  -83.54%  (p=0.000 n=10+9)
IndexPeriodic/IndexPeriodic4-2    635µs ± 0%   184µs ± 0%  -71.06%  (p=0.000 n=9+9)
IndexPeriodic/IndexPeriodic8-2    289µs ± 0%   184µs ± 0%  -36.51%  (p=0.000 n=10+9)
IndexPeriodic/IndexPeriodic16-2   133µs ± 0%   183µs ± 0%  +37.68%  (p=0.000 n=10+9)
IndexPeriodic/IndexPeriodic32-2  68.3µs ± 0%  70.2µs ± 0%   +2.76%  (p=0.000 n=10+10)
IndexPeriodic/IndexPeriodic64-2  35.8µs ± 0%  36.6µs ± 0%   +2.17%  (p=0.000 n=8+10)

strings:
name                             old time/op  new time/op  delta
IndexPeriodic/IndexPeriodic2-2    184µs ± 0%   184µs ± 0%   +0.11%  (p=0.029 n=4+4)
IndexPeriodic/IndexPeriodic4-2    184µs ± 0%   184µs ± 0%     ~     (p=0.886 n=4+4)
IndexPeriodic/IndexPeriodic8-2    184µs ± 0%   184µs ± 0%     ~     (p=0.486 n=4+4)
IndexPeriodic/IndexPeriodic16-2   185µs ± 1%   184µs ± 0%     ~     (p=0.343 n=4+4)
IndexPeriodic/IndexPeriodic32-2   184µs ± 0%    69µs ± 0%  -62.37%  (p=0.029 n=4+4)
IndexPeriodic/IndexPeriodic64-2   184µs ± 0%    37µs ± 0%  -80.17%  (p=0.029 n=4+4)

Fixes #22578

Change-Id: If2a4d8554cb96bfd699b58149d13ac294615f8b8
Reviewed-on: https://go-review.googlesource.com/76070
Reviewed-by: Alberto Donizetti <alb.donizetti@gmail.com>

1 files changed, 23 insertions, 15 deletions

diff --git a/src/strings/strings_generic.go b/src/strings/strings_generic.go
index 5429a74a22..b2af48bec8 100644
--- a/src/strings/strings_generic.go
+++ b/src/strings/strings_generic.go
@@ -25,22 +25,30 @@ func Index(s, substr string) int {
 	case n > len(s):
 		return -1
 	}
-	// Rabin-Karp search
-	hashss, pow := hashStr(substr)
-	var h uint32
-	for i := 0; i < n; i++ {
-		h = h*primeRK + uint32(s[i])
-	}
-	if h == hashss && s[:n] == substr {
-		return 0
-	}
-	for i := n; i < len(s); {
-		h *= primeRK
-		h += uint32(s[i])
-		h -= pow * uint32(s[i-n])
+	c := substr[0]
+	i := 0
+	t := s[:len(s)-n+1]
+	fails := 0
+	for i < len(t) {
+		if t[i] != c {
+			o := IndexByte(t[i:], c)
+			if o < 0 {
+				return -1
+			}
+			i += o
+		}
+		if s[i:i+n] == substr {
+			return i
+		}
 		i++
-		if h == hashss && s[i-n:i] == substr {
-			return i - n
+		fails++
+		if fails >= 4+i>>4 && i < len(t) {
+			// See comment in ../bytes/bytes_generic.go.
+			j := indexRabinKarp(s[i:], substr)
+			if j < 0 {
+				return -1
+			}
+			return i + j
 		}
 	}
 	return -1