bytes: faster Count, Index, Equal

Benchmarks are from GOARCH=amd64 on a MacPro5,1.

benchmark                                    old MB/s     new MB/s  speedup
bytes_test.BenchmarkEqual32                    452.89       891.07    1.97x
bytes_test.BenchmarkEqual4K                    852.71      1700.44    1.99x
bytes_test.BenchmarkEqual4M                    841.53      1587.93    1.89x
bytes_test.BenchmarkEqual64M                   838.22      1578.14    1.88x

bytes_test.BenchmarkIndex32                     58.02        48.99    0.84x
bytes_test.BenchmarkIndex4K                     48.26        41.32    0.86x
bytes_test.BenchmarkIndex4M                     48.20        41.24    0.86x
bytes_test.BenchmarkIndex64M                    48.08        41.21    0.86x
bytes_test.BenchmarkIndexEasy32                410.04       546.82    1.33x
bytes_test.BenchmarkIndexEasy4K                849.26     14257.37   16.79x
bytes_test.BenchmarkIndexEasy4M                854.54     17222.15   20.15x
bytes_test.BenchmarkIndexEasy64M               843.57     11060.40   13.11x

bytes_test.BenchmarkCount32                     57.24        50.68    0.89x
bytes_test.BenchmarkCount4K                     48.19        41.82    0.87x
bytes_test.BenchmarkCount4M                     48.18        41.74    0.87x
bytes_test.BenchmarkCount64M                    48.17        41.71    0.87x
bytes_test.BenchmarkCountEasy32                433.11       547.44    1.26x
bytes_test.BenchmarkCountEasy4K               1130.59     14194.06   12.55x
bytes_test.BenchmarkCountEasy4M               1131.23     17231.18   15.23x
bytes_test.BenchmarkCountEasy64M              1111.40     11068.88    9.96x

The non-easy Count/Index benchmarks are a worst case input.

regexp.BenchmarkMatchEasy0_32                  237.46       221.47    0.93x
regexp.BenchmarkMatchEasy0_1K                  553.53      1019.72    1.84x
regexp.BenchmarkMatchEasy0_32K                 693.99      1672.06    2.41x
regexp.BenchmarkMatchEasy0_1M                  688.72      1611.68    2.34x
regexp.BenchmarkMatchEasy0_32M                 680.70      1565.05    2.30x
regexp.BenchmarkMatchEasy1_32                  165.56       243.08    1.47x
regexp.BenchmarkMatchEasy1_1K                  336.45       496.32    1.48x
regexp.BenchmarkMatchEasy1_32K                 302.80       425.63    1.41x
regexp.BenchmarkMatchEasy1_1M                  300.42       414.20    1.38x
regexp.BenchmarkMatchEasy1_32M                 299.64       413.47    1.38x

R=golang-dev, r, iant
CC=golang-dev
https://golang.org/cl/5451116

1 files changed, 43 insertions, 10 deletions

diff --git a/src/pkg/bytes/bytes.go b/src/pkg/bytes/bytes.go
index 9bfd88fa39..307c89aa3d 100644
--- a/src/pkg/bytes/bytes.go
+++ b/src/pkg/bytes/bytes.go
@@ -37,7 +37,9 @@ func Compare(a, b []byte) int {
 }
 
 // Equal returns a boolean reporting whether a == b.
-func Equal(a, b []byte) bool {
+func Equal(a, b []byte) bool
+
+func equalPortable(a, b []byte) bool {
 	if len(a) != len(b) {
 		return false
 	}
@@ -74,18 +76,33 @@ func explode(s []byte, n int) [][]byte {
 
 // Count counts the number of non-overlapping instances of sep in s.
 func Count(s, sep []byte) int {
-	if len(sep) == 0 {
+	n := len(sep)
+	if n == 0 {
 		return utf8.RuneCount(s) + 1
 	}
+	if n > len(s) {
+		return 0
+	}
+	count := 0
 	c := sep[0]
-	n := 0
-	for i := 0; i+len(sep) <= len(s); i++ {
-		if s[i] == c && (len(sep) == 1 || Equal(s[i:i+len(sep)], sep)) {
-			n++
-			i += len(sep) - 1
+	i := 0
+	t := s[:len(s)-n+1]
+	for i < len(t) {
+		if t[i] != c {
+			o := IndexByte(t[i:], c)
+			if o < 0 {
+				break
+			}
+			i += o
 		}
+		if n == 1 || Equal(s[i:i+n], sep) {
+			count++
+			i += n
+			continue
+		}
+		i++
 	}
-	return n
+	return count
 }
 
 // Contains returns whether subslice is within b.
@@ -99,11 +116,27 @@ func Index(s, sep []byte) int {
 	if n == 0 {
 		return 0
 	}
+	if n > len(s) {
+		return -1
+	}
 	c := sep[0]
-	for i := 0; i+n <= len(s); i++ {
-		if s[i] == c && (n == 1 || Equal(s[i:i+n], sep)) {
+	if n == 1 {
+		return IndexByte(s, c)
+	}
+	i := 0
+	t := s[:len(s)-n+1]
+	for i < len(t) {
+		if t[i] != c {
+			o := IndexByte(t[i:], c)
+			if o < 0 {
+				break
+			}
+			i += o
+		}
+		if Equal(s[i:i+n], sep) {
 			return i
 		}
+		i++
 	}
 	return -1
 }