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