sort_benchmark_test.go

Documentation: golang.org/x/exp/slices

     1  // Copyright 2022 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 slices
     6  
     7  import (
     8  	"fmt"
     9  	"math/rand"
    10  	"sort"
    11  	"strconv"
    12  	"strings"
    13  	"testing"
    14  )
    15  
    16  // These benchmarks compare sorting a large slice of int with sort.Ints vs.
    17  // slices.Sort
    18  func makeRandomInts(n int) []int {
    19  	rand.Seed(42)
    20  	ints := make([]int, n)
    21  	for i := 0; i < n; i++ {
    22  		ints[i] = rand.Intn(n)
    23  	}
    24  	return ints
    25  }
    26  
    27  func makeSortedInts(n int) []int {
    28  	ints := make([]int, n)
    29  	for i := 0; i < n; i++ {
    30  		ints[i] = i
    31  	}
    32  	return ints
    33  }
    34  
    35  func makeReversedInts(n int) []int {
    36  	ints := make([]int, n)
    37  	for i := 0; i < n; i++ {
    38  		ints[i] = n - i
    39  	}
    40  	return ints
    41  }
    42  
    43  const N = 100_000
    44  
    45  func BenchmarkSortInts(b *testing.B) {
    46  	for i := 0; i < b.N; i++ {
    47  		b.StopTimer()
    48  		ints := makeRandomInts(N)
    49  		b.StartTimer()
    50  		sort.Ints(ints)
    51  	}
    52  }
    53  
    54  func makeSortedStrings(n int) []string {
    55  	x := make([]string, n)
    56  	for i := 0; i < n; i++ {
    57  		x[i] = strconv.Itoa(i)
    58  	}
    59  	Sort(x)
    60  	return x
    61  }
    62  
    63  func BenchmarkSlicesSortInts(b *testing.B) {
    64  	for i := 0; i < b.N; i++ {
    65  		b.StopTimer()
    66  		ints := makeRandomInts(N)
    67  		b.StartTimer()
    68  		Sort(ints)
    69  	}
    70  }
    71  
    72  func BenchmarkSlicesSortInts_Sorted(b *testing.B) {
    73  	for i := 0; i < b.N; i++ {
    74  		b.StopTimer()
    75  		ints := makeSortedInts(N)
    76  		b.StartTimer()
    77  		Sort(ints)
    78  	}
    79  }
    80  
    81  func BenchmarkSlicesSortInts_Reversed(b *testing.B) {
    82  	for i := 0; i < b.N; i++ {
    83  		b.StopTimer()
    84  		ints := makeReversedInts(N)
    85  		b.StartTimer()
    86  		Sort(ints)
    87  	}
    88  }
    89  
    90  func BenchmarkIntsAreSorted(b *testing.B) {
    91  	for i := 0; i < b.N; i++ {
    92  		b.StopTimer()
    93  		ints := makeSortedInts(N)
    94  		b.StartTimer()
    95  		sort.IntsAreSorted(ints)
    96  	}
    97  }
    98  
    99  func BenchmarkIsSorted(b *testing.B) {
   100  	for i := 0; i < b.N; i++ {
   101  		b.StopTimer()
   102  		ints := makeSortedInts(N)
   103  		b.StartTimer()
   104  		IsSorted(ints)
   105  	}
   106  }
   107  
   108  // Since we're benchmarking these sorts against each other, make sure that they
   109  // generate similar results.
   110  func TestIntSorts(t *testing.T) {
   111  	ints := makeRandomInts(200)
   112  	ints2 := Clone(ints)
   113  
   114  	sort.Ints(ints)
   115  	Sort(ints2)
   116  
   117  	for i := range ints {
   118  		if ints[i] != ints2[i] {
   119  			t.Fatalf("ints2 mismatch at %d; %d != %d", i, ints[i], ints2[i])
   120  		}
   121  	}
   122  }
   123  
   124  // The following is a benchmark for sorting strings.
   125  
   126  // makeRandomStrings generates n random strings with alphabetic runes of
   127  // varying lengths.
   128  func makeRandomStrings(n int) []string {
   129  	rand.Seed(42)
   130  	var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
   131  	ss := make([]string, n)
   132  	for i := 0; i < n; i++ {
   133  		var sb strings.Builder
   134  		slen := 2 + rand.Intn(50)
   135  		for j := 0; j < slen; j++ {
   136  			sb.WriteRune(letters[rand.Intn(len(letters))])
   137  		}
   138  		ss[i] = sb.String()
   139  	}
   140  	return ss
   141  }
   142  
   143  func TestStringSorts(t *testing.T) {
   144  	ss := makeRandomStrings(200)
   145  	ss2 := Clone(ss)
   146  
   147  	sort.Strings(ss)
   148  	Sort(ss2)
   149  
   150  	for i := range ss {
   151  		if ss[i] != ss2[i] {
   152  			t.Fatalf("ss2 mismatch at %d; %s != %s", i, ss[i], ss2[i])
   153  		}
   154  	}
   155  }
   156  
   157  func BenchmarkSortStrings(b *testing.B) {
   158  	for i := 0; i < b.N; i++ {
   159  		b.StopTimer()
   160  		ss := makeRandomStrings(N)
   161  		b.StartTimer()
   162  		sort.Strings(ss)
   163  	}
   164  }
   165  
   166  func BenchmarkSortStrings_Sorted(b *testing.B) {
   167  	ss := makeSortedStrings(N)
   168  	b.ResetTimer()
   169  
   170  	for i := 0; i < b.N; i++ {
   171  		sort.Strings(ss)
   172  	}
   173  }
   174  
   175  func BenchmarkSlicesSortStrings(b *testing.B) {
   176  	for i := 0; i < b.N; i++ {
   177  		b.StopTimer()
   178  		ss := makeRandomStrings(N)
   179  		b.StartTimer()
   180  		Sort(ss)
   181  	}
   182  }
   183  
   184  func BenchmarkSlicesSortStrings_Sorted(b *testing.B) {
   185  	ss := makeSortedStrings(N)
   186  	b.ResetTimer()
   187  
   188  	for i := 0; i < b.N; i++ {
   189  		Sort(ss)
   190  	}
   191  }
   192  
   193  // These benchmarks compare sorting a slice of structs with sort.Sort vs.
   194  // slices.SortFunc.
   195  type myStruct struct {
   196  	a, b, c, d string
   197  	n          int
   198  }
   199  
   200  type myStructs []*myStruct
   201  
   202  func (s myStructs) Len() int           { return len(s) }
   203  func (s myStructs) Less(i, j int) bool { return s[i].n < s[j].n }
   204  func (s myStructs) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
   205  
   206  func makeRandomStructs(n int) myStructs {
   207  	rand.Seed(42)
   208  	structs := make([]*myStruct, n)
   209  	for i := 0; i < n; i++ {
   210  		structs[i] = &myStruct{n: rand.Intn(n)}
   211  	}
   212  	return structs
   213  }
   214  
   215  func TestStructSorts(t *testing.T) {
   216  	ss := makeRandomStructs(200)
   217  	ss2 := make([]*myStruct, len(ss))
   218  	for i := range ss {
   219  		ss2[i] = &myStruct{n: ss[i].n}
   220  	}
   221  
   222  	sort.Sort(ss)
   223  	SortFunc(ss2, func(a, b *myStruct) int { return a.n - b.n })
   224  
   225  	for i := range ss {
   226  		if *ss[i] != *ss2[i] {
   227  			t.Fatalf("ints2 mismatch at %d; %v != %v", i, *ss[i], *ss2[i])
   228  		}
   229  	}
   230  }
   231  
   232  func BenchmarkSortStructs(b *testing.B) {
   233  	for i := 0; i < b.N; i++ {
   234  		b.StopTimer()
   235  		ss := makeRandomStructs(N)
   236  		b.StartTimer()
   237  		sort.Sort(ss)
   238  	}
   239  }
   240  
   241  func BenchmarkSortFuncStructs(b *testing.B) {
   242  	cmpFunc := func(a, b *myStruct) int { return a.n - b.n }
   243  	for i := 0; i < b.N; i++ {
   244  		b.StopTimer()
   245  		ss := makeRandomStructs(N)
   246  		b.StartTimer()
   247  		SortFunc(ss, cmpFunc)
   248  	}
   249  }
   250  
   251  func BenchmarkBinarySearchFloats(b *testing.B) {
   252  	for _, size := range []int{16, 32, 64, 128, 512, 1024} {
   253  		b.Run(fmt.Sprintf("Size%d", size), func(b *testing.B) {
   254  			floats := make([]float64, size)
   255  			for i := range floats {
   256  				floats[i] = float64(i)
   257  			}
   258  			midpoint := len(floats) / 2
   259  			needle := (floats[midpoint] + floats[midpoint+1]) / 2
   260  			b.ResetTimer()
   261  			for i := 0; i < b.N; i++ {
   262  				BinarySearch(floats, needle)
   263  			}
   264  		})
   265  	}
   266  }
   267  
   268  func BenchmarkBinarySearchFuncStruct(b *testing.B) {
   269  	for _, size := range []int{16, 32, 64, 128, 512, 1024} {
   270  		b.Run(fmt.Sprintf("Size%d", size), func(b *testing.B) {
   271  			structs := make([]*myStruct, size)
   272  			for i := range structs {
   273  				structs[i] = &myStruct{n: i}
   274  			}
   275  			midpoint := len(structs) / 2
   276  			needle := &myStruct{n: (structs[midpoint].n + structs[midpoint+1].n) / 2}
   277  			lessFunc := func(a, b *myStruct) int { return a.n - b.n }
   278  			b.ResetTimer()
   279  			for i := 0; i < b.N; i++ {
   280  				BinarySearchFunc(structs, needle, lessFunc)
   281  			}
   282  		})
   283  	}
   284  }
   285
View as plain text