benchmark-for-sort-v2.go

package main

import (
	"math/rand"
	stdsort "sort"
	"strconv"
	"testing"

	"github.com/peterrk/slices"
)

func randomInts(list []int) {
	size := len(list)
	for i := 0; i < size; i++ {
		list[i] = rand.Int()
	}
}

func constantInts(list []int) {
	size := len(list)
	v := rand.Int()
	for i := 0; i < size; i++ {
		list[i] = v
	}
}

func descentInts(list []int) {
	size := len(list)
	v := rand.Int()
	for i := 0; i < size; i++ {
		list[i] = v + size - i
	}
}

func ascentInts(list []int) {
	size := len(list)
	v := rand.Int()
	for i := 0; i < size; i++ {
		list[i] = v + i
	}
}

func smallInts(list []int) {
	size := len(list)
	limit := size / 100
	for i := 0; i < size; i++ {
		list[i] = rand.Intn(limit)
	}
}

func mixedInts(list []int) {
	size := len(list)
	part := size / 5
	limit := part / 100
	for i := 0; i < part; i++ {
		list[i] = rand.Intn(limit)
	}
	v := rand.Int()
	for i := part; i < part*2; i++ {
		list[i] = v + i
	}
	v = rand.Int()
	for i := part * 2; i < part*3; i++ {
		list[i] = v + size - i
	}
	for i := part * 3; i < part*4; i++ {
		list[i] = rand.Int()
	}
	for i := part * 4; i < size; i++ {
		list[i] = 0
	}
}

type genFunc struct {
	name string
	fn   func([]int)
}

var pattern = []genFunc{
	genFunc{"Small", smallInts},
	genFunc{"Random", randomInts},
	genFunc{"Constant", constantInts},
	genFunc{"Descent", descentInts},
	genFunc{"Ascent", ascentInts},
	genFunc{"Mixed", mixedInts},
}

type sizeClass struct {
	name string
	size int
}

var level = []sizeClass{
	sizeClass{"1K", 1000},
	sizeClass{"10K", 10_000},
	sizeClass{"100K", 100_000},
	sizeClass{"1M", 1000_000},
}

func benchmarkInt(b *testing.B, sort func([]int)) {
	rand.Seed(0)
	for _, gen := range pattern {
		for _, sc := range level {
			b.Run(gen.name+"-"+sc.name, func(b *testing.B) {
				b.StopTimer()
				list := make([]int, sc.size)
				for i := 0; i < b.N; i++ {
					gen.fn(list)
					b.StartTimer()
					sort(list)
					b.StopTimer()
				}
			})
		}
	}
}

func BenchmarkIntGeneric(b *testing.B) {
	benchmarkInt(b, slices.Sort[int])
}

func BenchmarkIntStd(b *testing.B) {
	benchmarkInt(b, stdsort.Ints)
}

func benchmarkFloat(b *testing.B, sort func([]float64)) {
	rand.Seed(0)
	for _, sc := range level {
		b.Run(sc.name, func(b *testing.B) {
			b.StopTimer()
			list := make([]float64, sc.size)
			for i := 0; i < b.N; i++ {
				for j := 0; j < sc.size; j++ {
					list[j] = rand.Float64()
				}
				b.StartTimer()
				sort(list)
				b.StopTimer()
			}
		})
	}
}

func BenchmarkFloatGeneric(b *testing.B) {
	benchmarkFloat(b, slices.Sort[float64])
}

func BenchmarkFloatStd(b *testing.B) {
	benchmarkFloat(b, stdsort.Float64s)
}

func benchmarkString(b *testing.B, sort func([]string)) {
	rand.Seed(0)
	for _, sc := range level {
		b.Run(sc.name, func(b *testing.B) {
			b.StopTimer()
			list := make([]string, sc.size)
			for i := 0; i < b.N; i++ {
				for j := 0; j < sc.size; j++ {
					list[j] = strconv.Itoa(rand.Int())
				}
				b.StartTimer()
				sort(list)
				b.StopTimer()
			}
		})
	}
}

func BenchmarkStrGeneric(b *testing.B) {
	benchmarkString(b, slices.Sort[string])
}

func BenchmarkStrStd(b *testing.B) {
	benchmarkString(b, stdsort.Strings)
}

type object struct {
	val int
	pad [5]int
}

var order = slices.Order[object]{
	Less: func(a, b object) bool {
		return a.val < b.val
	},
	RefLess: func(a, b *object) bool {
		return a.val < b.val
	},
}

func benchmarkStruct(b *testing.B, sort func([]object)) {
	rand.Seed(0)
	for _, sc := range level {
		b.Run(sc.name, func(b *testing.B) {
			b.StopTimer()
			list := make([]object, sc.size)
			for i := 0; i < b.N; i++ {
				for j := 0; j < sc.size; j++ {
					list[j].val = rand.Int()
				}
				b.StartTimer()
				sort(list)
				b.StopTimer()
			}
		})
	}
}

func BenchmarkStructGeneric(b *testing.B) {
	benchmarkStruct(b, func(list []object) {
		order.Sort(list)
	})
}

func BenchmarkStructStd(b *testing.B) {
	benchmarkStruct(b, func(list []object) {
		stdsort.Slice(list, func(i, j int) bool {
			return list[i].val < list[j].val
		})
	})
}

func BenchmarkStableGeneric(b *testing.B) {
	benchmarkStruct(b, func(list []object) {
		order.SortStable(list)
	})
}

func BenchmarkStableStd(b *testing.B) {
	benchmarkStruct(b, func(list []object) {
		stdsort.SliceStable(list, func(i, j int) bool {
			return list[i].val < list[j].val
		})
	})
}