runtime: Implement faster equals for strings and bytes.

(amd64)
benchmark           old ns/op    new ns/op    delta
BenchmarkEqual0            16            6  -63.15%
BenchmarkEqual9            22            7  -65.37%
BenchmarkEqual32           36            9  -74.91%
BenchmarkEqual4K         2187          120  -94.51%

benchmark            old MB/s     new MB/s  speedup
BenchmarkEqual9        392.22      1134.38    2.89x
BenchmarkEqual32       866.72      3457.39    3.99x
BenchmarkEqual4K      1872.73     33998.87   18.15x

(386)
benchmark           old ns/op    new ns/op    delta
BenchmarkEqual0            16            5  -63.85%
BenchmarkEqual9            22            7  -67.84%
BenchmarkEqual32           34           12  -64.94%
BenchmarkEqual4K         2196          113  -94.85%

benchmark            old MB/s     new MB/s  speedup
BenchmarkEqual9        405.81      1260.18    3.11x
BenchmarkEqual32       919.55      2631.21    2.86x
BenchmarkEqual4K      1864.85     36072.54   19.34x

Update #3751

R=bradfitz, r, khr, dave, remyoudompheng, fullung, minux.ma, ality
CC=golang-dev
https://golang.org/cl/8056043

5 files changed, 122 insertions, 34 deletions

diff --git a/src/pkg/bytes/asm_386.s b/src/pkg/bytes/asm_386.s
index 997738fe29..27cd4e787f 100644
--- a/src/pkg/bytes/asm_386.s
+++ b/src/pkg/bytes/asm_386.s
@@ -15,19 +15,3 @@ TEXT ·IndexByte(SB),7,$0
 	SUBL	$1, DI
 	MOVL	DI, ret+16(FP)
 	RET
-
-TEXT ·Equal(SB),7,$0
-	MOVL	a_len+4(FP), BX
-	MOVL	b_len+16(FP), CX
-	MOVL	$0, AX
-	CMPL	BX, CX
-	JNE	eqret
-	MOVL	a+0(FP), SI
-	MOVL	b+12(FP), DI
-	CLD
-	REP; CMPSB
-	JNE eqret
-	MOVL	$1, AX
-eqret:
-	MOVB	AX, ret+24(FP)
-	RET
diff --git a/src/pkg/bytes/asm_amd64.s b/src/pkg/bytes/asm_amd64.s
index b8f9f1b818..b84957b6d2 100644
--- a/src/pkg/bytes/asm_amd64.s
+++ b/src/pkg/bytes/asm_amd64.s
@@ -89,20 +89,3 @@ success:
 	SUBL $1, DI
 	MOVQ DI, ret+32(FP)
 	RET
-
-TEXT ·Equal(SB),7,$0
-	MOVQ	a_len+8(FP), BX
-	MOVQ	b_len+32(FP), CX
-	MOVL	$0, AX
-	CMPQ	BX, CX
-	JNE	eqret
-	MOVQ	a+0(FP), SI
-	MOVQ	b+24(FP), DI
-	CLD
-	REP; CMPSB
-	MOVL	$1, DX
-	CMOVLEQ	DX, AX
-eqret:
-	MOVB	AX, ret+48(FP)
-	RET
-
diff --git a/src/pkg/bytes/bytes_decl.go b/src/pkg/bytes/bytes_decl.go
index ce78be416a..fbf9282752 100644
--- a/src/pkg/bytes/bytes_decl.go
+++ b/src/pkg/bytes/bytes_decl.go
@@ -13,4 +13,4 @@ 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_$GOARCH.s
+func Equal(a, b []byte) bool // asm_arm.s or ../runtime/asm_{386,amd64}.s
diff --git a/src/pkg/bytes/bytes_test.go b/src/pkg/bytes/bytes_test.go
index 1d6274c33d..d296224ac4 100644
--- a/src/pkg/bytes/bytes_test.go
+++ b/src/pkg/bytes/bytes_test.go
@@ -61,6 +61,10 @@ var compareTests = []struct {
 	{[]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},
@@ -86,6 +90,58 @@ func TestCompare(t *testing.T) {
 	}
 }
 
