runtime/bytes: fast Compare for byte arrays and strings.

Uses SSE instructions to process 16 bytes at a time.

fixes #5354

R=bradfitz, google
CC=golang-dev
https://golang.org/cl/8853048

4 files changed, 214 insertions, 33 deletions

diff --git a/src/pkg/bytes/bytes.go b/src/pkg/bytes/bytes.go
index e42f744394..b07902579c 100644
--- a/src/pkg/bytes/bytes.go
+++ b/src/pkg/bytes/bytes.go
@@ -11,32 +11,6 @@ import (
 	"unicode/utf8"
 )
 
-// Compare returns an integer comparing two byte slices lexicographically.
-// The result will be 0 if a==b, -1 if a < b, and +1 if a > b.
-// A nil argument is equivalent to an empty slice.
-func Compare(a, b []byte) int {
-	m := len(a)
-	if m > len(b) {
-		m = len(b)
-	}
-	for i, ac := range a[0:m] {
-		bc := b[i]
-		switch {
-		case ac > bc:
-			return 1
-		case ac < bc:
-			return -1
-		}
-	}
-	switch {
-	case len(a) < len(b):
-		return -1
-	case len(a) > len(b):
-		return 1
-	}
-	return 0
-}
-
 func equalPortable(a, b []byte) bool {
 	if len(a) != len(b) {
 		return false
diff --git a/src/pkg/bytes/bytes_decl.go b/src/pkg/bytes/bytes_decl.go
index fbf9282752..4e761f4bfb 100644
--- a/src/pkg/bytes/bytes_decl.go
+++ b/src/pkg/bytes/bytes_decl.go
@@ -14,3 +14,10 @@ func IndexByte(s []byte, c byte) int // asm_$GOARCH.s
 // Equal returns a boolean reporting whether a == b.
 // A nil argument is equivalent to an empty slice.
 func Equal(a, b []byte) bool // asm_arm.s or ../runtime/asm_{386,amd64}.s
+
+//go:noescape
+
+// Compare returns an integer comparing two byte slices lexicographically.
+// The result will be 0 if a==b, -1 if a < b, and +1 if a > b.
+// A nil argument is equivalent to an empty slice.
+func Compare(a, b []byte) int // ../runtime/noasm_arm.goc or ../runtime/asm_{386,amd64}.s
diff --git a/src/pkg/bytes/bytes_test.go b/src/pkg/bytes/bytes_test.go
index d296224ac4..29134ac0be 100644
--- a/src/pkg/bytes/bytes_test.go
+++ b/src/pkg/bytes/bytes_test.go
@@ -47,7 +47,7 @@ type BinOpTest struct {
 	i int
 }
 
-var compareTests = []struct {
+var equalTests = []struct {
 	a, b []byte
 	i    int
 }{
@@ -73,12 +73,8 @@ var compareTests = []struct {
 	{nil, []byte("a"), -1},
 }
 
-func TestCompare(t *testing.T) {
+func TestEqual(t *testing.T) {
 	for _, tt := range compareTests {
-		cmp := Compare(tt.a, tt.b)
-		if cmp != tt.i {
-			t.Errorf(`Compare(%q, %q) = %v`, tt.a, tt.b, cmp)
-		}
 		eql := Equal(tt.a, tt.b)
 		if eql != (tt.i == 0) {
 			t.Errorf(`Equal(%q, %q) = %v`, tt.a, tt.b, eql)
@@ -90,7 +86,7 @@ func TestCompare(t *testing.T) {
 	}
 }
 
-func TestEqual(t *testing.T) {
+func TestEqualExhaustive(t *testing.T) {
 	var size = 128
 	if testing.Short() {
 		size = 32
diff --git a/src/pkg/bytes/compare_test.go b/src/pkg/bytes/compare_test.go
new file mode 100644
index 0000000000..0a36f5ad39
--- /dev/null
+++ b/src/pkg/bytes/compare_test.go
@@ -0,0 +1,204 @@
+package bytes_test
+
+import (
+	. "bytes"
+	"testing"
+)
+
+var compareTests = []struct {
+	a, b []byte
+	i    int
+}{
+	{[]byte(""), []byte(""), 0},
+	{[]byte("a"), []byte(""), 1},
+	{[]byte(""), []byte("a"), -1},
+	{[]byte("abc"), []byte("abc"), 0},
+	{[]byte("ab"), []byte("abc"), -1},
+	{[]byte("abc"), []byte("ab"), 1},
+	{[]byte("x"), []byte("ab"), 1},
+	{[]byte("ab"), []byte("x"), -1},
+	{[]byte("x"), []byte("a"), 1},
+	{[]byte("b"), []byte("x"), -1},
+	// test runtime·memeq's chunked implementation
+	{[]byte("abcdefgh"), []byte("abcdefgh"), 0},
+	{[]byte("abcdefghi"), []byte("abcdefghi"), 0},
+	{[]byte("abcdefghi"), []byte("abcdefghj"), -1},
+	// nil tests
+	{nil, nil, 0},
+	{[]byte(""), nil, 0},
+	{nil, []byte(""), 0},
+	{[]byte("a"), nil, 1},
+	{nil, []byte("a"), -1},
+}
+
+func TestCompare(t *testing.T) {
+	for _, tt := range compareTests {
+		cmp := Compare(tt.a, tt.b)
+		if cmp != tt.i {
+			t.Errorf(`Compare(%q, %q) = %v`, tt.a, tt.b, cmp)
+		}
+	}
+}
+
+func TestCompareIdenticalSlice(t *testing.T) {
+	var b = []byte("Hello Gophers!")
+	if Compare(b, b) != 0 {
+		t.Error("b != b")
+	}
+	if Compare(b, b[:1]) != 1 {
+		t.Error("b > b[:1] failed")
+	}
+}
+
+func TestCompareBytes(t *testing.T) {
+	n := 128
+	a := make([]byte, n+1)
+	b := make([]byte, n+1)
+	for len := 0; len < 128; len++ {
+		// randomish but deterministic data.  No 0 or 255.
+		for i := 0; i < len; i++ {
+			a[i] = byte(1 + 31*i%254)
+			b[i] = byte(1 + 31*i%254)
+		}
+		// data past the end is different
+		for i := len; i <= n; i++ {
+			a[i] = 8
+			b[i] = 9
+		}
+		cmp := Compare(a[:len], b[:len])
+		if cmp != 0 {
+			t.Errorf(`CompareIdentical(%d) = %d`, len, cmp)
+		}
+		if len > 0 {
+			cmp = Compare(a[:len-1], b[:len])
+			if cmp != -1 {
+				t.Errorf(`CompareAshorter(%d) = %d`, len, cmp)
+			}
+			cmp = Compare(a[:len], b[:len-1])
+			if cmp != 1 {
+				t.Errorf(`CompareBshorter(%d) = %d`, len, cmp)
+			}
+		}
+		for k := 0; k < len; k++ {
+			b[k] = a[k] - 1
+			cmp = Compare(a[:len], b[:len])
+			if cmp != 1 {
+				t.Errorf(`CompareAbigger(%d,%d) = %d`, len, k, cmp)
+			}
+			b[k] = a[k] + 1
+			cmp = Compare(a[:len], b[:len])
+			if cmp != -1 {
+				t.Errorf(`CompareBbigger(%d,%d) = %d`, len, k, cmp)
+			}
+			b[k] = a[k]
+		}
+	}
+}
+
+func BenchmarkCompareBytesEqual(b *testing.B) {
+	b1 := []byte("Hello Gophers!")
+	b2 := []byte("Hello Gophers!")
+	for i := 0; i < b.N; i++ {
+		if Compare(b1, b2) != 0 {
+			b.Fatal("b1 != b2")
+		}
+	}
+}
+
+func BenchmarkCompareBytesToNil(b *testing.B) {
+	b1 := []byte("Hello Gophers!")
+	var b2 []byte
+	for i := 0; i < b.N; i++ {
+		if Compare(b1, b2) != 1 {
+			b.Fatal("b1 > b2 failed")
+		}
+	}
+}
+
+func BenchmarkCompareBytesEmpty(b *testing.B) {
+	b1 := []byte("")
+	b2 := b1
+	for i := 0; i < b.N; i++ {
+		if Compare(b1, b2) != 0 {
+			b.Fatal("b1 != b2")
+		}
+	}
+}
+
+func BenchmarkCompareBytesIdentical(b *testing.B) {
+	b1 := []byte("Hello Gophers!")
+	b2 := b1
+	for i := 0; i < b.N; i++ {
+		if Compare(b1, b2) != 0 {
+			b.Fatal("b1 != b2")
+		}
+	}
+}
+
+func BenchmarkCompareBytesSameLength(b *testing.B) {
+	b1 := []byte("Hello Gophers!")
+	b2 := []byte("Hello, Gophers")
+	for i := 0; i < b.N; i++ {
+		if Compare(b1, b2) != -1 {
+			b.Fatal("b1 < b2 failed")
+		}
+	}
+}
+
+func BenchmarkCompareBytesDifferentLength(b *testing.B) {
+	b1 := []byte("Hello Gophers!")
+	b2 := []byte("Hello, Gophers!")
+	for i := 0; i < b.N; i++ {
+		if Compare(b1, b2) != -1 {
+			b.Fatal("b1 < b2 failed")
+		}
+	}
+}
+
+func BenchmarkCompareBytesBigUnaligned(b *testing.B) {
+	b.StopTimer()
+	b1 := make([]byte, 0, 1<<20)
+	for len(b1) < 1<<20 {
+		b1 = append(b1, "Hello Gophers!"...)
+	}
+	b2 := append([]byte("hello"), b1...)
+	b.StartTimer()
+	for i := 0; i < b.N; i++ {
+		if Compare(b1, b2[len("hello"):]) != 0 {
+			b.Fatal("b1 != b2")
+		}
+	}
+	b.SetBytes(int64(len(b1)))
+}
+
+func BenchmarkCompareBytesBig(b *testing.B) {
+	b.StopTimer()
+	b1 := make([]byte, 0, 1<<20)
+	for len(b1) < 1<<20 {
+		b1 = append(b1, "Hello Gophers!"...)
+	}
+	b2 := append([]byte{}, b1...)
+	b.StartTimer()
+	for i := 0; i < b.N; i++ {
+		if Compare(b1, b2) != 0 {
+			b.Fatal("b1 != b2")
+		}
+	}
+	b.SetBytes(int64(len(b1)))
+}
+
+func BenchmarkCompareBytesBigIdentical(b *testing.B) {
+	b.StopTimer()
+	b1 := make([]byte, 0, 1<<20)
+	for len(b1) < 1<<20 {
+		b1 = append(b1, "Hello Gophers!"...)
+	}
+	b2 := b1
+	b.StartTimer()
+	for i := 0; i < b.N; i++ {
+		if Compare(b1, b2) != 0 {
+			b.Fatal("b1 != b2")
+		}
+	}
+	b.SetBytes(int64(len(b1)))
+}