sort_slices_benchmark_test.go

     1  // Copyright 2023 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 sort_test
     6  
     7  import (
     8  	"math/rand/v2"
     9  	"slices"
    10  	. "sort"
    11  	"strconv"
    12  	stringspkg "strings"
    13  	"testing"
    14  )
    15  
    16  // Benchmarks comparing sorting from the slices package with functions from
    17  // the sort package (avoiding functions that are just forwarding to the slices
    18  // package).
    19  
    20  func makeRandomInts(n int) []int {
    21  	r := rand.New(rand.NewPCG(42, 0))
    22  	ints := make([]int, n)
    23  	for i := 0; i < n; i++ {
    24  		ints[i] = r.IntN(n)
    25  	}
    26  	return ints
    27  }
    28  
    29  func makeSortedInts(n int) []int {
    30  	ints := make([]int, n)
    31  	for i := 0; i < n; i++ {
    32  		ints[i] = i
    33  	}
    34  	return ints
    35  }
    36  
    37  func makeReversedInts(n int) []int {
    38  	ints := make([]int, n)
    39  	for i := 0; i < n; i++ {
    40  		ints[i] = n - i
    41  	}
    42  	return ints
    43  }
    44  
    45  func makeSortedStrings(n int) []string {
    46  	x := make([]string, n)
    47  	for i := 0; i < n; i++ {
    48  		x[i] = strconv.Itoa(i)
    49  	}
    50  	Strings(x)
    51  	return x
    52  }
    53  
    54  const N = 100_000
    55  
    56  func BenchmarkSortInts(b *testing.B) {
    57  	for i := 0; i < b.N; i++ {
    58  		b.StopTimer()
    59  		ints := makeRandomInts(N)
    60  		b.StartTimer()
    61  		Sort(IntSlice(ints))
    62  	}
    63  }
    64  
    65  func BenchmarkSlicesSortInts(b *testing.B) {
    66  	for i := 0; i < b.N; i++ {
    67  		b.StopTimer()
    68  		ints := makeRandomInts(N)
    69  		b.StartTimer()
    70  		slices.Sort(ints)
    71  	}
    72  }
    73  
    74  func BenchmarkSortIsSorted(b *testing.B) {
    75  	for i := 0; i < b.N; i++ {
    76  		b.StopTimer()
    77  		ints := makeSortedInts(N)
    78  		b.StartTimer()
    79  		IsSorted(IntSlice(ints))
    80  	}
    81  }
    82  
    83  func BenchmarkSlicesIsSorted(b *testing.B) {
    84  	for i := 0; i < b.N; i++ {
    85  		b.StopTimer()
    86  		ints := makeSortedInts(N)
    87  		b.StartTimer()
    88  		slices.IsSorted(ints)
    89  	}
    90  }
    91  
    92  // makeRandomStrings generates n random strings with alphabetic runes of
    93  // varying lengths.
    94  func makeRandomStrings(n int) []string {
    95  	r := rand.New(rand.NewPCG(42, 0))
    96  	var letters = []rune("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
    97  	ss := make([]string, n)
    98  	for i := 0; i < n; i++ {
    99  		var sb stringspkg.Builder
   100  		slen := 2 + r.IntN(50)
   101  		for j := 0; j < slen; j++ {
   102  			sb.WriteRune(letters[r.IntN(len(letters))])
   103  		}
   104  		ss[i] = sb.String()
   105  	}
   106  	return ss
   107  }
   108  
   109  func BenchmarkSortStrings(b *testing.B) {
   110  	for i := 0; i < b.N; i++ {
   111  		b.StopTimer()
   112  		ss := makeRandomStrings(N)
   113  		b.StartTimer()
   114  		Sort(StringSlice(ss))
   115  	}
   116  }
   117  
   118  func BenchmarkSlicesSortStrings(b *testing.B) {
   119  	for i := 0; i < b.N; i++ {
   120  		b.StopTimer()
   121  		ss := makeRandomStrings(N)
   122  		b.StartTimer()
   123  		slices.Sort(ss)
   124  	}
   125  }
   126  
   127  func BenchmarkSortStrings_Sorted(b *testing.B) {
   128  	ss := makeSortedStrings(N)
   129  	b.ResetTimer()
   130  
   131  	for i := 0; i < b.N; i++ {
   132  		Sort(StringSlice(ss))
   133  	}
   134  }
   135  
   136  func BenchmarkSlicesSortStrings_Sorted(b *testing.B) {
   137  	ss := makeSortedStrings(N)
   138  	b.ResetTimer()
   139  
   140  	for i := 0; i < b.N; i++ {
   141  		slices.Sort(ss)
   142  	}
   143  }
   144  
   145  // These benchmarks compare sorting a slice of structs with sort.Sort vs.
   146  // slices.SortFunc.
   147  type myStruct struct {
   148  	a, b, c, d string
   149  	n          int
   150  }
   151  
   152  type myStructs []*myStruct
   153  
   154  func (s myStructs) Len() int           { return len(s) }
   155  func (s myStructs) Less(i, j int) bool { return s[i].n < s[j].n }
   156  func (s myStructs) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
   157  
   158  func makeRandomStructs(n int) myStructs {
   159  	r := rand.New(rand.NewPCG(42, 0))
   160  	structs := make([]*myStruct, n)
   161  	for i := 0; i < n; i++ {
   162  		structs[i] = &myStruct{n: r.IntN(n)}
   163  	}
   164  	return structs
   165  }
   166  
   167  func TestStructSorts(t *testing.T) {
   168  	ss := makeRandomStructs(200)
   169  	ss2 := make([]*myStruct, len(ss))
   170  	for i := range ss {
   171  		ss2[i] = &myStruct{n: ss[i].n}
   172  	}
   173  
   174  	Sort(ss)
   175  	slices.SortFunc(ss2, func(a, b *myStruct) int { return a.n - b.n })
   176  
   177  	for i := range ss {
   178  		if *ss[i] != *ss2[i] {
   179  			t.Fatalf("ints2 mismatch at %d; %v != %v", i, *ss[i], *ss2[i])
   180  		}
   181  	}
   182  }
   183  
   184  func BenchmarkSortStructs(b *testing.B) {
   185  	for i := 0; i < b.N; i++ {
   186  		b.StopTimer()
   187  		ss := makeRandomStructs(N)
   188  		b.StartTimer()
   189  		Sort(ss)
   190  	}
   191  }
   192  
   193  func BenchmarkSortFuncStructs(b *testing.B) {
   194  	cmpFunc := func(a, b *myStruct) int { return a.n - b.n }
   195  	for i := 0; i < b.N; i++ {
   196  		b.StopTimer()
   197  		ss := makeRandomStructs(N)
   198  		b.StartTimer()
   199  		slices.SortFunc(ss, cmpFunc)
   200  	}
   201  }
   202
View as plain text