+func TestEqual(t *testing.T) {
+	var size = 128
+	if testing.Short() {
+		size = 32
+	}
+	a := make([]byte, size)
+	b := make([]byte, size)
+	b_init := make([]byte, size)
+	// randomish but deterministic data
+	for i := 0; i < size; i++ {
+		a[i] = byte(17 * i)
+		b_init[i] = byte(23*i + 100)
+	}
+
+	for len := 0; len <= size; len++ {
+		for x := 0; x <= size-len; x++ {
+			for y := 0; y <= size-len; y++ {
+				copy(b, b_init)
+				copy(b[y:y+len], a[x:x+len])
+				if !Equal(a[x:x+len], b[y:y+len]) || !Equal(b[y:y+len], a[x:x+len]) {
+					t.Errorf("Equal(%d, %d, %d) = false", len, x, y)
+				}
+			}
+		}
+	}
+}
+
+// make sure Equal returns false for minimally different strings.  The data
+// is all zeros except for a single one in one location.
+func TestNotEqual(t *testing.T) {
+	var size = 128
+	if testing.Short() {
+		size = 32
+	}
+	a := make([]byte, size)
+	b := make([]byte, size)
+
+	for len := 0; len <= size; len++ {
+		for x := 0; x <= size-len; x++ {
+			for y := 0; y <= size-len; y++ {
+				for diffpos := x; diffpos < x+len; diffpos++ {
+					a[diffpos] = 1
+					if Equal(a[x:x+len], b[y:y+len]) || Equal(b[y:y+len], a[x:x+len]) {
+						t.Errorf("NotEqual(%d, %d, %d, %d) = true", len, x, y, diffpos)
+					}
+					a[diffpos] = 0
+				}
+			}
+		}
+	}
+}
+
 var indexTests = []BinOpTest{
 	{"", "", 0},
 	{"", "a", -1},
@@ -303,10 +359,30 @@ func bmIndexByte(b *testing.B, index func([]byte, byte) int, n int) {
 	buf[n-1] = '\x00'
 }
 
+func BenchmarkEqual0(b *testing.B) {
+	var buf [4]byte
+	buf1 := buf[0:0]
+	buf2 := buf[1:1]
+	for i := 0; i < b.N; i++ {
+		eq := Equal(buf1, buf2)
+		if !eq {
+			b.Fatal("bad equal")
+		}
+	}
+}
+
+func BenchmarkEqual1(b *testing.B)           { bmEqual(b, Equal, 1) }
+func BenchmarkEqual6(b *testing.B)           { bmEqual(b, Equal, 6) }
+func BenchmarkEqual9(b *testing.B)           { bmEqual(b, Equal, 9) }
+func BenchmarkEqual15(b *testing.B)          { bmEqual(b, Equal, 15) }
+func BenchmarkEqual16(b *testing.B)          { bmEqual(b, Equal, 16) }
+func BenchmarkEqual20(b *testing.B)          { bmEqual(b, Equal, 20) }
 func BenchmarkEqual32(b *testing.B)          { bmEqual(b, Equal, 32) }
 func BenchmarkEqual4K(b *testing.B)          { bmEqual(b, Equal, 4<<10) }
 func BenchmarkEqual4M(b *testing.B)          { bmEqual(b, Equal, 4<<20) }
 func BenchmarkEqual64M(b *testing.B)         { bmEqual(b, Equal, 64<<20) }
+func BenchmarkEqualPort1(b *testing.B)       { bmEqual(b, EqualPortable, 1) }
+func BenchmarkEqualPort6(b *testing.B)       { bmEqual(b, EqualPortable, 6) }
 func BenchmarkEqualPort32(b *testing.B)      { bmEqual(b, EqualPortable, 32) }
 func BenchmarkEqualPort4K(b *testing.B)      { bmEqual(b, EqualPortable, 4<<10) }
 func BenchmarkEqualPortable4M(b *testing.B)  { bmEqual(b, EqualPortable, 4<<20) }
diff --git a/src/pkg/bytes/equal_test.go b/src/pkg/bytes/equal_test.go
new file mode 100644
index 0000000000..a393d5e7de
--- /dev/null
+++ b/src/pkg/bytes/equal_test.go
@@ -0,0 +1,45 @@
+// Copyright 2013 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+//
+// +build linux
+
+package bytes_test
+
+import (
+	. "bytes"
+	"syscall"
+	"testing"
+	"unsafe"
+)
+
+// This file tests the situation where memeq is checking
+// data very near to a page boundary.  We want to make sure
+// equal does not read across the boundary and cause a page
+// fault where it shouldn't.
+
+// This test runs only on linux.  The code being tested is
+// not OS-specific, so it does not need to be tested on all
+// operating systems.
+
+func TestEqualNearPageBoundary(t *testing.T) {
+	pagesize := syscall.Getpagesize()
+	b := make([]byte, 4*pagesize)
+	i := pagesize
+	for ; uintptr(unsafe.Pointer(&b[i]))%uintptr(pagesize) != 0; i++ {
+	}
+	syscall.Mprotect(b[i-pagesize:i], 0)
+	syscall.Mprotect(b[i+pagesize:i+2*pagesize], 0)
+
+	// both of these should fault
+	//pagesize += int(b[i-1])
+	//pagesize += int(b[i+pagesize])
+
+	for j := 0; j < pagesize; j++ {
+		b[i+j] = 'A'
+	}
+	for j := 0; j <= pagesize; j++ {
+		Equal(b[i:i+j], b[i+pagesize-j:i+pagesize])
+		Equal(b[i+pagesize-j:i+pagesize], b[i:i+j])
+	}
+}