benchmark-for-sort-v3.go

package main

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

	uno "github.com/peterrk/slices"
	exp "golang.org/x/exp/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)) {
	for _, gen := range pattern {
		for _, sc := range level {
			b.Run(gen.name+"-"+sc.name, func(b *testing.B) {
				b.StopTimer()
				rand.Seed(0)
				list := make([]int, sc.size)
				for i := 0; i < b.N; i++ {
					gen.fn(list)
					b.StartTimer()
					sort(list)
					b.StopTimer()
				}
			})
		}
	}
}

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

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

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

func benchmarkFloat(b *testing.B, sort func([]float64)) {
	for _, sc := range level {
		b.Run(sc.name, func(b *testing.B) {
			b.StopTimer()
			rand.Seed(0)
			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 BenchmarkFloatUno(b *testing.B) {
	benchmarkFloat(b, uno.Sort[float64])
}

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

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

func benchmarkString(b *testing.B, sort func([]string)) {
	for _, sc := range level {
		b.Run(sc.name, func(b *testing.B) {
			b.StopTimer()
			rand.Seed(0)
			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 BenchmarkStrUno(b *testing.B) {
	benchmarkString(b, uno.Sort[string])
}

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

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

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

var order = uno.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)) {
	for _, sc := range level {
		b.Run(sc.name, func(b *testing.B) {
			b.StopTimer()
			rand.Seed(0)
			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 BenchmarkStructUno(b *testing.B) {
	benchmarkStruct(b, func(list []object) {
		order.Sort(list)
	})
}

func BenchmarkStructExp(b *testing.B) {
	benchmarkStruct(b, func(list []object) {
		exp.SortFunc(list, func(a, b object) bool {
			return a.val < b.val
		})
	})
}

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

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

func BenchmarkStableExp(b *testing.B) {
	benchmarkStruct(b, func(list []object) {
		exp.SortStableFunc(list, func(a, b object) bool {
			return a.val < b.val
		})
	})
}

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

func benchmarkPointer(b *testing.B, sort func([]*object)) {
	for _, sc := range level {
		b.Run(sc.name, func(b *testing.B) {
			b.StopTimer()
			rand.Seed(0)
			list := make([]*object, sc.size)
			for j := 0; j < sc.size; j++ {
				list[j] = new(object)
			}
			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 BenchmarkPointerUno(b *testing.B) {
	benchmarkPointer(b, func(list []*object) {
		uno.SortFunc(list, func(a, b *object) bool {
			return a.val < b.val
		})
	})
}

func BenchmarkPointerExp(b *testing.B) {
	benchmarkPointer(b, func(list []*object) {
		exp.SortFunc(list, func(a, b *object) bool {
			return a.val < b.val
		})
	})
}

func BenchmarkPointerStd(b *testing.B) {
	benchmarkPointer(b, func(list []*object) {
		std.Slice(list, func(i, j int) bool {
			return list[i].val < list[j].val
		})
	})
}