compare_test.go

     1  // Copyright 2013 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package bytes_test
     6  
     7  import (
     8  	. "bytes"
     9  	"fmt"
    10  	"internal/testenv"
    11  	"testing"
    12  )
    13  
    14  var compareTests = []struct {
    15  	a, b []byte
    16  	i    int
    17  }{
    18  	{[]byte(""), []byte(""), 0},
    19  	{[]byte("a"), []byte(""), 1},
    20  	{[]byte(""), []byte("a"), -1},
    21  	{[]byte("abc"), []byte("abc"), 0},
    22  	{[]byte("abd"), []byte("abc"), 1},
    23  	{[]byte("abc"), []byte("abd"), -1},
    24  	{[]byte("ab"), []byte("abc"), -1},
    25  	{[]byte("abc"), []byte("ab"), 1},
    26  	{[]byte("x"), []byte("ab"), 1},
    27  	{[]byte("ab"), []byte("x"), -1},
    28  	{[]byte("x"), []byte("a"), 1},
    29  	{[]byte("b"), []byte("x"), -1},
    30  	// test runtime·memeq's chunked implementation
    31  	{[]byte("abcdefgh"), []byte("abcdefgh"), 0},
    32  	{[]byte("abcdefghi"), []byte("abcdefghi"), 0},
    33  	{[]byte("abcdefghi"), []byte("abcdefghj"), -1},
    34  	{[]byte("abcdefghj"), []byte("abcdefghi"), 1},
    35  	// nil tests
    36  	{nil, nil, 0},
    37  	{[]byte(""), nil, 0},
    38  	{nil, []byte(""), 0},
    39  	{[]byte("a"), nil, 1},
    40  	{nil, []byte("a"), -1},
    41  }
    42  
    43  func TestCompare(t *testing.T) {
    44  	for _, tt := range compareTests {
    45  		numShifts := 16
    46  		buffer := make([]byte, len(tt.b)+numShifts)
    47  		// vary the input alignment of tt.b
    48  		for offset := 0; offset <= numShifts; offset++ {
    49  			shiftedB := buffer[offset : len(tt.b)+offset]
    50  			copy(shiftedB, tt.b)
    51  			cmp := Compare(tt.a, shiftedB)
    52  			if cmp != tt.i {
    53  				t.Errorf(`Compare(%q, %q), offset %d = %v; want %v`, tt.a, tt.b, offset, cmp, tt.i)
    54  			}
    55  		}
    56  	}
    57  }
    58  
    59  func TestCompareIdenticalSlice(t *testing.T) {
    60  	var b = []byte("Hello Gophers!")
    61  	if Compare(b, b) != 0 {
    62  		t.Error("b != b")
    63  	}
    64  	if Compare(b, b[:1]) != 1 {
    65  		t.Error("b > b[:1] failed")
    66  	}
    67  }
    68  
    69  func TestCompareBytes(t *testing.T) {
    70  	lengths := make([]int, 0) // lengths to test in ascending order
    71  	for i := 0; i <= 128; i++ {
    72  		lengths = append(lengths, i)
    73  	}
    74  	lengths = append(lengths, 256, 512, 1024, 1333, 4095, 4096, 4097)
    75  
    76  	if !testing.Short() || testenv.Builder() != "" {
    77  		lengths = append(lengths, 65535, 65536, 65537, 99999)
    78  	}
    79  
    80  	n := lengths[len(lengths)-1]
    81  	a := make([]byte, n+1)
    82  	b := make([]byte, n+1)
    83  	for _, len := range lengths {
    84  		// randomish but deterministic data. No 0 or 255.
    85  		for i := 0; i < len; i++ {
    86  			a[i] = byte(1 + 31*i%254)
    87  			b[i] = byte(1 + 31*i%254)
    88  		}
    89  		// data past the end is different
    90  		for i := len; i <= n; i++ {
    91  			a[i] = 8
    92  			b[i] = 9
    93  		}
    94  		cmp := Compare(a[:len], b[:len])
    95  		if cmp != 0 {
    96  			t.Errorf(`CompareIdentical(%d) = %d`, len, cmp)
    97  		}
    98  		if len > 0 {
    99  			cmp = Compare(a[:len-1], b[:len])
   100  			if cmp != -1 {
   101  				t.Errorf(`CompareAshorter(%d) = %d`, len, cmp)
   102  			}
   103  			cmp = Compare(a[:len], b[:len-1])
   104  			if cmp != 1 {
   105  				t.Errorf(`CompareBshorter(%d) = %d`, len, cmp)
   106  			}
   107  		}
   108  		for k := 0; k < len; k++ {
   109  			b[k] = a[k] - 1
   110  			cmp = Compare(a[:len], b[:len])
   111  			if cmp != 1 {
   112  				t.Errorf(`CompareAbigger(%d,%d) = %d`, len, k, cmp)
   113  			}
   114  			b[k] = a[k] + 1
   115  			cmp = Compare(a[:len], b[:len])
   116  			if cmp != -1 {
   117  				t.Errorf(`CompareBbigger(%d,%d) = %d`, len, k, cmp)
   118  			}
   119  			b[k] = a[k]
   120  		}
   121  	}
   122  }
   123  
   124  func TestEndianBaseCompare(t *testing.T) {
   125  	// This test compares byte slices that are almost identical, except one
   126  	// difference that for some j, a[j]>b[j] and a[j+1]<b[j+1]. If the implementation
   127  	// compares large chunks with wrong endianness, it gets wrong result.
   128  	// no vector register is larger than 512 bytes for now
   129  	const maxLength = 512
   130  	a := make([]byte, maxLength)
   131  	b := make([]byte, maxLength)
   132  	// randomish but deterministic data. No 0 or 255.
   133  	for i := 0; i < maxLength; i++ {
   134  		a[i] = byte(1 + 31*i%254)
   135  		b[i] = byte(1 + 31*i%254)
   136  	}
   137  	for i := 2; i <= maxLength; i <<= 1 {
   138  		for j := 0; j < i-1; j++ {
   139  			a[j] = b[j] - 1
   140  			a[j+1] = b[j+1] + 1
   141  			cmp := Compare(a[:i], b[:i])
   142  			if cmp != -1 {
   143  				t.Errorf(`CompareBbigger(%d,%d) = %d`, i, j, cmp)
   144  			}
   145  			a[j] = b[j] + 1
   146  			a[j+1] = b[j+1] - 1
   147  			cmp = Compare(a[:i], b[:i])
   148  			if cmp != 1 {
   149  				t.Errorf(`CompareAbigger(%d,%d) = %d`, i, j, cmp)
   150  			}
   151  			a[j] = b[j]
   152  			a[j+1] = b[j+1]
   153  		}
   154  	}
   155  }
   156  
   157  func BenchmarkCompareBytesEqual(b *testing.B) {
   158  	b1 := []byte("Hello Gophers!")
   159  	b2 := []byte("Hello Gophers!")
   160  	for i := 0; i < b.N; i++ {
   161  		if Compare(b1, b2) != 0 {
   162  			b.Fatal("b1 != b2")
   163  		}
   164  	}
   165  }
   166  
   167  func BenchmarkCompareBytesToNil(b *testing.B) {
   168  	b1 := []byte("Hello Gophers!")
   169  	var b2 []byte
   170  	for i := 0; i < b.N; i++ {
   171  		if Compare(b1, b2) != 1 {
   172  			b.Fatal("b1 > b2 failed")
   173  		}
   174  	}
   175  }
   176  
   177  func BenchmarkCompareBytesEmpty(b *testing.B) {
   178  	b1 := []byte("")
   179  	b2 := b1
   180  	for i := 0; i < b.N; i++ {
   181  		if Compare(b1, b2) != 0 {
   182  			b.Fatal("b1 != b2")
   183  		}
   184  	}
   185  }
   186  
   187  func BenchmarkCompareBytesIdentical(b *testing.B) {
   188  	b1 := []byte("Hello Gophers!")
   189  	b2 := b1
   190  	for i := 0; i < b.N; i++ {
   191  		if Compare(b1, b2) != 0 {
   192  			b.Fatal("b1 != b2")
   193  		}
   194  	}
   195  }
   196  
   197  func BenchmarkCompareBytesSameLength(b *testing.B) {
   198  	b1 := []byte("Hello Gophers!")
   199  	b2 := []byte("Hello, Gophers")
   200  	for i := 0; i < b.N; i++ {
   201  		if Compare(b1, b2) != -1 {
   202  			b.Fatal("b1 < b2 failed")
   203  		}
   204  	}
   205  }
   206  
   207  func BenchmarkCompareBytesDifferentLength(b *testing.B) {
   208  	b1 := []byte("Hello Gophers!")
   209  	b2 := []byte("Hello, Gophers!")
   210  	for i := 0; i < b.N; i++ {
   211  		if Compare(b1, b2) != -1 {
   212  			b.Fatal("b1 < b2 failed")
   213  		}
   214  	}
   215  }
   216  
   217  func benchmarkCompareBytesBigUnaligned(b *testing.B, offset int) {
   218  	b.StopTimer()
   219  	b1 := make([]byte, 0, 1<<20)
   220  	for len(b1) < 1<<20 {
   221  		b1 = append(b1, "Hello Gophers!"...)
   222  	}
   223  	b2 := append([]byte("12345678")[:offset], b1...)
   224  	b.StartTimer()
   225  	for j := 0; j < b.N; j++ {
   226  		if Compare(b1, b2[offset:]) != 0 {
   227  			b.Fatal("b1 != b2")
   228  		}
   229  	}
   230  	b.SetBytes(int64(len(b1)))
   231  }
   232  
   233  func BenchmarkCompareBytesBigUnaligned(b *testing.B) {
   234  	for i := 1; i < 8; i++ {
   235  		b.Run(fmt.Sprintf("offset=%d", i), func(b *testing.B) {
   236  			benchmarkCompareBytesBigUnaligned(b, i)
   237  		})
   238  	}
   239  }
   240  
   241  func BenchmarkCompareBytesBig(b *testing.B) {
   242  	b.StopTimer()
   243  	b1 := make([]byte, 0, 1<<20)
   244  	for len(b1) < 1<<20 {
   245  		b1 = append(b1, "Hello Gophers!"...)
   246  	}
   247  	b2 := append([]byte{}, b1...)
   248  	b.StartTimer()
   249  	for i := 0; i < b.N; i++ {
   250  		if Compare(b1, b2) != 0 {
   251  			b.Fatal("b1 != b2")
   252  		}
   253  	}
   254  	b.SetBytes(int64(len(b1)))
   255  }
   256  
   257  func BenchmarkCompareBytesBigIdentical(b *testing.B) {
   258  	b.StopTimer()
   259  	b1 := make([]byte, 0, 1<<20)
   260  	for len(b1) < 1<<20 {
   261  		b1 = append(b1, "Hello Gophers!"...)
   262  	}
   263  	b2 := b1
   264  	b.StartTimer()
   265  	for i := 0; i < b.N; i++ {
   266  		if Compare(b1, b2) != 0 {
   267  			b.Fatal("b1 != b2")
   268  		}
   269  	}
   270  	b.SetBytes(int64(len(b1)))
   271  }
   272
View as plain text