src/bytes/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 }