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