benchmark-for-sort.go

package main

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

	"github.com/peterrk/slices"
)

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

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

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

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

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

func mixedInts(size int) []int {
	list := make([]int, size)
	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
	}
	return list
}

type genFunc struct {
	name string
	fn   func(int) []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 benchmark(b *testing.B, size int, gen func(int) []int, sort func([]int)) {
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		list := gen(size)
		b.StartTimer()
		sort(list)
	}
}

func benchmarkAll(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) {
				benchmark(b, sc.size, gen.fn, sort)
			})
		}
	}
}

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

func BenchmarkStd(b *testing.B) {
	benchmarkAll(b, stdsort.Ints)
}