sort_test.go

Documentation: github.com/bytedance/sonic/internal/encoder

     1  /*
     2   * Copyright 2021 ByteDance Inc.
     3   *
     4   * Licensed under the Apache License, Version 2.0 (the "License");
     5   * you may not use this file except in compliance with the License.
     6   * You may obtain a copy of the License at
     7   *
     8   *     http://www.apache.org/licenses/LICENSE-2.0
     9   *
    10   * Unless required by applicable law or agreed to in writing, software
    11   * distributed under the License is distributed on an "AS IS" BASIS,
    12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13   * See the License for the specific language governing permissions and
    14   * limitations under the License.
    15   */
    16  
    17  package encoder
    18  
    19  import (
    20      `bytes`
    21      `math/rand`
    22      `reflect`
    23      `sort`
    24      `strconv`
    25      `testing`
    26      `unsafe`
    27  )
    28  
    29  var keyLen = 15
    30  
    31  type encodedKeyValues []encodedKV
    32  type encodedKV struct {
    33  	key      string
    34  	_MapPair []byte
    35  }
    36  
    37  func (sv encodedKeyValues) Len() int           { return len(sv) }
    38  func (sv encodedKeyValues) Swap(i, j int)      { sv[i], sv[j] = sv[j], sv[i] }
    39  func (sv encodedKeyValues) Less(i, j int) bool { return sv[i].key < sv[j].key }
    40  
    41  func getKvs(std bool) interface{} {
    42      var map_size = 1000
    43      if std {
    44          kvs := make(encodedKeyValues, map_size)
    45          for i:=map_size-1; i>=0; i-- {
    46              kvs[i] = encodedKV{
    47                  key: "\"test_" + strconv.Itoa(i) + "\"",
    48              }
    49          }
    50          return kvs
    51      } else {
    52          kvs := make([]_MapPair, map_size)
    53          for i:=map_size-1; i>=0; i-- {
    54              kvs[i] = _MapPair{
    55                  k: "\"test_" + strconv.Itoa(i) + "\"",
    56              }
    57          }
    58          return kvs
    59      }
    60  }
    61  
    62  func BenchmarkSort_Sonic(b *testing.B) {
    63      ori := getKvs(false).([]_MapPair)
    64      kvs := make([]_MapPair, len(ori))
    65      b.ResetTimer()
    66      for i:=0; i<b.N; i++ {
    67          copy(kvs, ori)
    68          radixQsort(kvs, 0, maxDepth(len(kvs)))
    69      }
    70  }
    71  
    72  func BenchmarkSort_Std(b *testing.B) {
    73      ori := getKvs(true).(encodedKeyValues)
    74      kvs := make(encodedKeyValues, len(ori))
    75      b.ResetTimer()
    76      for i:=0; i<b.N; i++ {
    77          copy(kvs, ori)
    78          sort.Sort(kvs)
    79      }
    80  }
    81  
    82  func BenchmarkSort_Parallel_Sonic(b *testing.B) {
    83      ori := getKvs(false).([]_MapPair)
    84      b.ResetTimer()
    85      b.RunParallel(func(p *testing.PB) {
    86          kvs := make([]_MapPair, len(ori))
    87          for p.Next() {
    88              copy(kvs, ori)
    89              radixQsort(kvs, 0, maxDepth(len(kvs)))
    90          }
    91      })
    92  }
    93  
    94  func BenchmarkSort_Parallel_Std(b *testing.B) {
    95      ori := getKvs(true).(encodedKeyValues)
    96      b.ResetTimer()
    97      b.RunParallel(func(p *testing.PB) {
    98          kvs := make(encodedKeyValues, len(ori))
    99          for p.Next() {
   100              copy(kvs, ori)
   101              sort.Sort(kvs)
   102          }
   103      })
   104  }
   105  
   106  type kvSlice []_MapPair
   107  
   108  // Make kvSlice meet sort.Interface.
   109  func (self kvSlice) Less(i, j int) bool { return self[i].k < self[j].k }
   110  func (self kvSlice) Swap(i, j int)      { self[i], self[j] = self[j], self[i] }
   111  func (self kvSlice) Len() int           { return len(self) }
   112  
   113  //go:nosplit
   114  func (self kvSlice) Sort() {
   115      radixQsort(self, 0, maxDepth(len(self)))
   116  }
   117  
   118  func (self kvSlice) String() string {
   119      buf := bytes.NewBuffer(nil)
   120      for i, kv := range self {
   121          if i > 0 {
   122              buf.WriteByte(',')
   123          }
   124          buf.WriteString(kv.k)
   125      }
   126      return buf.String()
   127  }
   128  
   129  func TestSort_SortRandomKeys(t *testing.T) {
   130      kvs := getRandKvs(100, keyLen)
   131      sorted := make([]_MapPair, len(kvs))
   132  
   133      copy(sorted, kvs)
   134      sort.Sort(kvSlice(sorted))
   135      kvs.Sort()
   136  
   137      got := kvs.String()
   138      want := kvSlice(sorted).String()
   139      if !reflect.DeepEqual(got, want) {
   140          t.Errorf(" got: %v\nwant: %v\n", got, want)
   141      }
   142  }
   143  
   144  func genKey(kl int) []byte {
   145      l := int(rand.Uint32()%uint32(kl) + 2)
   146      k := make([]byte, l)
   147      k[0], k[l-1] = '"', '"'
   148      for i := 1; i < l-1; i++ {
   149          k[i] = byte('a' + int(rand.Uint32()%26))
   150      }
   151      return k
   152  }
   153  
   154  func getRandKvs(kn int, kl int) kvSlice {
   155      keys := make(map[string]bool)
   156      kvs := make(kvSlice, 0)
   157      for len(keys) < kn {
   158          k := genKey(kl)
   159          keys[string(k)] = true
   160      }
   161      for k := range keys {
   162          var kv _MapPair
   163          kv.k = k
   164          kv.v = unsafe.Pointer(&k)
   165          kvs = append(kvs, kv)
   166      }
   167      return kvs
   168  }
   169
View as plain text